Datastrucstures And Algorithms:Graphs 图的存储表示 2、邻接表 (adjacency list) •逆邻接表实例： 有向图G1 A B 0 A 3 null 1 B 0 null 2 null 3 D null D 注意： 在说明邻接表表示图时，我们用数组表示了结点表，但本书中采用用链表表 示结点表，更具有优越性。如下图所示，其中，<C>为数据场之值为C的结点 的地址，其余类推。 <C> <D>hull <A> <A> D null <C> 16 ALDS
16 物料管理 ALDS 16 DataStrucstures And Algorithms:Graphs 图的存储表示 2、邻接表（adjacency list） •逆邻接表实例： A B C D 有向图 G1 A B 2 3 0 1 2 3 null 0 0 2 C D null null null •注意：在说明邻接表表示图时，我们用数组表示了结点表，但本书中采用用链表表 示结点表，更具有优越性。如下图所示，其中，<C>为数据场之值为C的结点 的地址，其余类推。 <C> null null null null A B C D <C> <D> <A> <A> null
Datastrucstures And Algorithms:Graphs 图的存储表示 邻接表的表 示和实现： 向图G1 A B D 顶点表 边表 tag data next adj dest link A <B> <C> B <D>A A <A> 17 ALDS
17 物料管理 ALDS 17 DataStrucstures And Algorithms:Graphs 图的存储表示 邻接表的表 示和实现： A B C D 向图 G1 顶点表 A <B> ∧ ∧ ∧ ∧ tag data next adj dest link 边表 B D C <C> <D> ∧ <A>
Datastrucstures And Algorithms:Graphs 图的存储表示 template <class VertexType,class EdgeType Graph<VertexType,EdgeType>:Graph(VertexType flag,EdgeType tag):Vertex finish flag(flag),Edge_finish_flag(tag){ Num Vertex=0;NumEdge=0;VertexType v,u;EdgeType e; Vertex<VertexType,EdgeType>*p,*q;l∥指向J顶点的指针。 cout <<"Input vertex data one by one!"<endl; head=NULL; while cin >>v,v!=Vertex finish flag){ head=new Vertex<VertexType,EdgeType>(v,head,NULL); Exception(!head,"Head is NULL!); Num Vertex ++ 18 ALDS
18 物料管理 ALDS 18 DataStrucstures And Algorithms:Graphs 图的存储表示 null template <class VertexType, class EdgeType > Graph< VertexType, EdgeType > :: Graph( VertexType flag, EdgeType tag):Vertex_finish_flag(flag),Edge_finish_flag(tag) { NumVertex = 0; NumEdge = 0; VertexType v, u; EdgeType e; Vertex<VertexType,EdgeType> * p,*q; // 指向顶点的指针。 cout << " Input vertex data one by one! " << endl; head = NULL; while ( cin >> v, v != Vertex_finish_flag ) { head = new Vertex<VertexType,EdgeType>( v, head, NULL ); Exception( !head, “Head is NULL!” ); NumVertex ++; }
Datastrucstures And Algorithms:Graphs 图的存储表示 cout<<"Input edges data one by one!"<endl; while cin >>v,cin >>u,cin >>e,e!=Edge finish flag Exception(!(p=GetVertexPos(v)),"It is NULL!"): ∥寻找边的出发顶点的地址，为空则错。 Exception (!(q=GetVertexPos(u)),"It is NULL!"): ∥寻找边的到达顶点的地址，为空则错。 p->adj=new Edge<VertexType,EdgeType>(q,e,p->adj): Exception(lp->adj,“Fail on memory！”) NumEdge++; 19 ALDS
19 物料管理 ALDS 19 DataStrucstures And Algorithms:Graphs 图的存储表示 cout << " Input edges data one by one! " << endl; while ( cin >> v, cin >> u, cin >> e, e != Edge_finish_flag ) { Exception( !(p = GetVertexPos(v)), “It is NULL!”); // 寻找边的出发顶点的地址，为空则错。 Exception (!( q = GetVertexPos(u)), “It is NULL!”); // 寻找边的到达顶点的地址，为空则错。 p->adj = new Edge<VertexType,EdgeType>( q, e, p->adj ); Exception( !p->adj, “ Fail on memory! ” ); NumEdge ++; } }
Datastrucstures And Algorithms:Graphs 图的存储表示 3、十字链表 data:结点的数据场，保存结点的 结点表中的结点的表示： 数据值。 firstout:结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 data firstin firstout firstin:结点的指针场，给出进入该 结点的第一条边的边结点的地 址。 边结点表中的结点的表示：mark:边结点的标志域。本书未使用。 mark ver1 ver2 path2 Path1 ver:本条边的出发结点 path1:出发结点相同的边 的地址。 中的下一条边的地址。 ver2:本条边的终止结点 path2:终止结点相同的边 的地址。 中的下一条边的地址。 20 ALDS
20 物料管理 ALDS 20 DataStrucstures And Algorithms:Graphs 图的存储表示 3、十字链表 data firstin firstout mark ver1 ver2 •边结点表中的结点的表示： •结点表中的结点的表示： data:结点的数据场，保存结点的 数据值。 firstout: 结点的指针场，给出自该 结点出发的的第一条边的 边结点的地址。 firstin:结点的指针场，给出进入该 结点的第一条边的 边结点的地 址。 mark:边结点的标志域 。本书未使用。 path2 Path1 ver1: 本条边的出发结点 的地址。 ver2: 本条边的终止结点 的地址。 path1:出发结点相同的边 中的下一条边的地址。 path2:终止结点相同的边 中的下一条边的地址