第5.4连通图与生成树

PAGEPAGE3 图的结第五 5.1—图的概念三图的基本术语§5.1的基本概G由两个集合V,E构成，记作例V1={v0E1={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v有序对<vi,vj有序对<vi,vj4§5.1的基本概V2={v0,v1,v2,v3,v4无序对无序对G2图5§5.1的基本概 例1交通图（公路、铁路）例3通讯线路图例4边：各道工序之间的顺序关 §7.1的基本概e三图e1邻接点：边e=(v,u)，则称顶点v、u相邻接关联边：边e=(v,u),则称边e关连顶点v、u2顶点的度、入度、出度顶点V的度=与V顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为图的=（每条边对图的所有顶点的度数和“贡献”2度 §5.1的基本概3路径、回无向图G=（V，E）中的顶点序列v1,v2,…,vk,若i=1,2,…k-1)vv1uvk则称该序列是从顶点v到顶点u路径；若v=u例有向图D=（V，E）中的顶点序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),vv1uvk则称该序列是从顶点v到顶点u例在图1中，V0,V1,V2,V3是V0到V3的路径；V0,V1,V2,V3,V0路；在图2中，V0,V2,V3是有向无向8简单路径和简单例在图1中，V0,V1,V2,V3V0,V1,V2,V4,V1无向

有向连通图（强连通图在无（有）向图G=<V,Ev、u都存在从v到u的路径，则称G是连通图（强连通图） 图 图子 V，E1E1关联的顶点都在V1中，则称G1是G例(b)、(c)(a)的子 连通分量（强连通分量无向图G的极大连通子图称为G

§5.1的基本概G连通子图，将G有向图D的极大强连通子图称为D强连通分连通连通G1的生成生成

§5.1的基本概包含无向图G所有顶点的的极小连通子图称为G极小连通子图意思是：该子图是G若T是G的生成树当且仅当TT是G的连通子图T包含G的所有四图的基本操 第五 5.2图的结构 邻接 链 邻接多重§5.2图的结图的结构至少要保存两类信息顶点的数顶点间的关G=<VG=<VE>是图V={v0,v1,v2…vn-1},设顶点数据为它邻接矩图的邻接矩阵表示法（AdjacencyMatrix）也称作数组表示一个是用于顶点信息的一维数组；另一个用于图 若图是一个具有n个顶点的无权图，的邻接矩阵是n×n矩阵：

j]

若<vivj>或(vivj)—数组表示法(

§5.2图 结邻接矩阵：G的邻接矩阵是满足如下条件的n1若(vi,vj)E0101010101010111010001100010110000000011000若图是一个有n个顶点的网，则它的邻接矩阵是具有如下性质的n×n矩阵：

j]

若<vivj>或(vi反例如：一个有向网N,其邻接矩阵55427896155无向图数组表示法特点无向图邻接矩阵是对称矩阵，同一条边表示了两次顶点vi的度：等于二维数组i行（或列）中1的个数

§5.2图的结判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清数组表示法的空数组表示法的空只与图的顶点数有1010010110100110图的基本操作

§5.2图的结求无向图某顶点vi的度(或有向图中vi的出度)。A[I,0]A[I,n-1]中的非0个数，即数组A中第i行的非0元素的个数求有向图某顶点vi度A[0,i]到An-1,i中的非0个数，即数组A第i列的非0元素的个数检测图中的总边数。扫描整个数组A，统计出数组中非0元素的个数。无的总边数为非0元素个数的一半，而有向图的总弧数为非0元素个010101010101010111010001100000000100§5.2图的结该结点表该结点表示（ViVj）,其中的1是在一维数组中的位在一维 邻接表是图的链式结无向图的邻接顶点：通常按顺序将顶点数据例下 例21234m- 图的邻接表类型constMAX_VERTEX_NUM=

§5.2图的结typedef ode //弧结点的结intadjvex; //该弧所指向的顶点的位置 ode*nextarc; //指向下一条弧的指针VRTypeweight; //与弧相关的权值，无权则为0InfoType //指向该弧相关信息的指}typedefstructVNode //顶点结点的结VertexType //顶点信ode //指向第一条依附该顶点的}typedefstruct //图的邻接表结构定AdjList //顶点数int //图的当前顶点数和弧GraphKind //图的种类标 }无向图的邻接表的特 §5.2图的结在G邻接表中，同一条边对应两个结点(v->w,w顶点v的度：等于v对应线性链表的长度判定两顶点v，u是否邻接：要看v对应线性链表中有无应的结点4)适用于边稀疏的邻接表邻接表的空间代与图的边及顶点数均有为2234m-有向图的邻接表和逆邻接有向图的邻接例例

§5.2图的结下 113300m-

类似于无向图的2所不同的是2以同一顶点为起用线性链 类似于有向图的所类似于有向图的所不同的是例例03 03 0 02 2m-第五次作§5.2图的结三、链表 该图的链如flashheadvexheadvex表示弧头顶点在图中的位置tailvex表示弧尾顶点在图中的位置hlink指向与此弧的弧头相同的下一条弧图的链表

(a)链表弧结点结构示意firstin域(链域)用于指向以该顶点作为弧头的第一个firstin域(链域)用于指向以该顶点作为弧头的第一个弧顶点

firstout域(链域)用于指向以该顶点作为弧尾的第一个弧顶点tlink指向与此弧的弧尾相同的下一条弧(b)链表顶点结点结构示意43221432211323433441441图图有向图G1的链图的链表结构形式化定义如下＃defineMAX-VERTEX- /*最多顶点个数typedefenum{DG,DN,UDG,UDN} /*图的种类typedefstruct ode{ ode typedefstruct /*顶点信息 typedef vertex［MAX-VERTEX- /*图的顶点数和弧数 /*图的种类 } /*图的链表表示法(Orthogonal建立一个有向图的链表的算法如下voidCrtOrthList（OrthList/*从终端输入n个顶点的信息和e条弧的信息，以建立一个有向图的链表{scanf(″%d,%d&n,&e);/*从键盘输入图的顶点个数和弧的个数for(i=0;i<n;{scanf(″%c″,g.vertex［i］.firstin=NULL；g.vertex［i］}for(k=0;k<e;{scanf(″%c,%c″,&vt,i=LocateVertex（g，vt）；j= p->tailvex=i；p-p->tlink=g.vertex［i］.firstout；g.vertex［i］.firstoutp->hlink=g.vertex［j］.firstin；g.vertex［j］.firstin}}/*CrtOrthList四、邻接多重表 §5.2图 结行的操作带来不便。以下面的无向图为例，当从顶点A出发了边(A,E)之后，为了下次不再对这条边进行，就需要找到表示这条边的另一个结点加问标志。表如flash标志域：可用以标记该条边是否被搜索标志域：可用以标记该条边是否被搜索过ivex的边ivex：是该边依附的一个顶点在图 jvex：是该边依附的另一个顶点在图jlink(链域)：用于指向下一条依附于顶的位置序号

中的位置序号data域用于顶点的名字与顶点有data域用于顶点的名字与顶点有关的信息，如

jvex的边fifirstedge域用于指向第一条依附于该顶点的边dat邻接多重表中顶点结点结构 邻接多重表的结点结typedefstructEdgeNodeintmark,ivex,structEdgeNode typedefstruct{VertexDatadata;EdgeNode*firstedge;typedef /*图的顶点数和弧数 /*图的种类 /*基于图的邻接多重表表示法(AdjacencyMulti-54354345无向图G2的邻接多重§5.2图的结在不同的结构下，实现的效率 无向键盘输入数据，建立一个无向图的邻接矩阵，并输出该邻接矩在无向图的邻接矩阵的基础上计算各顶点的度，并输出有向键盘输入数据，建立一个有向图的邻接表，并输出该邻接表在有向图的邻接表的基础上计算各顶点的度，并输出§5.3

都进行一次且仅进行一次。如何确保每个顶点都被到如何确保每个顶点只被一次§5.3的图的遍历：从图的某顶点出发，图中所有顶点，并且每个顶点仅一次。为保证每一个顶点只被一次，必须对顶点进行标记，顶点vi未被，值为0；当vi已被，则值为1图的遍历有两种遍历方法（它们对无向图，有向图都适用§5.3的度优先遍从图中某顶点v1）顶点2）依次从v的未被的邻接点出发，继续对图进行深度优先遍历例求图G以V0为起点的的深度优先遍历例（1）

这是序列所经过的路由于由于没有规

深度优先遍从图中某顶点v（1）顶点

§5.3的 依次从v的未 的邻接点 出发，对图进行深度优先遍历直到与v有路径相连的顶点全部 时还有顶点未被问到，则另取一未被（1）根结点先序遍历左子树先序遍历右子树

图的遍历树的遍历有什么不如果将图顶点的邻接是不是很类似§5.3的深度优先遍历算调用深度优先遍历算法的主函bool //附设标识数voidDFSTraverse(Graph{//对图G作深度优先遍for(v=0;v<G.vexnum;visited[v]= //标识数组初始for(v=0;v<G.vexnum;if(!visited[v])DFS(G,v);//对尚未的顶点调用}深度优先遍历算法flash演§5.3的图深度优先遍历voidDFS(GraphG,int{//从顶点v出发递归地深度优先遍历图visited[v]=TRUE; //顶点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)//对v的尚未过的邻接顶点w递归调用if(!visited[w])DFS(G,}（1）顶点v并标记顶点v为已若顶点vj尚未被，则深度优先遍历递归顶点12356

§5.3的1 212553 43401 01

该图的深度优先二广度优先遍历（类似于树的按层遍历）从图中某个未被过的顶点vi出发：1）顶点vi；

§5.3的2）vi的所有未被的邻接点w1,w2,…wk依次从这些邻接点出发，它们的所有未被的邻接点依此类推，直到图中所有过的顶点的邻接点都被例求图G的以V0起点的的广度优先序由由于没有规邻接点的顺序广度优先序列不是唯一广度优先遍历算从图中某顶点vi出发1）顶点vi；（容易实现

§5.3的2）vi的所有未被的邻接点w1,w2,…wk；（容易实现3）依次从这些邻接点（在步骤2）的顶点）出发，它们的所有未被的邻接点;依此类推，直到图中所有过的顶点为实现3），需要保存在步骤(2）中的顶点，而且这些在广度优先遍历算在广度优先遍历算法中需设置一队列保存的顶点并控制遍历顶点的顺序§5.3的广度优先遍从图中某顶点v1）顶点v2）v的所有未被的邻接点w1,w2,…wk3）依次从这些邻接点出发，它们的所有未被的邻接点依此类推，直到图中所有过的顶点的邻接点都被V0V1V2 V5V6广广度优先遍历算法flash演voidBFSTraverse(MGraph{//对以数组表示的图G进行广度优先搜索遍bool //附设标识数Queue 附设队for(v=0;v<G.vexnum;++v)visited[v]=FALSE; 设置空队Qfor(v=0;v<G.vexnum;++v)if({//从每一个未被的顶点出发进行广度优先搜visited[v]=TRUE; //图中第v个顶EnQueue(Q v入队while{DeQueue(Q //队头元素出队并置为for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)if(!visited[w]{visited[wTRUE 图中w个顶EnQueue(Q, //当 的顶点w入队列}//}//}//if 图的广度优先遍历算法需要一个队列以保持过的顶点的顺序，以按顺 这些顶点邻接顶点。连通图的广度优先遍历算法为（1）初始顶点v并标记顶点v为已顶点v入队列当队列非空时则继续执行，否则算法结束出队列取得队头顶点查找顶点u的第一个邻接顶点若顶点u的邻接顶点w不存在，则转到步骤（3），否则执行后序句①若顶点w尚未被，则顶点w并标记顶点w为已②顶点w入队列③查找顶点u的的下一个邻接顶点，转到步骤（6）§§5.4 无向图的生成

§5.4生成树是通图G的一个极小的连通子图。包含图G的有顶点，但只有n-1条边，并且是连通的深度优先生成 广度优先生成最小若有通的无向图G，有n个顶点，并且它的边是值的。在G上构造最小生成树G’–它的n-1条边的权值之和

§5.4成例 例如何求连通图最小生成树要在n个城市间建立通信网，如如何求连通图最小生成树求解: 连通6个城市且

§5.4小的生成二算法加顶点算法P175算法7-算法基本步设G=（V，E）为一个具有n个顶点的带权的连通网络，T=（U，TE）为构造的生成树（1）初始时（2）在所有uU 、vV-U 的边（u,v）中选择一条权值最小的边，V(u0,v0)加入TE，同时将vV重复(2)、（3），直到U=V为止算法的flash§5.4小的生成U={V0 U={V0,V2 U={11 4 1 4

1 4

1 4 U={V0,V2,V5,V3 U={V0,V2,V5,V3,V1}U={V0,V2,V5,V3,V194§5.4小的生成三算 加边的算基本步设G=（V，E）为一个具有n个顶点的带权的连通网络，最小生成树的初状态为有n个顶点但无边的非连通T=（V，）将E，则将其加入T中，否则，将其弃循环至有N-1条边算法flash 算法的时复度为O(n，与网中的边数无关，因 算法的时间复杂度为O(eloge（为网中边的数目），因此适合于求边稀疏的网的最小生成树。33221243第六次作§5.5有向无环图及应用—AOV网扑排序键路有向无环图：没有回路的有向

§5.5应用：工程流程、生产过程中各道工序的流程、程序流程、课程的AOV网（activityonvertexnet用顶点表示活动，边表示活动的顺序关系的有向图称为AOV 某工程可分为7个子工程，若用顶点表示子工程（也称活动），用例 课程流程

§5.5某校计算机专业课程流程可用AOV网表示。其中顶点：表示课程（也称动），弧：表示课程间的先修关系课 课程名 程序设

如何安排施工计划 如何安排教学计 离散数 数据结 汇编语 算法分 计算机体

数值分

扑排1拓扑排

§5.5对工程问题，人们至少关心如下两类问题程进度的关键子工程§5.5一个可行的施工计划为：V0,V1,V2,一个可行的学习计划为可行的计划的特点：若在流程图中顶点v是顶点u的前趋，则§5.5拓扑序列：有向图D的一个顶点序列称作一个拓扑序列如果该序列中任两顶点v、u，若在D中v是u前趋，则在拓扑序列中v也是u前。拓扑排序：将有向图中顶点排成拓扑 拓扑排序的应安排施工计划（如上 判断工程流程的是否合如何判断AOV网（有向图

进行拓扑排 §5.5 拓扑排序方法在有向图选一无前趋的顶点v，输出从有向图中删除v及以v为尾的孤拓扑排序算法P182算法7-§5.5 拓扑排序算法P182算法7-拓扑排序方法的另一种描述(等价描述选择一入度0v，输出将v邻接到的顶点的入度减重复1、2直到输出全部顶点或有向图没有入度为0的顶点拓扑排序涉及的数据和操作数据：有向图，顶点的入度操作（1）择一入度0顶点v，输出（2）v邻接到的顶u的入度减在有向图选一无前趋的顶点在有向图选一无前趋的顶点v，输出从有向图中删除v及以v为尾的孤重复1、2、直至输出全部顶点或有向图中不存在无前趋顶算法的flash55532555323440416266263 为了实现拓扑排序的算法,对于给定的有向图,采用邻接表作为结构,为每个顶点设立一个链表,每个链表有一个表头结点,这些表头结点构成一个数组,表头结点中增加一个存typedef /*表头结点类型 /*顶点信息intcount; ode*firstarc; }voidTopSort(VNodeadj[],int inti,j;intSt[MAXV],top=-1;/*栈St的指针为top*/ode*p;forif /*入度为0的顶点入栈 top++; whiletop>- /*栈不为空时循环 printf("%d",i);while j=p->adjvex;adj[j].count--if{top++;St[top]=j;p=p }三AOE网与关键路

§5.5AOE网：用边表示活动，顶点表示事件，权表示活动持续的时间的网对工程人们关心两类问题的关键子工程

顶点表示事边表示活

AOE事件Vi发生表ak可以开

事件Vj发生表ak已结§5.5网、E网，都能表示工程各子工程的流程，一个用顶点表示活动，一个用边表示活动，但网侧重表示活动的前后次序，E网除表示活E网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。实际应用中采关键路径：最长的路径V1->V3->V4-相关概念关键路径：事件Vj的最早发生时间ve(j：从源点1到顶点j的最长路径长度。这个时间决定了所有以Vj的最早开始时间。事件Vj的最迟发生时间vl(j：在不影响整个工期的情况下，事件Vj必须发生的时间。活动ai的最迟开始时间l(i):在不推迟整个工程完工的前提下，活动ai最迟必须开始进行的时间，即l(i)=vl(k)-dut(〈j,k〉)，其中dut(〈j,k〉)为活动ai的持续时间。关键活动：最早开始时间=最迟开始时间的活动， l(i)=e(i)的活动事件Viak事件Vjak例如，上图是一个有8例如，上图是一个有8项活动的AOE-网。其中有6个事8,VV,a 如，活动a1需要3天，活动a4需要3天等等 事件vj的最早发生时间

§5.5 ve[j]=从源点到顶点vj的最长路径的长i事件vj的最迟发生时间vl[j]=Min{vl(k)- vl[j]=vl[n]-从顶点vj到终点的最长路径的长活动ak的最早开始时间设ak=<i,j> 活动ak的最晚开始时间e1[k]=vl[j]-活动ak的延迟时间diff[k]=e1[k]- 把活动ai的最晚开始时间e1[i]与最早开始时间ee[i]之差定义为活动ai的延迟时计算过程flash§5.5对于活动ai，若e1[i]-事件事件最早发生时最晚发生时003422666788活动最早发最晚发生时010034342225666 BBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDHBBFAECIGDH活动a10：e(10)=ve(F)=16,l(10)=vl(I)- BBFAECIGDH§5.6最短路径（一、最短路径问交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路交通咨询系统：A到B最短路计算机网发送节省费用A到B沿最短路径传路径长度：路径上边路径上边的权值之最短路径：两结点间权值之和最小的路例：求V0到V4最短路V0到V4路径：V0 V0V0V1V0V2V3V0V2V3V1

§5.6短二从某源点到其余各点的最短路带权值的有向图的单源最短路径问如何如何求从某源到其余各点的最短路径1算法Dijkstra算法的基本思

§5.6短按路径长度递增顺序求最短路径算法。与求最小生成树的普里姆算法类Dijkstra算法的基本步设V0是起始源点，U已求得最短路径终点集合。V-U=未确定最短路径的顶的集初始U长度最短的最短路径是从v0下一条长度最短的路径ViVU，先求出V0到Vi中间只U中结点的最短路径②上述最短路径中长度最小者即为下一条长度最短的路径③将所求最短路径的终点加入U中重复2）直到求出所有的最短路路径终点

-

-

-

-路径终点

（V0,v2）

a

-

-路径终点

）

（V0,V4,v3）路径终点

-

-

--路径终点

（V0,V4,v5（V0,v4,v3,V5（V0,v4,v3,V5）最短路的终

{V0,V2,V4}{V0,V2,V4,V3}

§5.6短始终无(c)第(c)第一次求得的结果第二次求得的结果05 105 182430 1 (a)一个有向网点00341823030341824303403418243 1 (e)第三次求得的结 第四次求得的结果图5- Dijkstra算 §5.6最短路voiddijstra(intcost[][N],intv{intfor(i=0i<Ni++dist[i]=cost[v][i//初始dist[v]=-for(i=0;i<N;{j=mincost(dist);//找非0、非负且最小的dist[j]if(j==0);break;dist[j]=-dist[j];//vj并入U中for(k=0;k<N;k调整dist[k] vk是尚未到达的终if(-dist[k]=-dis