网络(带权图)的邻接表 6 data adi dest cost link A 0A 5 21B s十316 28∧ BxC 2e 32∧ 3 D 9∧ 项点表)(出边表)
◼ 网络 (带权图) 的邻接表 B A C D 6 9 5 2 8 data adj A B C D 0 1 2 3 dest cost link 1 5 3 6 2 8 3 2 1 9 (顶点表) (出边表)
带权图的边结点中保存该边上的权值 cost 顶点i的边链表的表头指针a在顶点表的 下标为i的顶点记录中,该记录还保存了该 顶点的其它信息。 在邻接表的边链表中,各个边结点的链入 顺序任意,视边结点输入次序而定。 设图中有n个顶点,e条边,则用邻接表表 示无向图时,需要n个顶点结点,2e个边 结点;用邻接表表示有向图时,若不考虑 逆邻接表,只需n个顶点结点,e个边结点
◼ 带权图的边结点中保存该边上的权值cost。 ◼ 顶点 i 的边链表的表头指针 adj 在顶点表的 下标为 i 的顶点记录中，该记录还保存了该 顶点的其它信息。 ◼ 在邻接表的边链表中，各个边结点的链入 顺序任意，视边结点输入次序而定。 ◼ 设图中有 n 个顶点，e 条边，则用邻接表表 示无向图时，需要 n 个顶点结点，2e 个边 结点；用邻接表表示有向图时，若不考虑 逆邻接表，只需 n 个顶点结点，e 个边结点
邻接表表示的图的类定义 #define Defaultsize 10 template <class Type> class Graph; template< class Type> struct Edge{∥边结点 friend class Graph<Type>; int dest; ∥/目标顶点下标 float cost: ∥/边上的权值 E age /一边链接指针 Edge( /构造函数 Edge(int D, float C): destD), 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 * link; //下一边链接指针 Edge ( ) { } //构造函数 Edge ( int D, float C ) : dest (D), cost (C), link (NULL) { }
int operator = Edge&E) const i return dest!=E dest; j template< class Type> struct vertex{/顶点 friend class Graph <Type>; ype data; /项点数据 Edge *ad ∥/链表头指针 template< class Type> class Graph{∥图类 private
int operator != ( Edge& E ) const { return dest != E.dest; } } template <class Type> struct Vertex { //顶点 friend class Graph <Type>; Type data; //顶点数据 Edge *adj; //边链表头指针 } template <class Type> class Graph { //图类 private:
Vertex<lype>* NodeTable;点表 int Num ertices ∥/当前顶点个数 int Max Vertices 最大顶点个数 int NumEdges ∥/当前边数 int Get VertexPos( 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;)
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; }