邻接表表示的图的类定义 const int Defaultsize=10; template <class DistType> class Graph template <class DistType> struct Edge t int dests Dist'Type cost Edge<DistType> *link Eage(i Edge(int D, DistType C): dest (D), cost(C), link(null)d int operator = const Edge &e) const f return dest != Edest;)
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 NameType, class DistType> struct vertex i Neme'Type data; Edge<DistType> *adj template <class NameType, class Disttype> class Graph i friend class vertex <NameType, DistType>; friend class Edge<DistType>; pI rivate Vertex<Name Type, DistType>" Node Table int Num vertices int Maxvertices
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 NumEdges int Getvertex Pos( const Type vertex ) public Graph( int sz Graph (; int GraphEmpty o const i return Num vertices==0; int GraphFull( const f return Num vertices == Max vertices NumEdges --MarEdges; j NameType getvalue( const int i) f return i>=0 &&i< Numvertices Node Tablei] data: NULL; j
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(f return Num Vertices; 3 int NumberofEdges (freturn NumEdges; j void Insertvertex( const NameType vertex ) void Remove vertex( const int v ) void InsertEdge( const int vl, const int v2 const DistType weight) 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 )i
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 adj dest cost link dest cost link AB 39∧ pD AHB 230 6∧ 3|C 28∧ G9 Node/ able Edge linked list(出边表) 邻接表的构造函数和析构函数 template <class Name Type, class DistType> Graph<Name Type, DistType>: Graph( const int sz= DefaultSize Numvertices(O), Max vertices(sz), NumEdges(ort
template <class NameType, class DistType> Graph<NameType, DistType>:: Graph ( const int sz = DefaultSize ) : NumVertices (0), MaxVertices (sz), NumEdges (0){