数据结构第七章 图幻灯片.ppt

《数据结构第七章 图幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章 图幻灯片.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第七章 图第1页，共88页，编辑于2022年，星期六 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成的数构成的数据结构。据结构。Graph=(V,R)其中，VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧头弧头，w 为弧尾弧尾。谓词 P(v,w)定义了弧 的意义或信息。7.1 图的定义和术语图的定义和术语第2页，共88页，编辑于2022年，星期六 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图有向图。AB E C D例如例如:G1=(V1,VR1)其中V1=A,B,C,D,EVR1=,第3页，共88页，编辑于2022年，星期六

2、若VR 必有VR,则称(v,w)为顶点v 和顶点 w 之间存在一条边边。B CA D F E由顶点集和边集构成的图称作无无向图向图。例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=,第4页，共88页，编辑于2022年，星期六名词和术语名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林第5页，共88页，编辑于2022年，星期六ABECFAEFBBC设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G 为 G 的子图子图。1597211132 弧或边带权的图分别

3、称作有向网有向网或无向无向网网。第6页，共88页，编辑于2022年，星期六假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完完全图全图；含有 e=n(n-1)条弧的有向图称作 有有向完全图向完全图；若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。第7页，共88页，编辑于2022年，星期六 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点邻接点，ACDFE例如例如:ID(B)=3ID(A)=2 边(v,w)和顶点v 和w 相关联关联。和顶点v 关联的边的数目边的数目定义为边的度度。B第8页，共88页，编辑于2022年，星

4、期六顶点的出度出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说对有向图来说，顶点的入度入度:以顶点v为弧头的弧的数目。顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)例如例如:ID(B)=2OD(B)=1TD(B)=3第9页，共88页，编辑于2022年，星期六设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECF如如:长度为3的路径A,B,C,F简单路径简单路径:序列中顶点不重复出现的路径。简单回路简单回路:序列中第一个

5、顶点和最后一个顶点相同的路径。第10页，共88页，编辑于2022年，星期六若图G中任意两个顶点之间都有路径相通，则称此图为连通图连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量连通分量。BACDFEBACDFE第11页，共88页，编辑于2022年，星期六 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF对有向图，对有向图，否则，其各个强连通子图称作它的强连强连通分量通分量。第12页，共88页，编辑于2022年，星期六 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此

6、连通图的生生成树成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。BACDFE第13页，共88页，编辑于2022年，星期六结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧基本操作基本操作第14页，共88页，编辑于2022年，星期六CreatGraph(&G,V,VR):/按定义(V,VR)构造图DestroyGraph(&G):/销毁图结构的建立和销毁结构的建立和销毁第15页，共88页，编辑于2022年，星期六对顶点的访问操作对顶点的访问操作LocateVex

7、(G,u);/若G中存在顶点u，则返回该顶点在/图中“位置位置”；否则返回其它信息。GetVex(G,v);/返回 v 的值。PutVex(&G,v,value);/对 v 赋值value。第16页，共88页，编辑于2022年，星期六对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回 v 的“第一个邻接点第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(G,v,w);/返回 v 的（相对于 w 的）“下一个邻接下一个邻接/点点”。若 w 是 v 的最后一个邻接点，则/返回“空”。第17页，共88页，编辑于2022年，星期六插入或删除顶点插入或

8、删除顶点InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧。第18页，共88页，编辑于2022年，星期六插入和删除弧插入和删除弧InsertArc(&G,v,w);/在G中增添弧，若G是无向的，/则还增添对称弧。DeleteArc(&G,v,w);/在G中删除弧，若G是无向的，/则还删除对称弧。第19页，共88页，编辑于2022年，星期六遍遍 历历DFSTraverse(G,v,Visit();/从顶点v起深度优先深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit();/从

9、顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。第20页，共88页，编辑于2022年，星期六7.2 图的存储表示图的存储表示一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示第21页，共88页，编辑于2022年，星期六Aij=0 (i,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为第22页，共88页，编辑于2022年，星期六有向图的邻接矩阵为有向图的邻接矩阵为非对称矩阵非对称矩阵ABECF第23页，共88页，编辑于2022年，星期六

10、typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;第24页，共88页，编辑于2022年，星期六typedef struct /图的定义图的定义 VertexType /顶点信息 vexsMAX_VERTEX_NUM;AdjMatrix arcs;/弧的信息 int vexnum,arcnum;/顶点数，弧数 GraphKind

11、 kind;/图的种类标志 MGraph;第25页，共88页，编辑于2022年，星期六0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE二、图的邻接表二、图的邻接表 存储表示存储表示第26页，共88页，编辑于2022年，星期六1 4230 120 1 2 3 4 A B C D E有向图的邻接表有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。第27页，共88页，编辑于2022年，星期六ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的邻接表中，对每个顶点，链接的是指向该顶

12、点的弧。第28页，共88页，编辑于2022年，星期六typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info;/该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构第29页，共88页，编辑于2022年，星期六typedef struct VNode VertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;da

13、ta firstarc顶点的结点结构顶点的结点结构第30页，共88页，编辑于2022年，星期六typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;图的结构定义图的结构定义第31页，共88页，编辑于2022年，星期六三、有向图的十字链表存储表示三、有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾有相同弧尾的结点指向下一个有相同弧头有相同弧头的结点typedef struct ArcBox /弧的结构表示弧的结构表示 int tailvex

14、,headvex;InfoType *info;struct ArcBox *hlink,*tlink;VexNode;第32页，共88页，编辑于2022年，星期六顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;VexNode;第33页，共88页，编辑于2022年，星期六typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点(表头向量)

15、int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)第34页，共88页，编辑于2022年，星期六四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox *ilink,*jlink;InfoType *info;/该边信息指针 EBox;边的结构表示边的结构表示第35页，共88页，编辑于2022年，星期六typedef struct /邻接多重表邻接多重表 VexBox adjmulis

16、tMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data;EBox *firstedge;/指向第一条依附该顶点的边 VexBox;无向图的结构表示无向图的结构表示第36页，共88页，编辑于2022年，星期六7.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历应用举例遍历应用举例第37页，共88页，编辑于2022年，星期六 从图中某个顶点V0 出发，访问

17、此顶点，然后依次从依次从V0的各个未被访问的邻接点出发的各个未被访问的邻接点出发深度优先搜索遍历图深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图的深度优先搜索遍历连通图的深度优先搜索遍历第38页，共88页，编辑于2022年，星期六Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3w2第39页，共88页，编辑于2022年，星期六从上页的图解可见从上页

18、的图解可见:1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志 visitedw”。2.如何判别V的邻接点是否被访问？第40页，共88页，编辑于2022年，星期六void DFS(Graph G,int v)/从顶点从顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w /递归调用DFS/DFS第41页，共88页，编

19、辑于2022年，星期六 首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历非连通图的深度优先搜索遍历第42页，共88页，编辑于2022年，星期六void DFSTraverse(Graph G,Status(*Visit)(int v)/对图对图 G 作深度优先遍历。作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vw1,V-w2,V-w8 的路径长度为1；V-w7

20、,V-w3,V-w5 的路径长度为2；V-w6,V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4第45页，共88页，编辑于2022年，星期六 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访按这些顶点被访问的先后次序依次访问它们的邻接点问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。第46页，共88页，编辑于2022年，星期六 void BFSTraverse(Graph G,S

21、tatus(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vnext=Q.rear-next=NULLvoid EnQueue(LinkQueue&Q,QelemType e)p=(QueuePtr)malloc(sizeof(QNode);p-data=e;p-next=NULL;p-priou=Q.front Q.rear-next=p;Q.rear=p;void DeQueue(LinkQueue&Q,QelemType&e)Q.front=Q.front

22、-next;e=Q.front-data第57页，共88页，编辑于2022年，星期六7.4 (连通网的连通网的)最小生成树最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下如何在最节省经费的前提下建立建立这个通讯网通讯网？问题：问题：第58页，共88页，编辑于2022年，星期六 构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）第59页，共8

23、8页，编辑于2022年，星期六 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的在添加的顶点顶点 w 和已经在生成树上的顶点和已经在生成树上的顶点v 之间必定之间必定存在一条边，并且该边的权值在所有连通顶存在一条边，并且该边的权值在所有连通顶点点 v 和和 w 之间的边中取值最小之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想普里姆算法的基本思想:第60页，共88页，编辑于2022年，星期六abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+

24、8+3+5+16+21=67第61页，共88页，编辑于2022年，星期六 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通在所有连通U中顶点和中顶点和V-U中顶点的边中顶点的边中选取权值最小的边中选取权值最小的边。一般情况下所添加的顶点应满足下列条件:第62页，共88页，编辑于2022年，星期六 设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中集中的每个顶点，记录和顶点集的每个顶点，记录和顶点集U中顶点相连中顶点相连接的代价最小的边：接的代价最小的边：struct VertexType adjvex;/U集

25、中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;第63页，共88页，编辑于2022年，星期六abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c55第64页，共88页，编辑于2022年，星期六void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcs

26、kj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i)继续向生成树上添加顶点继续向生成树上添加顶点;第65页，共88页，编辑于2022年，星期六 k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.a

27、rcskj.adj;第66页，共88页，编辑于2022年，星期六具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：第67页，共88页，编辑于2022年，星期六abcdegf195141827168213ae12dcbgf7148531621例如例如:7121819第68页，共88页，编辑于2022年，星期六算法

28、描述算法描述:构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kn-1)+i;检查边集 E 中第第 i 条权值最小的边条权值最小的边(u,v);若若(u,v)加入加入ST后不使后不使ST中产生回路中产生回路，则则 输出边输出边(u,v);且且 k+;第69页，共88页，编辑于2022年，星期六普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法第70页，共88页，编辑于2022年，星期六7.7 关键路径关键路径问题问题:假设以有向网表示一个施工流图，弧上的权值表示

29、完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。第71页，共88页，编辑于2022年，星期六abcdefghk64521187244例如例如:“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。源点汇点6174第72页，共88页，编辑于2022年，星期六 如何求关键活动？如何求关键活动？“事件(顶点)”的 最早发生时间 ve(j)ve(j)=从源点到顶点j的最长路径长度；“事件(顶点)”的 最迟发生时间 vl(k)vl(k)=从顶点k

30、到汇点的最短路径长度。第73页，共88页，编辑于2022年，星期六 假设第 i 条弧为 则 对第 i 项活动言 “活动(弧)”的 最早开始时间 ee(i)ee(i)=ve(j)；“活动(弧)”的 最迟开始时间 el(i)el(i)=vl(k)dut()；第74页，共88页，编辑于2022年，星期六 事件发生时间的计算公式：ve(源点)=0；ve(k)=Maxve(j)+dut()vl(汇点)=ve(汇点)；vl(j)=Minvl(k)dut()第75页，共88页，编辑于2022年，星期六abcdefghk645211872440000000006457115 71514181818181818

31、18181818161486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-k第76页，共88页，编辑于2022年，星期六06457715 1418181416107866000064577715 1414160236688710第77页，共88页，编辑于2022年，星期六 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序；而 求vl的顺序应该是按拓扑逆序拓扑逆序的次序；因为 拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此 应该在拓扑排序的过程中，另设一个“栈栈”记下拓扑有序序列。第78页，共88页，编辑于2022年，星期六1.1.熟悉图

32、的各种存储结构及其构造算法，熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储了解实际问题的求解效率与采用何种存储结构和算法有密切联系。结构和算法有密切联系。2.2.熟练掌握图的两种搜索路径的遍历：熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。先搜索的算法。在学习中应注意图的遍历算法与树的遍在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。历算法之间的类似和差异。第79页，共88页，编辑于2022年，星期六 3.3.应用图的遍历算法求解各种简应用图的遍历算法求解各种简单路径问题。单路径问题。4.

33、4.理解教科书中讨论的各种图的理解教科书中讨论的各种图的算法。算法。第80页，共88页，编辑于2022年，星期六作业作业一、选择题一、选择题1、邻接表是图的一种_。A）顺序存储结构 B）链接存储结构C）索引存储结构 D）散列存储结构2、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中_。A）第i行非的元素之和 B）第i列非的元素之和C）第i行非且非0的元素个数 D）第i列非且非0的元素个数第81页，共88页，编辑于2022年，星期六3、在一个无向图中，所有顶点的度之和等于边数的_倍。A）1/2 B）1 C）2 D）44、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A）1

34、/2 B）1 C）2 D）45、采用邻接表存储的图的深度优先遍历算法类似于二叉树的_算法。A）前序遍历 B）中序遍历 C）后序遍历 D）按层遍历第82页，共88页，编辑于2022年，星期六6、任何一个无向连通图_最小生成树。A）只有一棵 B）有一棵或多棵C）一定有多棵 D）可能不存在7、下列说法不正确的是_A）图的遍历过程中每一顶点仅被访问一次B）遍历图的基本方法有深度优先搜索和广度优先搜索两种C）图的深度优先搜索的方法不适用于有向图D）图的深度优先搜索是一个递归过程第83页，共88页，编辑于2022年，星期六8、具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A）5 B）6 C）7

35、D）89、在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。A）n B）n1 C）n1 D）n/210、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是_。A）n B）(n-1)2 C）n1 D）n2第84页，共88页，编辑于2022年，星期六二、填空题二、填空题1 1、有、有、有、有n n个顶点个顶点个顶点个顶点e e条边的无向图，采用邻接表存储时，有条边的无向图，采用邻接表存储时，有条边的无向图，采用邻接表存储时，有条边的无向图，采用邻接表存储时，有_个表头结点，有个表头结点，有个表头结点，有个表头结点，有_个链表结点。个链表结点。个链表结点。个链表结点。2 2、

36、对于由、对于由、对于由、对于由n n个顶点组成的有向完全图来说，图中共包含个顶点组成的有向完全图来说，图中共包含个顶点组成的有向完全图来说，图中共包含个顶点组成的有向完全图来说，图中共包含_条边，对于由条边，对于由条边，对于由条边，对于由n n个顶点组成的无向完全图来说，图中共包含个顶点组成的无向完全图来说，图中共包含个顶点组成的无向完全图来说，图中共包含个顶点组成的无向完全图来说，图中共包含_条边。条边。条边。条边。3 3、在一个、在一个、在一个、在一个_图中寻找拓扑序列的过程称为图中寻找拓扑序列的过程称为图中寻找拓扑序列的过程称为图中寻找拓扑序列的过程称为_4 4、一个图的、一个图的、一个

37、图的、一个图的_表示法是唯一的，而表示法是唯一的，而表示法是唯一的，而表示法是唯一的，而_表示法是不唯一的。表示法是不唯一的。表示法是不唯一的。表示法是不唯一的。5 5、用邻接矩阵、用邻接矩阵、用邻接矩阵、用邻接矩阵A1.nA1.n，1.n1.n存储有向图存储有向图存储有向图存储有向图GG，其第，其第，其第，其第i i行的所有元素之和等于顶点行的所有元素之和等于顶点行的所有元素之和等于顶点行的所有元素之和等于顶点i i的的的的_。6 6、有、有、有、有n n个顶点的有向图个顶点的有向图个顶点的有向图个顶点的有向图GG最多有最多有最多有最多有_条弧。条弧。条弧。条弧。7 7、n n个顶点的连通图

38、至少有个顶点的连通图至少有个顶点的连通图至少有个顶点的连通图至少有_条边。条边。条边。条边。第85页，共88页，编辑于2022年，星期六三、综合题三、综合题1、在下图所示的各无向图中：（1）找出所有的简单环。（2）找出哪些图是连通图？对非连通图给出其连通分量。（3）哪些图是自由树（或森林）？123123412341234(a)(b)(c)(d)第86页，共88页，编辑于2022年，星期六2.已知AOE网有9个结点：V1V2V3V4V5V6V7V8V9，其邻接矩阵如图所示。（1）请画出该AOE图。（2）计算完成整个计划需要的时间。（3）求出该AOE网的关键路径。第87页，共88页，编辑于2022年，星期六第88页，共88页，编辑于2022年，星期六