邻接表表示的图的类定义 const int Defaultsize= 10; template <class DistType> class Graph; template <class DistType> struct Edge t int dest. Distlype cost Edge<DistType>link; Eage(d Edge( int D, DistType c): dest (D), cost(C), link(nullo int operator!=( const Edge &e) const i return dest !=Edest; 3
邻接表表示的图的类定义 const int DefaultSize = 10; template <class DistType> class Graph; template <class DistType> struct Edge { int dest; DistType cost; Edge<DistType> *link; Edge ( ) { } Edge ( int D, DistType C ) : dest (D), cost (C), link (NULL) { } int operator != ( const Edge &E ) const { return dest != E.dest; } }
template <class Name'Type, class DistType> struct Vertex i NemeType data Edge<DistType> *adj template <class NameType, class DistType> class graph i friend class vertex <NameType, DistType>; friend class Edge<DistType>; private: Vertex<Name'Type, DistType>*Node Table; int Numvertices int max vertices
template <class NameType, class DistType> struct Vertex { NemeType data; Edge<DistType> *adj; } template <class NameType, class DistType> class Graph { friend class vertex <NameType, DistType>; friend class Edge<DistType>; private: Vertex<NameType, DistType> *NodeTable; int NumVertices; int MaxVertices;
int NudGes int Getvertex Pos( const Type vertex ) public: Graph( int sz ) Graph (; int GraphEmpty o const i return Numvertices==0; int GraphFull( const f return Numvertices - Max vertices l NumEdges=--MarEdges;) NameType Getvalue( const int i) f return i>=0 &&i< Numvertices Node Tableidata: NULL;
int NumEdges; int GetVertexPos ( const Type & vertex ); public: Graph ( int sz ); ~Graph ( ); int GraphEmpty ( ) const { return NumVertices == 0; } int GraphFull ( ) const { return NumVertices == MaxVertices || NumEdges ==MaxEdges;} NameType GetValue ( const int i ) { return i >= 0 && i < NumVertices ? NodeTable[i].data : NULL; }
int Numberofvertices oi return Numvertices; int NumberofEdges(f return NumEdges;) void Insert vertex( const NameType vertex void Remove vertex( const int v) void InsertEdge( const int vl, const int v2 const DistType weight )i void RemoveEdge( const int vl, const int v2) DistType Getweight( const int vl, const int v2) int GetFirstNeighbor const int v ) int GetNextNeighbor( const int vl, const int v2)
int NumberOfVertices ( ) { return NumVertices; } int NumberOfEdges( ) { return NumEdges;} void InsertVertex ( const NameType & vertex ); void RemoveVertex ( const int v ); void InsertEdge ( const int v1, const int v2, const DistType weight ); void RemoveEdge ( const int v1, const int v2 ); DistType GetWeight ( const int v1, const int v2 ); int GetFirstNeighbor ( const int v ); int GetNextNeighbor( const int v1, const int v2 ); }
网络(带权图)的邻接表 data ad] dest cost link dest cost link AB 24∧ 39∧ D A,≠B 230 263 ∧ 3|C 2|8∧ G9 Nodet'able Edge Linked list(出边表) 邻接表的构造函数和析构函数 template <class NameType, class DistType> Graph<Name Type, DistType>:: Graph( const int sz= Defaultsize ) Numvertices(0), Max Vertices(sz), NumEdges(O)
网络 (带权图) 的邻接表 邻接表的构造函数和析构函数 template <class NameType, class DistType> Graph<NameType, DistType>:: Graph ( const int sz = DefaultSize ) : NumVertices(0), MaxVertices (sz), NumEdges (0){