网络(带权图)的邻接表 6 A data adi dest cost link 0A 5 36∧ 5 1B 28入 B 892e 32|∧ 3D 191∧ 项点表)(出边表)
BA CD 69 5 2 8 data adj ABCD 0123 dest cost link 1 5 3 6 2 8 3 2 1 9
带权图的边结点中保存该边上的权值 cost 」顶点的边链表的表头指针d在顶点表的 下标为i的顶点记录中,该记录还保存了该 顶点的其它信息。 g在邻接表的边链表中,各个边结点的链入 顺序任意,视边结点输入次序而定。 设图中有n个顶点,e条边,则用邻接表表 示无向图时,需要m个顶点结点,2e个边 结点;用邻接表表示有向图时,若不考虑 逆邻接表,只需n个顶点结点,e个边结点
邻接表表示的图的类定义 #define Defaultsize 10 template <class Type> class graph template< class Type> struct Edge{∥边结点 friend class Graph<Type>; int dest: ∥/目标顶点下标 float cost: /边上的权值 Edge<Iype>*link;/下一边链接指针 Edge (d 构造函数 Edge( int D, Type C) dest D), cost(C), link (NULL)
#define DefaultSize 10 template <class Type> class Graph; template <class Type> struct Edge { //边结点 friend class Graph<Type>; int dest; //目标顶点下标 float cost; //边上的权值 Edge<Type> * link; //下一边链接指针 Edge ( ) { } //构造函数 Edge ( int D, Type C ) : dest (D), cost (C), link (NULL) { }
int operator = Edge<Type>& e) consti return dest!=E dest; j template< class Type> struct Vertex{/顶点 friend class Graph <Type> Neme Type data; //项点数据 Edge< MistYpe>*adj;∥边链表头指针 template< class Type> class Graph{∥图类 private:
int operator != ( Edge<Type>& E ) const { return dest != E.dest; } } template <class Type> struct Vertex { //顶点 friend class Graph <Type>; NemeType data; //顶点数据 Edge<DistType> *adj; //边链表头指针 } template <class Type> class Graph { //图类 private:
Vertex<Type>* NodeTable;∥顶点表 int Num Vertices, ∥/当前顶点个数 int Max vertices. /最大顶点个数 int Num Edges, ∥/当前边数 int Get VertexPos( const Type vertex ) public Graph( int Sz ) aGraph (; int GraphEmpty o const f return Num Vertices ==0; 3 nt GraphFull o const freturn Num Vertices== Max Vertices;)
Vertex<Type> * NodeTable; //顶点表 int NumVertices; //当前顶点个数 int MaxVertices; //最大顶点个数 int NumEdges; //当前边数 int GetVertexPos ( const Type vertex ); public: Graph ( int sz ); ~Graph ( ); int GraphEmpty ( ) const { return NumVertices == 0; } int GraphFull ( ) const { return NumVertices == MaxVertices; }