第7章 图结构

}

ArcNode* p;

for(i=0;iadjvex<<\ else //对于网要输出下标与对应的权的值 cout<<'['<adjvex<<','<weight<<\ p=p->nextarc; } cout<

(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>G.xlist[i].data; //输入所有顶点的信息到data中 G.xlist[i].firstin=G.xlist[i].firstout=NULL; //设定初始的单链表为空 } if(G.kind==DG)cout<<\输入图中\条弧的信息u v:\\n\ else cout<<\输入图中\.arcnum<<\条弧和权的信息u v w:\\n\ for(k=0;k>u>>v; } while(!((i=LocateVex_OLG(G,u))&&(j=LocateVex_OLG(G,v)))); pr=new ArcBox; //动态分配弧存储空间 pr->tailvex=--i; //i从位置值转换为下标值 pr->headvex=--j; //j从位置值转换为下标值 if(G.kind==DN)cin>>pr->weight; pr->hlink=G.xlist[j].firstin; //将输入的弧插入到相应链表的首部 G.xlist[j].firstin=pr; pr->tlink=G.xlist[i].firstout; G.xlist[i].firstout=pr; }//end for } (4)显示十字链表信息的操作

函数void DisplyOLG(OLGraph G)分别按邻接表和逆邻接表方式显示当前十字链表G的信息。

void DisplyOLG(OLGraph G) { int i; ArcBox* p;

-.182.-