在有向图中,统计第i行1的个数可得顶点 i的出度,统计第j行1的个数可得顶点j 的入度。 在无向图中,统计第i行(列)1的个数可得 顶点i的度。 网络的邻接矩阵 w(,),若i≠诅<i,j>∈E或(;j)∈E Aedge[ilj]=oo 若i≠诅且<ij>∈E或(i,jE 0 若i=J
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
2 8③ 6 o092 39 5208-3508 00o60 用邻接矩阵表示的图的类的定义 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 J[Max Vertices]; int CurrentEdges int Find Vertex(Seq List <Type> l; const Type vertex)f return L Find(vertex);) int Get Vertex Pos( int vertex f return Find Vertex( VerticesList, vertex);) public Graph( int Sz= MaxEdges )
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 () const i return VerticesList IsEmpty (; int GraphFull( const i return VerticesList. IsFullo Currentedges--MaxEdges; j int Numberof Vertices() f return VerticesList last +1; int NumberofEdges( f return CurrentEdges; j Type Get Value( int 1) freturn i>=0 &&i<- verticesList last 2 VerticesList datai]: 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; }
Dist'Type 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 vI, int v2, float weight ) void Remove Vertex (int v )i void RemoveEdge( int v1, 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 ); }