第7章 图结构
}
ArcNode* p;
for(i=0;i (5)演示程序主函数 程序中分别建立有向图G1、无向图G2、有向网G3和无向网G4的邻接表，并显示输出所建立的每个邻接表的数据信息。 void main() { ALGraph G1,G2,G3,G4; GKind gk1=DG,gk2=UDG,gk3=DN,gk4=UDN; cout<<\建立一个有向图的邻接表G1:\\n\ CreateGraph_AL(G1,gk1); cout<<\建立一个无向图的邻接表G2:\\n\ CreateGraph_AL(G2,gk2); cout<<\有向图G1的邻接表为:\\n\ DisplyAL(G1); cout<<\无向图G2的邻接表为:\\n\ DisplyAL(G2); cout<<\ cout<<\建立一个有向网的邻接表G3:\\n\ CreateGraph_AL(G3,gk3); cout<<\建立一个无向网的邻接表G4:\\n\ CreateGraph_AL(G4,gk4); cout<<\有向网G3的邻接表为:\\n\ DisplyAL(G3); cout<<\无向网G4的邻接表为:\\n\ DisplyAL(G4); } 程序运行演示结果为： 建立一个有向图的邻接表G1: 输入顶点数和边(弧)数vexnum arcnum:6 8↙ -.179.- 第7章 图结构 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙ 输入图中8条边(弧)的信息u v: 1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5↙ 建立一个无向图的邻接表G2: 输入顶点数和边(弧)数vexnum arcnum:6 7↙ 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙ 输入图中7条边(弧)的信息u v: 1 2 1 4 2 3 2 6 5 3 5 6 5 4↙ 有向图G1的邻接表为: 0 (1): [3] [1] 1 (2): 2 (3): [5] [0] 3 (4): [2] 4 (5): [3] 5 (6): [4] [0] 无向图G2的邻接表为: 0 (1): [3] [1] 1 (2): [5] [2] [0] 2 (3): [4] [1] 3 (4): [4] [0] 4 (5): [3] [5] [2] 5 (6): [4] [1] *************************************** 建立一个有向网的邻接表G3: 输入顶点数和边(弧)数vexnum arcnum:4 4↙ 按某种顺序输入4个顶点的值: 1 2 3 4↙ 输入图中4条边(弧)和权的信息u v w: 1 2 7 1 3 1 3 4 5 4 1 9↙ 建立一个无向网的邻接表G4: 输入顶点数和边(弧)数vexnum arcnum:5 5↙ 按某种顺序输入5个顶点的值: 1 2 3 4 5↙ 输入图中5条边(弧)和权的信息u v w: 1 2 9 4 1 8 4 2 3 4 5 1 3 5 12↙ 有向网G3的邻接表为: 0 (1): [2,1] [1,7] 1 (2): 2 (3): [3,5] 3 (4): [0,9] 无向网G4的邻接表为: 0 (1): [3,8] [1,9] 1 (2): [3,3] [0,9] 2 (3): [4,12] 3 (4): [4,1] [1,3] [0,8] 4 (5): [2,12] [3,1] 说明： （1）程序演示中建立的是图7.1、图7.3中4个图的一种邻接表表示：G1.vertices、G2.vertices、G3.vertices和G4.vertices。 （2）在程序显示的结果中，第一列为顶点的下标，第二列为图中所有顶点的值。对于图，单链表中的每一项表示该顶点的邻接点的下标；对于网，单链表中的每一项表示该顶点的邻接点的下标值和相应边（弧）的权值。 （3）在建立邻接表时，由于输入的是顶点信息，所以要先通过查找求得该顶点在图中的位置，再将相应结点插入到对应单链表的首部，所以，该操作的时间复杂度为O(n*e)。 7.2.3有向图的十字链表表示法 十字链表是有向图的另一种链式存储结构，该方法是将有向图的邻接表和逆邻接表结合起来得到的一种链表。 1．十字链表的定义 类似邻接表，在十字链表中包含链表的头结点和弧结点两种类型的结点，图7.13给出十字链结点结构的示图。 其中，头结点包含顶点信息域(data)、指向以该顶点为弧头的第一个弧结点的指针域(firstin)、指向以该顶点为弧尾的第一个弧结点的指针域(firstout)，表的所有头结点以顺序存储。弧结点包含表示弧尾顶点下标的尾域(tailvex)、表示弧头顶点下标的头域(headvex)、指向弧头相同的下一条弧的指针域(hlink)、指向弧尾相同的下一条弧的指针域(tlink)、弧的信息（如权 -.180.- 第7章 图结构 值）域(info)。 例如，图7.14给出有向图的一种十字链表表示。 如果将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的十字链表存储结构。在有向图的十字链表表示中，链表的头结点之间是顺序存储结构，弧结点所在的链表是非循环链表，结点之间的相对位置自然形成，不一定按顶点序列号有序。由此可见，有向图的十字链表表示方式是不唯一的。 2．十字链表的存储表示与实现 (1)十字链表存储结构的类型定义 下面分别给出十字链弧结点(ArcBox)、顶点结点(OLVexNode)、十字链表(OLGraph)的类型定义。 struct ArcBox{ //弧结点的结构定义 int tailvex,headvex; //定义弧尾和弧头顶点的位置 ArcBox *hlink,*tlink; //弧头相同、弧尾相同的弧的链域 int weight; //定义有向网中弧的权值 }; struct OLVexNode{ //顶点结点结构定义 VType data; //顶点信息 ArcBox *firstin,*firstout; //分别指向顶点的第一条入弧和出弧 }; struct OLGraph{ //定义十字链表类型 OLVexNode *xlist; //链表头结点数组指针 int vexnum,arcnum; //有向图的顶点数和弧数 GKind kind; }; (2)十字链表的查找操作 函数int LocateVex_OLG(OLGraph G,VType u) 返回顶点u在图G中的位置，如果查找失败则返回0值。 int LocateVex_OLG(OLGraph G,VType u) { int i; for(i=0;i -.181.- 第7章 图结构 } else return(0); (3)建立十字链表的算法实现 函数void CreateGraph_OLG(OLGraph& G,GKind kind)根据图的类型kind建立一个有向图或有向网的十字链表G。 void CreateGraph_OLG(OLGraph& G,GKind kind) { int i,j,k; VType u,v; ArcBox* pr; G.kind=kind; cout<<\输入顶点数和边(弧)数vexnum arcnum:\ cin>>G.vexnum>>G.arcnum; G.xlist=new OLVexNode[G.vexnum]; //为顶点数组分配内存空间 cout<<\按某种顺序输入\.vexnum<<\个顶点的值:\\n\ for(i=0;i 函数void DisplyOLG(OLGraph G)分别按邻接表和逆邻接表方式显示当前十字链表G的信息。 void DisplyOLG(OLGraph G) { int i; ArcBox* p; -.182.-