第7章网状结构

第7章图第7章图7.1图的基本概念

7.2图的存储结构

7.3

图的遍历

7.4图的生成树

7.5图的应用7.6图的算法C语言程序实现举例7.1图的基本概念定义及其基本运算

1.图的定义

图是n(n≥0)个元素组成的有限集合。图可以用二元组形式表示，即G=(V,E)其中，V是数据元素的集合，称为顶点集；E是数据元素之间关系的集合，称为边集。（a）无向图G1(b)有向图G2图7.1有向图和无向图图7.2无向图G1的部分子图2图的基本术语

1．图的种类（1）无向图（2）有向图（3）混合图（4）稀疏图与稠密图（5）赋权图（a）顶点赋权图(b)边赋权图图7.3赋权图2．邻接点与度（1）邻接点

（2）顶点的度

3．路径（1）路径

（2）路径长度

（3）简单路径

（4）简单图

（5）连通图（a）无向图G3（b）G3的连通分量图7.4非连通的无向图及其连通分量邻接矩阵7.2图的存储结构图的邻接矩阵表示法是用一个一维数组来存放顶点的信息，再用一个二维数组来存放边或弧的信息的表示方法，又称为数组表示法。图7.1中有向图和无向图的表示分别为。

图7-3（b）的边赋权图表示为：图7-3（b）的边赋权图表示为：图的邻接矩阵表示法具有以下特点：（1）无向图的n阶矩阵一定是对称矩阵。（2）无向图的n阶矩阵的第i行（或第i列）非零元素的个数为第i个顶点的度。（3）有向图的n阶矩阵的第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数就是第i个顶点的入度。（4）邻接矩阵表示法可以很容易确定图中任意两个顶点之间是否有边相连。

【例7.1】建立无向图的邻接矩阵存储结构。voidcreate_MGraph(Mgraph*g,inte)/*建立无向图的邻接矩阵，e为边数*/{for(i=0;i<VEX_NUM;i++)g->vexs[i]=i;/*顶点信息*/for(i=0;i<VEX_NUM;i++)

for(j=0;j<VEX_NUM;j++)g->arcs[i][j]=0;/*二维数组先赋

0*/for(k=0;k<e;k++){scanf("%d,%d",&i,&j);/*i为边的一端顶点，j为边的另一端顶点*/g->arcs[i][j]=1;g->arcs[j][i]=1;}}7.2.2邻接表图的邻接表是一种顺序分配和链式分配相结合的存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。每个链表中附设头结点，其数据域存放的是该结点的信息，指针域存放第一个与之相邻接的顶点的地址。212345V1V2V3V4V545∧3∧13∧∧54邻接表的特点如下：（1）若无向图G有n个顶点，e条边，则邻接表需要n个表头结点和2e个表结点。显然，对于边很少的图，用邻接表比用邻接矩阵要节省存储空间。（2）在无向图的邻接表中，顶点vi的度为第i个链表中表结点的个数。（3）在有向图的邻接链表中，第i个链表中的表结点的个数只是顶点vi的出度。如果要统计vi的入度，必须扫描整个邻接表，显然比较费时间。可以另外再建立一个逆邻接表，使第i个链表表示以vi为头的所有的弧。有向图G2的邻接表和逆邻接表如图7.6、7.7所示。121345V1V2V3∧V4∧V54∧25∧35∧图7.6有向图G2的邻接表表示（4）在邻接表中，若要判断两个顶点vi和vj之间是否有边或弧相连，需要遍历第i个或第j个单链表，不如邻接矩阵方便。【例7.2】建立有向图的邻接表表示法。voidcreate_ALgraph(ALgraph

g,inte)/*建立有向图的邻接表，e为弧的数目*/{for(i=1;i<=VEX_NUM;i++)/*结点下标从1开始*/{scanf("%d",&g[i].data);/*输入表结点的信息*/g[i].firstarc=NULL;}for(k=1;k<=e;k++)/*建立边表*/{scanf("%d,%d",&i,&j);/*输入边的弧尾和弧头*/p=(struct

arcnode*)malloc(sizeof(struct

arcnode));p->adjvex=j;p->nextarc=g[i].firstarc;/*插入下标为i的边表的第一个结点的位置*/g[i].firstarc=p;}}图的遍历就是按照某种顺序依次访问图中所有顶点，而且每个顶点仅访问一次。若图是连通图或强连通图，则从图中任一顶点出发都可以沿某一路径找到图中其他顶点，否则就不然。由于图中每个顶点都可能与图中其他顶点邻接并存在回路，为了避免重复访问已访问过的顶点，在图遍历的过程中，通常要对已访问的顶点作标记。图的遍历有两种基本方法：深度优先搜索和广度优先搜索。7.3图的遍历

7.3.1深度优先搜索深度优先搜索是指在图中任选一个顶点v作为出发点，并访问它，将其标记为已访问过，然后依次从顶点v未访问过的邻接顶点w出发进行深度优先搜索；若顶点w的所有邻接点均已访问过，则进行回溯到前一个访问过的顶点继续进行深度优点搜索，直到图中相连通的所有顶点都被访问。如果图中还有未访问的顶点，则从另一未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过为止。显然这是一个递归的搜索过程。【例7.3】对邻接表存储图结构的深度优先搜索算法。intvisitied[VEX_NUM+1]={0};/*visited数组存顶点被访问否，0表示未被访问*/voiddfs(ALgraph

g,inti){printf("%3d",g[i].data);/*输出已经访问的结点信息*/visited[i]=1;/*设置标志位访问过*/p=g[i].firstarc;/*p指向第一个边表的结点*/while(p!=NULL){if(visited[p->adjvex]==0)/*从未访问过的邻接点出发*/

dfs(g,p->adjvex);p=p->nextarc;/*找下一个邻接点*/}}广度优先搜索是指在图中任选一个出发点v，并访问它之后，依次访问v的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们的未曾访问过的邻接点，直至所有顶点都被访问过。通常是使用队列来存储顶点的访问序列，先将初始顶点入队列，以后每次出队列一个元素则访问之，同时将其所有邻接点顺序入对列，直到队列为空时结束广度优先搜索的过程。7.3.2广度优先搜索

【例7.4】对邻接表存储图结构的广度优先搜索算法。intvisitied[VEX_NUM+1]={0};/*visited数组存顶点被访问否，0表示未被访问*/voidbfs(ALgraph

g,inti){InitQueue(q);/*队列初始化*/printf("%3d",g[i].data);/*输出已经访问的结点信息*/visited[i]=1;/*设置标志位访问过*/InQueue(q,i);/*将i入队列*/while(!QueueEmpty(q)){DelQueue(q,i);/*出队列*/p=g[i].firstarc;

while(p!=NULL){if(visited(p->adjvex)==0)

{printf("%3d",g[i].data);visited[p->adjvex]=1;InQueue(q,p->adjvex);}p=p->nextarc;}}}7.3.3求图的连通分量

求图的连通分量是图遍历的一种简单应用。当无向图是连通时，只需调用一次dfs（或bfs）算法，便可访问图中的所有顶点。当无向图是非连通图时，从图中某顶点v出发遍历图，不能访问到图的所有顶点，而只能访问到包含v所在的最大连通子图（连通分量）中的所有顶点。若从非连通图中每个连通分量中的一个顶点出发遍历图，则可求出无向图的所有连通分量。【例7.5】对邻接表存储结构的图通过深度优先搜索算法实现求非连通图的连通分量的算法。intvisitied[VEX_NUM+1]={0};/*visited数组存顶点被访问否，0表示未被访问*/voidcon(ALgraphg){count=0;/*非连通图的连通分量的个数*/for(i=1;i<=VEX_NUM;i++)

if(!visited(i)){count++;dfs(g,i);/*调用深度优先搜索算法*/}

printf("\n共有%d个连通分量。\n",count);}7.4图的生成树

7.4.1生成树的概念对于连通图或强连通图，从任一顶点出发遍历，或是对于有根的有向图，从图的根顶点出发遍历，可以访问到所有的顶点。遍历时经过的边加上所有顶点构成图的一个连通子图，称为图的生成树。图7.8无向图G4及生成树7.4.2最小生成树在边赋权图中，权值总和最小的生成树称为最小生成树。比如，我们要建一个能连接5幢大楼的局域网络，经过初步测量后，得到了各楼之间的距离如图7.9所示。其中边上的权值表示楼间的距离。如果能找出这张图的最小生成树，就可以用最少的网络连线连接5幢大楼，完成局域网络的构建。图7.9边赋权图G5及邻接矩阵31359867396132547.4.3普里姆（Prim）算法和克鲁斯卡尔(Kruskal)算法

1．普里姆（Prim）算法Prim算法的时间主要花费在选择最小生成树的n-1条边上。整个算法的时间复杂度是O(n2)。2．克鲁斯卡尔（Kruskal）算法Kruskal算法是根据边的权值以递增的方式逐渐建立最小生成树的方法。与Prim算法不同，Kruskal算法在一开始就把所有顶点都放到最小生成树中。每次循环只根据MST性质，选择一条合适的边加到最小生成树，直到没有合适的边为止。7.5图的应用

图有很多实际的应用，在此仅介绍拓扑排序、关键路径和最短路径问题。拓扑排序研究的是工程是否顺利进行；关键路径讨论的是工程能否缩短工期，提前完工；最短路径商讨的是如何降低工程成本。7.5.1拓扑排序

1．AOV网AOV网不能有回路，否则工程无法进行，称为死锁。如图7.13所示，A、B、C三个活动互为其他活动能进行下去的前提，所以哪个活动也不能继续下去，造成死锁。在实际应用中应避免死锁现象的发生。ACB图7.13

带回路的AOV图2．拓扑排序对于一个AOV网，其所有顶点可以排成一个线性序列，该序列具有以下的性质：如果在AOV网中，从顶点vi到顶点vj存在一条路径，则在线性序列中，顶点vi一定排在顶点vj之前。具有这样性质的线性序列称为拓扑序列，构造拓扑序列的操作称为拓扑排序。7.5.2关键路径

AOE网是另一类系统工程中经常使用的图的模型，使用该模型可以很方便地分析和计算工程中的关键路径，从而可以有效地实现对工程进度的管理。1．AOE网

一个有向图可以用来估算工程的计划完成时间，这时它的顶点表示事件，边表示活动，边上权值表示活动持续的时间。这样带权的有向图称为AOE网。顶点表示的事件实际上就是它的入边所表示的活动已完成，它的出边所表示的活动可以开始的一种状态。2．关键路径

AOE网中有些活动可以并行进行，所以完成整个工程的最短时间是从开始顶点到完成顶点的最长路径长度，路径长度为路径上各边的权值之和。从源点到汇点最长的带权路径称为关键路径，关键路径的带权路径长度是完成整个工程的最短时间。（1）事件最早发生时间（ve）事件最早发生时间是从源点到该事件顶点的最长路径长度。计算方法为：

ve(v1)=0ve(vj)=max{ve(vi)+weight(<vi,vj>)}（2）事件最迟发生时间（le）最迟发生时间等于汇点最早发生时间减去该顶点到汇点的最长带权路径长度。比如事件E，最迟发生时间le(v5)=18-11=7。计算方法为：

le(vn)=ve(vn)le(vi)=min{le(vj)-weight(<vi,vj>)}（3）活动最早开始时间（e）（4）活动最晚开始时间

7.5.2最短路径

假设有一张地区图，如图7.16所示，边上的权值表示城市之间的距离。我们讨论两种最常见的最短路径问题。601050101000123455

3020图7.16

赋权有向图1．单源顶点最短路径问题求解2．求有向网中每对顶点间的路径7.6图的算法C语言程序实现举例

7.7.1无向图的邻接表的建立和遍历7.7.2有向无环图的拓扑排序和求关键路径1．有向无环图的拓扑排序2．有向无环图的关键路径1.填空题（1）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的

。（2）图的逆邻接表存储结构只适用于

图。（3）图的深度优先遍历序列

唯一的。（4）图的BFS生成树的树高比DFS生成树的数高

。（5）拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在

。（6）若要求一个稀疏图G的最小生成树，最好用

算法来求解。习题72.选择题（1）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.1/2B.1C.2D.4（2）用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。A.栈B.队列C.树D.图（3）具有n个顶点的无向完全图，边的总数为（）。A.nB.n+1C.2n-1D.n(n-1)/2（4）有n个顶点的连通图G的最小生成树有（）条边。A.n-1B.nC.n+1D.不确定（5）一个有向无环图的拓扑序列个数是（）。A.