网络的邻接矩阵 W(G,j),如果i!=j且<j>∈E或(j)∈E AEg/={∞香则但是i!= 0,对角线i==j ①①②③ A.Edge=∞ 3508② 60丿③
, ( , ) , , ( , ), . [ ][ ] 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 private: Seqlist<Name Type> verticesList(Max vertices) Dist'Type Edge[ Max vertices [Max vertices int CurrentEdges, int Find vertex( seq list<NameType>& 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 Name Type &vertex f return Findvertex(VerticesList, vertex ;3 publics Graph( const int sz-MaxNumEdges ) int GraphEmptyo const i return VerticesList. IsEmpty ;j int GraphFullo const( return Verticeslist ISFullol CurrentEdges --MaxEdges, 3 int Numberofvertices O freturn VerticesList last; j int NumberofEdges( return CurrentEdges; j
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; }
Name Type Getvalue( const int i) f return i>=0 &&i< verticesList last VerticesList data: NULL; int GetWeight( const int v1, 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 vl, 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<Name Type, DistType>: Graph(const int sz)t 构造函数 for (int i=0; i< Sz; i++) for( intj=0;j< Sz;++)Edge=0 Currentedges =0; template <class NameType, class DistType> DistType Graph<Name Type, DistType> GetWeight( const int vl, const int v2)( )给出以顶点和ν2为两端点的边上的权值
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 为两端点的边上的权值