网络的邻接矩阵 W(,j,如果i=j且<i,j>∈E或(j)∈E AE(ge={∞,否则但是i!=j 0,对角线i=j Aedge=
网络的邻接矩阵 , ( , ) , , ( , ), . [ ][ ] i j i j W i j i j i j E i j E Edge i j == != ! < 0 A = 对角线 否则,但是 如果 = 且 或
用邻接矩阵表示的图的类的定义 const int MaxEdges =50 const int Max Vertices=10 template <class NameType, class Disttype> class graph i rivate Seqlist<NameType> vertices list(max vertices); DistType Edge Max vertices [Max vertices]: int CurrentEdges int Findvertex( Seq list<Name Type>& l; const Name Type &vertex f return L Find(vertex);)
用邻接矩阵表示的图的类的定义 const int MaxEdges = 50; const int MaxVertices = 10; template <class NameType, class DistType> class Graph { private: SeqList<NameType> VerticesList (MaxVertices); DistType Edge[MaxVertices][MaxVertices]; int CurrentEdges; int FindVertex ( SeqList<NameType> & L; const NameType &vertex ) { return L.Find (vertex); }
int GetvertexPos( const NameType &vertex f return Find Vertex(verticesList, vertex );3 ublic. Graph( const int Sz-MaxNumEdges )i int GraphEmpty( consti return Verticeslist ISEmpty (;j int GraphFullo const return VerticesList. IsFullo I CurrentEdges=-MaxEdges; j int Numberofvertices( f return VerticesList last;) int NumberofEdges(i return CurrentEdges
int GetVertexPos ( Const NameType &vertex ) { return FindVertex (VerticesList, vertex ); } public: Graph ( const int sz=MaxNumEdges); int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); } int GraphFull( ) const { return VerticesList.IsFull( ) || CurrentEdges ==MaxEdges;} int NumberOfVertices( ) { return VerticesList.last;} int NumberOfEdges( ) { return CurrentEdges;}
NameType Getvalue( const int i) freturn i>=0 &&i< verticesList last 9 VerticesList datai: NULL int GetWeight( const int vl, const int v2 int GetFirstNeighbor const int v ) int GetNextNeighbor( const int vl, const int v2 ) void Insert vertex( const NameType vertex ) void Insertedge const int vl, const int v2, DistType weight ) void Remove vertex( const int v) void RemoveEdge( const int vI, const int v2 )
NameType GetValue ( const int i ) { return i >= 0 && i < VerticesList.last ? VerticesList.data[i] : NULL; } int GetWeight ( const int v1, const int v2 ); int GetFirstNeighbor ( const int v ); int GetNextNeighbor( const int v1, const int v2 ); void InsertVertex ( const NameType & vertex ); void InsertEdge ( const int v1, const int v2, DistType weight ); void RemoveVertex ( const int v ); void RemoveEdge ( const int v1, const int v2 ); }
邻接矩阵实现的部分图操作 template <class Name Type, class DistType> Graph<NameType, Dist Type>:: Graph( const int sz) /构造函数 for(inti=0;i<s;计+) for( intj=0;j< Sz;j++) EdgeLl=0; Currentedges=0 template <class NameType, class DistType> DistType Graph<Name Type, DistType> GetWeight( const int vl, const int v2) )给出以顶点ν和ν为两端点的边上的权值
邻接矩阵实现的部分图操作 template <class NameType, class DistType> Graph<NameType, DistType>::Graph(const int sz){ //构造函数 for ( int i = 0; i < sz; i++ ) for ( int j = 0; j < sz; j++ ) Edge[i][j] = 0; CurrentEdges = 0; } template <class NameType, class DistType> DistType Graph<NameType, DistType>:: GetWeight( const int v1, const int v2 ) { //给出以顶点v1 和 v2 为两端点的边上的权值