在有向图中,统计第i行1的个数可得顶点 i的出度,统计第j行1的个数可得顶点j 的入度。 在无向图中,统计第i行(列1的个数可得 顶点的度。 网络的邻接矩阵 w(,)若i≠诅<i,>∈E或ij∈E A.edgelilii 若i≠沮且<ij>E或i,j)≠E 0 若
◼ 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 行 1 的个数可得顶点 j 的入度。 ◼ 在无向图中, 统计第 i 行 (列) 1 的个数可得 顶点i 的度。 网络的邻接矩阵 = = = i j i j i , j i , j i j i j i , j i , j i j 若 若 且 或 若 且 或 , , ( ) ( , ), ( ) [ ][ ] 0 E E W E E A.edge
8 (2 6 o092 3 5 2 edge 3508 60 0 用邻接矩阵表示的图的类的定义 const int MaxEdges=50 const int Max vertices=10; template <class Type>
8 6 3 1 9 2 5 4 2 0 3 1 = 6 0 3 5 0 8 0 9 2 0 1 4 A.edge 用邻接矩阵表示的图的类的定义 const int MaxEdges = 50; const int MaxVertices = 10; template <class Type>
class graph i private Seqlist<Type> verticeslist(Max vertices) float Edge[Max Vertices [ Max Vertices ] int CurrentEdges int Find Vertex(Seq List <Type>& li const Type vertex) return L Find(vertex);) int Get VertexPos( int vertex) f return Find Vertex( VerticesList, vertex);) public Graph( int sz= Max Edges )
class Graph { private: SeqList<Type> VerticesList (MaxVertices); float Edge[MaxVertices][MaxVertices]; int CurrentEdges; int FindVertex (SeqList <Type> & L; const Type vertex){ return L.Find (vertex); } int GetVertexPos ( int vertex ) { return FindVertex (VerticesList, vertex); } public: Graph ( int sz = MaxEdges );
int GraphEmpty O const( return VerticesList IsEmpty (;) int GraphFullo) const( return Verticeslist IsFulloll CurrentEdges=-MaxEdges; j int NumberOfVertices () f return VerticesList last +1; int NumberOfEdges f return CurrentEdges;5 Type Get value( int 1) f return i>=0 &&i<= VerticesList last 2 VerticesList data1: NULL
int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); } int GraphFull( ) const { return VerticesList.IsFull( ) || CurrentEdges == MaxEdges; } int NumberOfVertices ( ) { return VerticesList.last +1; } int NumberOfEdges ( ) { return CurrentEdges; } Type GetValue ( int i ) { return i >= 0 && i <= VerticesList.last ? VerticesList.data[i] : NULL; }
DistType Get Weight( int vl, int v2); int Get FirstNeighbor( int v ); int GetNextNeighbor( int vI, int v2 ) void Insert Vertex( const Type vertex ) void InsertEdge int vl, int v2, float weight ) void Remove Vertex(int v); void RemoveEdge(int vl, int v2 ) 邻接矩阵实现的部分图操作
DistType GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); void InsertVertex ( const Type vertex ); void InsertEdge ( int v1, int v2, float weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); } 邻接矩阵实现的部分图操作