【数据结构】——图的相关习题

一、选择填空判断题

题型一（有向图与无向图）

1、具有n个顶点的有向完全图有（）条弧边。
A、n（n-1）/2
B、n（n-1）
C、n（n+1）/2
D、n（n+1）

解析：（B）
若一个有向图中，若每个顶点都有互相相反的两条弧连接，则称为有向完全图，在一个含有n个顶点的有向完全图中，共有n(n-1)条弧。

例如，含有4个顶点的有向完全图中，共有n(n-1)=4×3=12条弧，如下：

2、在一个无向图中，所有顶点的度等于所有边数的（）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A、1/2
B、2
C、1
D、4

解析：（B）（C）
在一个无向图中，所有顶点的度之和等于所有边数的两倍。
例如，对于下面这个图，其顶点度之和为2+3+3+2=10，该图边的个数为5，故10=2×5。

在有向图中，对于一个顶点，该结点的度等于顶点的入度+顶点的出度，该结点的弧头数目称为入度，记为ID(v)；结点的弧尾数目称为出度，记为OD(v)，即TD(v)=ID(v)+OD(v)。

对于一个含有n个顶点有向图，每个顶点的度最大可达2(n-1)，另外所有顶点的入度之和等于所有顶点出度之和。
例如，下面这个有向图，其所有的顶点的入度之和为2+0+2+1=5，所有的顶点出度之和为0+3+1+1=5，它们是相等的：

3、一个有28条边的非连通无向图至少有（）个顶点。
A、7
B、8
C、9
D、10

解析：（C）
若一个含有n个顶点的无向连通图，构成一棵树时图中边数最少，有n-1条边；当为无向完全图时，图的边数最多，即n(n-1)/2条边。

考虑为由一个含有n个顶点的无向完全图和一个单独的顶点构成非连通无向图，无向完全图中共n(n-1)/2条边，n(n-1)/2=28，
即为n=8最大边数，这样结点数最少，再加上单独的一个顶点，即构成非连通无向图，故至少有8+1=9个顶点。

题型二（深度/广度优先遍历）

1、若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（）。
A、强连通图
B、连通图
C、有回路
D、一棵树

解析：（B）
在一个有向图中，任意两个不同的顶点都存在相互之间的路径，则称为强连通图，与题意无向图不符。若无向图中任意两个结点都是连通的（任意两个结点之间有路径），则称该图为连通图，由于从任意顶点出发进行一次深度优先搜索即可访问所有的顶点，所以该图一定是连通图；回路不一定包含图的所有顶点；连通图可能是树，也可能存在环。

2、无向图G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，c），（a，e），（b，e），（c，f），（f，d），（e，d）}，以顶点a为源点对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A、a，b，e，c，d，f
B、a，c，f，e，b，d
C、a，e，b，c，f，d
D、a，e，d，f，c，b

解析：（D）
如下可画出该无向图：

图的深度优先搜索（DFS）【类似树的先序遍历，先访问结点，然后递归向外层结点遍历，尽可能深地搜索一个图，都采用回溯算法】。
DFS算法是一个递归过程，其中需借助栈完成操作。首先选取图中某一顶点vi，访问后，任意选取一个与vi邻接的顶点，且该顶点未被访问，……，继续重复该过程，直到图中所有与vi连通的顶点都被访问到；若还有顶点未被访问到，则另外选取一个未被访问的顶点再次作为起始点，重复以上步骤，继续直至图中所有结点被访问。

以顶点a为源点对该图进行深度优先遍历，然后选择与a邻接的任一顶点，由于与a邻接的顶点有b，c，e，可有以下三种访问序列{a，b，……}或{a，c，……}或{a，e，……}，

然后，选择访问顶点d，也可以选择还未被访问的顶点。由于先前选择访问的序列是{a，d}，此时访问与顶点d相邻的顶点f，得到序列{a，d，f}；再访问与顶点f相邻的顶点c，得到序列{a，d，f，c}；由于此时与c邻接的顶点a和f都被访问过，回退到f，继续检查d，与d邻接的顶点也被访问过，……，最后直到顶点d还未被访问，访问它，可得到序列{a，e，d，f，c，b}。

3、如下所示的图进行从顶点1开始的广度优先搜索遍历，可得到的顶点访问序列为（）。
A、1，3，2，4，5，6，7
B、1，2，4，3，5，6，7
C、1，2，3，4，5，7，6
D、2，5，1，4，7，3，6

解析：（A）
图的广度优先搜索（BFS）【类似树的层序遍历，一层一层向外遍历】。
首先选取一个起始点顶点vi，访问后将其入队并标记为已访问（使用队列用于避免重复访问，存放已经访问过的各邻接顶点）；当队列不为空时检查出队顶点的所有邻接顶点，访问未被访问的邻接顶点并将其入队，……，继续重复该过程，直到图中所有与vi连通的顶点都被访问到；当队列为空时跳出循环，则此时遍历完成。

以顶点1为源点对该图进行广度优先遍历，选择与其邻接的所有顶点进行访问，有2和3，可得序列{1，2，3，……}或{1，3，2，……}；例如，先选择访问顶点3，再访问顶点2，再访问顶点2或顶点3的邻接顶点4，接着访问顶点4的邻接顶点5和6，最后访问顶点7，从而得到序列{1，3，2，4，5，6，7}。

题型三（邻接矩阵和邻接表）

1、一个具有n个顶点，e条边的无向图的邻接矩阵中，零元素的个数为（）。
A、n²
B、n²-2e
C、n+2e
D、e

解析：（B）
无向图的邻接矩阵一定是对称矩阵，关于对角线对称，且主对角线一定为零（只针对简单图），而无向完全图中，由于任意两个顶点之间都有边连接，所以除了邻接矩阵的主对角线外，其余元素都为1。对于一个含有n个顶点，e条边的无向图，其邻接矩阵中元素为零的个数为n²-2e。

有向图的邻接矩阵不一定是对称矩阵；另外，若一个图的邻接矩阵是对称的，则它可以是无向图或有向图。

2、（填空）若无向图采用邻接矩阵存储，则存储空间的大小只与图中______的个数有关；若采用邻接表存储，其空间大小与图中______的个数有关。

解析：顶点；顶点、边
邻接矩阵通过一个一维数组存储顶点，一个二维数组存储顶点之间的相邻关系，一个顶点数为n的图的邻接矩阵是n×n（n行n列），即一个方阵，用邻接矩阵方法来表示一个图需要n²个存储空间，它只与图中的顶点数有关，其空间复杂度为O(n²)。

邻接表方法采用顺序存储结构和链式存储结构来存储图，对于图中每个顶点v_i，将所有邻接于v_i的顶点连成一个单链表，即这个单链表就称为顶点v_i的邻接表，另外还需将所有顶点的邻接表放进数组中，通过邻接表存储图所用的空间大小取决于图的顶点数和边的个数，顶点数n决定了顶点表的空间大小，边的个数决定了边表结点的空间大小。

题型四（十字链表和邻接多重表）

1、十字链表是和邻接多重表分别是（）的存储结构。
A、有向图、无向图
B、无向图、有向图
C、无向图、无向图
D、有向图、有向图

解析：（A）
（1）十字链表是一种链式存储结构，用于表示有向图，data域用于存储顶点的信息，firstin和firstout域分别指向以该顶点弧头或弧尾的第一个弧结点，顶点表的结构如下：

（2）邻接多重表是一种链式存储结构，用于表示无向图，邻接多重表也是由顶点表和边表组成，每个顶点由两个域组成，data域用于存储顶点的信息，firstedge域用于指向第一条与其邻接的边，顶点表的结构如下：

题型五（拓扑排序）

1、已知有向图G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E={<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>}，则G的拓扑序列是（）。
A、V1，V3，V4，V6，V2，V5，V7
B、V1，V3，V2，V6，V4，V5，V7
C、V1，V3，V4，V5，V2，V6，V7
D、V1，V2，V5，V3，V4，V6，V7

解析：（A）
根据E序列可以画出如下图：

对于一个AOV网进行拓扑排序的步骤如下：
1、从网中找选择一个没有前驱，即入度ID(v)=0的顶点；
2、删除该顶点且删除由该顶点的所有起始边（出度的边），并将该顶点输出当前拓扑排序；
3、重复(1)和(2)步骤，直至AOV网为空或不存在没有前驱的结点为止；
4、最后得到一个序列，即拓扑排序（AOV网的拓扑排序的序列不止一个）。

该图，是从V1开始进行拓扑排序，
删除顶点V1且删除由该顶点的所有起始边，即<V1，V2>，<V1，V3>，<V1，V4>，如下：

并将该顶点输出当前拓扑排序，{V1}。
从网中找选择一个没有前驱，即入度ID(v)=0的顶点，此时可以选择V2或V3或V4：

根据题中选项，拓扑序列中第二个为V2或V3，若以V2继续重复步骤，删除顶点V2且删除由该顶点的所有起始边后的下一个顶点应该是V3或V4（此时没有前驱的顶点只有V3或V4），所以D选项错误。
若以V3继续重复步骤，删除顶点V3且删除由该顶点的所有起始边，如下：

并将该顶点输出当前拓扑排序，{V1，V3}。
从网中找选择一个没有前驱，即入度ID(v)=0的顶点，此时可以选择V2或V4：

若此时选择V2继续进行，则下一个顶点应该是V4或V5，此时拓扑序列应该为{V1，V3，V2，V4/V5，…}，所以B选项错误。
若选择V4继续，则下一个顶点应该是V2或V6，A选项中是首先选择V6，继续如下：

并将该顶点输出当前拓扑排序，{V1，V3，V4，V6}。
选择V6继续，则下一个顶点应该是V2，并将该顶点输出当前拓扑排序，{V1，V3，V4，V6，V2}。

下一个顶点只能是V5，然后是V7，最终所有顶点都访问完成，得到的拓扑序列为{V1，V3，V4，V6，V2，V5，V7}，A选项正确。

2、下图所示的有向图中所有的拓扑序列共有（）个。
A、4
B、6
C、5
D、7

解析：（C）
可知有以下拓扑序列：
{V1，V2，V3，V6，V4，V5，V7}；
{V1，V2，V3，V4，V6，V5，V7}；
{V1，V2，V3，V4，V5，V6，V7}；
{V1，V2，V4，V3，V6，V5，V7}；
{V1，V2，V4，V3，V5，V6，V7}。

题型六（关键路径）

1、（多选）下面关于关键路径的说法正确的是（）。
A、求关键路径是以拓扑排序为基础的
B、关键活动一定位于关键路径上
C、一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同
D、一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差

解析：（A、B、C）
在AOE网中，由源点到汇点的有向路径可能有多条，从而完成活动的路径长度也不同，将所有路径中具有最大路径长度的路径称为关键路径，且这条路径上的所有活动称为关键活动，是决定整个工程的关键因素，关键路径是整个工程所完成的最短时间。

一个事件的最迟发生时间为vl(k)=min{vl(j)-weight(v_k,v_j)}，其中v_k为v_j的任意前驱，即等于取【以该事件为尾的弧的活动的最迟开始时间】与【最迟结束时间与该活动的持续时间的差】的最小值。

2、（多选）下面的（）方法可以判断出一个有向图是否有环（回路）。
A、深度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径

解析：（A、B、D）
图的深度优先搜索（DFS），类似树的先序遍历，先访问结点，然后递归向外层结点遍历，尽可能深地搜索一个图，在生成树中访问到的顶点会是起始顶点的子孙，所以可以判断是否有环。

拓扑排序中是选择一个没有前驱，即入度ID(v)=0的顶点进行下去，而存在环时环的顶点是某边的起始，从而无法加入拓扑序列，无法找到下一个顶点删除时即可以判断是否有环。

二、应用题

题型一（深度/广度优先遍历）

根据图的存储结构，求出图的深度/广度优先遍历序列

1、设一个图以邻接表存储，如下图所示。边结点的第一个数据为边的终点下标，第二个数据为边的权值，第三个数据为指向下一个边结点的指针，写出从顶点A开始的深度和广度优先遍历序列。

解：进行深度优先遍历的步骤如下：
1、首先访问0，即A，访问后标记已访问过，此时深度优先遍历序列为{A}；
2、查看A单链表，第一个未访问的邻接顶点为1，即顶点B，并以B为出发点继续深度遍历，此时深度优先遍历序列为{A，B}；
3、查看B单链表，0对应的顶点A已经访问，所以第一个未访问的邻接顶点为2，即顶点C，并以C为出发点继续深度遍历，此时深度优先遍历序列为{A，B，C}；
4、查看C单链表，0对应的顶点A已经访问，1对应的顶点B也访问过，所以第一个未访问的邻接顶点为3，即顶点D，并以D为出发点继续深度遍历，此时深度优先遍历序列为{A，B，C，D}；
5、查看D单链表，0对应的顶点A已经访问，2对应的顶点C也访问过，所以第一个未访问的邻接顶点为5，即顶点F，并以F为出发点继续深度遍历，此时深度优先遍历序列为{A，B，C，D，F}；
6、查看F单链表，1对应的顶点B访问过，2对应的顶点C也访问过，3对应的顶点D也访问过，所以第一个未访问的邻接顶点为4，即顶点E，此时深度优先遍历序列为{A，B，C，D，F，E}，由于所有的顶点都被访问到，深度遍历结束。

进行广度优先遍历的步骤如下：
1、首先访问0，即A，访问后标记已访问过，使其入队，然后删除当前队头结点，此时广度优先遍历序列为{A}；
2、遍历单链表0，将单链表中的1、2、3对应的顶点B、C、D入队且访问，此时广度优先遍历序列为{A，B，C，D}；
3、遍历单链表1，将单链表中未访问的加入队中，4、5对应的顶点E、F入队且访问，此时广度优先遍历序列为{A，B，C，D，E，F}，由于所有的顶点都被访问到，广度优先遍历结束。

题型二（邻接矩阵和邻接表）

根据图，画出图的邻接矩阵和邻接表

1、画出下面的带权无向图的邻接矩阵。

解：对于带权图，设图G=(V，E)，若顶点是E(G)中的边，则用其边的权值标记；若顶点不是E(G)中的边，则用∞标记，记为A[i][j]=∞，如下：

2、已知带权有向图G=（V,E），其中V（G）={A，B，C，D，E}，用<U，V，W>表示弧<U，V>及权值W，E（G）={<A，B，10>，<A，C，100>，<A，E，30>，<B，D，50>，<B，E，5>，<D，C，15>，<E，C，25>，<E，D，20>}，画出其邻接表。

解：可以画出该带权有向图：

其邻接表如下：

题型三（深度/广度优先生成树）

根据图的邻接表存储结构，画出图以及图的深度/广度优先生成树

1、设G=（V，E）以邻接表存储，如下图所示，画出该图的深度优先生成树和广度优先生成树。

解：由该邻接表可知，顶点1与2，3，4邻接，顶点2与1，3，4，5邻接，顶点3与1，2，4邻接，顶点4与1，2，3，5邻接，顶点5与2，4邻接，画出该图：

图的深度优先遍历序列步骤：
1、首先访问顶点1，访问后标记已访问过，此时序列为{1}；
2、查看单链表1，其第一个未访问的邻接顶点为2，再以顶点2为出发点继续深度遍历，此时序列为{1，2}；
3、查看单链表2，顶点1已经访问过，所以其未访问的邻接顶点为3，再以顶点3为出发点继续深度遍历，此时序列为{1，2，3}；
4、查看单链表3，顶点1和顶点2已经访问过，所以其未访问的邻接顶点为4，再以顶点4为出发点继续深度遍历，此时序列为{1，2，3，4}；
5、查看单链表4，顶点1、顶点2、顶点3已经访问过，所以其未访问的邻接顶点为5，再以顶点5为出发点继续深度遍历，此时序列为{1，2，3，4，5}，由于所有的顶点都被访问到，深度优先遍历结束。

图的广度优先遍历序列步骤：
1、首先访问顶点1，访问后标记已访问过，使其入队，然后删除当前队头结点，此时序列为{1}；
2、遍历单链表1，使其未访问的邻接顶点2、3、4入队并标记，此时序列为{1，2，3，4}；
3、遍历单链表2，使其未访问的邻接顶点5入队并标记，此时序列为{1，2，3，4，5}，由于所有的顶点都被访问到，广度优先遍历结束。

对一个连通图或非连通图进行DFS遍历后，若将在遍历过程中所经历过的顶点保留，则可以形成一棵树或森林，即深度优先生成树或深度优先生成森林；另外，基于邻接表存储的深度优先生成树或深度优先生成森林也是不唯一的；而对于邻接矩阵则是唯一的。
深度优先生成树：

对一个连通图或非连通图进行DFS遍历后，若将在遍历过程中所经历过的顶点保留，则可以形成一棵树或森林，即深度优先生成树或深度优先生成森林；另外，基于邻接表存储的深度优先生成树或深度优先生成森林也是不唯一的；而对于邻接矩阵则是唯一的。
广度优先生成树：

题型四（拓扑排序）

根据图，写出其拓扑排序

1、给出有向图的所有拓扑序列。

解：以1开始：{1，2，3，6，4，6}
以2开始：{2，1，3，5，4，6}
{2，3，1，5，4，6}

题型五（广度优先搜索算法最短路径）

根据所给图，通过广度优先搜索算法求图中一个顶点到另一个顶点的最短路径

1、下图所示是一个带权有向图，求：
（1）以顶点V1为起点的广度优先生成顶点序列及对应的生成树；
（2）以顶点V1为起点的深度优先生成生成树；
（3）由顶点V1到顶点V3的最短路径。

解：（1）由图可知，由顶点V1开始的广度优先遍历序列为：
首先遍历V1，得到的遍历序列为{V1}，
与V1出发的顶点有V2、V4、V6，所以序列为{V1，V2，V4，V6}，
{V1，V2，V4，V6，V3}
{V1，V2，V4，V6，V3，V5}。

对一个连通图或非连通图进行BFS遍历后，若将在遍历过程中所经历过的顶点保留，则可以形成一棵树或森林，即广度优先生成树或广度优先生成森林。
其广度优先生成生成树如下：

（2）由顶点V1开始的深度优先遍历序列为：
{V1，V2，V3，V4，V5，V6}。
其深度优先生成生成树如下：

（3）由从V1开始的广度优先遍历序列为{V1，V2，V4，V6，V3，V5}。访问V2、V4和V6，再访问与这些顶点邻接的顶点，由于V2与V3邻接，此时路径长度V1——V2——V3，长度为33+36=69；由于V4与V2、V3、V5邻接，若选择经过V4，则得到路径V1——V4——V3，路径长度29+38=67；通过对比，可知最短路径为V1——V4——V3。

题型六（Dijkstra 单源最短路径）

根据所给图，通过Dijkstra算法求图中一个顶点到另一个顶点的最短路径

1、通过迪杰斯特拉算法求出下图顶点1到其他顶点的最短路径。

（1）首先可以绘制如下的表格，表格左边从1开始，表格上方即除了起始点剩下的顶点：

每个DST下面为起始点（顶点1）到该顶点的权值，该权值会一直叠加，若该顶点与所选顶点非邻接，则用∞表示。

（2）由于起始点1与顶点2、顶点5邻接，权值分别为30、10，而其余顶点非邻接，如下表：

每一次所选顶点都选择当前顶点到下一个顶点的最小权值。

（3）此时由顶点1到下一个顶点的选择项有顶点2、顶点4、顶点5，其中权值10<30<60，所以下一个所选顶点为顶点5。并确定最短路径的集合以及未确定的剩下顶点集合，另外，若从顶点1到该顶点有路径，也需要加上前面经过顶点的权值，则进行更新其DIST，若无路径则仍然为上个DIST。

可知，经过顶点5出发的下一个顶点有顶点2、顶点6，即顶点1→顶点5→顶点2的权值为10+15=25，顶点1→顶点5→顶点6的权值为10+7=17，其余顶点的DIST仍然为上个DIST，填入表中：

（4）此时由顶点5到下一个顶点的选择项有顶点2、顶点6，其中权值7<15，所以下一个所选顶点为顶点6。并确定最短路径的集合以及未确定的剩下顶点集合。

可知，经过顶点6出发的下一个顶点有顶点2、顶点3、顶点7，即顶点1→顶点5→顶点6→顶点2的权值为10+7+3=20，顶点1→顶点5→顶点6→顶点3的权值为10+7+16=33，顶点1→顶点5→顶点6→顶点7的权值为10+7+8=25，其余顶点的DIST仍然为上个DIST。

另外，由于此时到顶点5已经没有路径，且已为最小值，可以确定顶点1到顶点5的最短路径为顶点1→顶点5，权值为10。

（5）此时由顶点6到下一个顶点的选择项有顶点2、顶点3、顶点7，其中权值3<8<16，所以下一个所选顶点为顶点2。并确定最短路径的集合以及未确定的剩下顶点集合。

此时可以确定顶点2和顶点6的最短路径，由于到顶点6已经没有路径，且已为最小值，可以确定顶点1到顶点6的最短路径为顶点1→顶点5→顶点6，权值为17；由于到顶点2已经没有路径，且已为最小值，可以确定顶点1到顶点2的最短路径为顶点1→顶点5→顶点6→顶点2，权值为20，如下表：

（6）由于一个分支顶点2已经确定了，确定下一个分支，8<16，所以下一个所选顶点为顶点7。并确定最短路径的集合以及未确定的剩下顶点集合。

起始顶点到顶点3、顶点4、顶点8的权值更新为31、28、35，此时可以确定顶点7最短路径，由于到顶点7已经没有路径，且已为最小值，可以确定顶点1到顶点7的最短路径为顶点1→顶点5→顶点6→顶点7，权值为25，如下表：

（7）与顶点7邻接的顶点有顶点3、顶点4、顶点8，此时3<6<10，所以下一个所选顶点为顶点4，由于到顶点4已经没有路径，且已为最小值，可以确定顶点1到顶点4的最短路径为顶点1→顶点5→顶点6→顶点7→顶点4，权值为28，如下表：

（8）由于6<10，选择顶点3，此时由于到顶点3已经没有路径，且已为最小值，可以确定顶点1到顶点4的最短路径为顶点1→顶点5→顶点6→顶点7→顶点3，权值为31，如下表：

（9）最后选择顶点8，可以确定顶点1到顶点8的最短路径为顶点1→顶点5→顶点6→顶点7→顶点8，权值为35，如下表：

题型七（关键路径）

根据所给图，求一个顶点到另一个顶点的的关键路径

1、设AOE网的事件集为V={V1,V2,V3,V4,V5,V6,V7},用(Vi,Vj,w)表示活动,其中Vi,Vj分别表示第i和第j个事件,w表示从Vi到Vj的持续时间,活动集为E={(V1,V2,10),(V1,V3,8),(V1,V4,20),(V2,V4,5),(V3,V4,7),(V3,V5,20),(V4,V6,6),(V5,V6,9),(V5,V7,2),(V6,V7,2)}。
（1）画出它的邻接表（表结点按顶点编号递减序排列）；
（2）写出每个活动的最早开始时间和最迟开始时间；
（3）写出从V1到V7的所有关键路径。

解：（1）该AOE网如下：

其邻接表如下：
（2）①由图可以求得该图的拓扑有序序列和逆拓扑有序序列，
拓扑有序序列和逆拓扑有序序列分别为{V1，V2，V3，V4，V5，V6，V7}，{V7，V6，V5，V4，V3，V2，V1}。

②设ve(V)为顶点V代表的事件的最早发生时间，依照拓扑序列的先后顺序求各顶点所对应事件的最早发生时间。
【正向，初值为0，取权值最大为事件的最早发生时间】
设事件1的开始时间为0，即ve(V1)=0；
根据拓扑排序继续求V2，V3，V4，可得：
ve(V2)=ve(V1)+10=10；
ve(V3)=ve(V1)+8=8；
其中V4较特殊，由于到V4的路径有三条，分别是V1→V2→V4、V1→V3→V4、V1→V4，
要取其中权值最大者，也就是最早发生时间，取V1→V4，ve(V4)=ve(V1)+20=20；

继续求其它事件的最早发生时间：
ve(V5)=ve(V3)+20=28；
由于到V6的路径有四条，分别是V1→V4→V6、V1→V2→V4→V6、V1→V3→V4→V6、V1→V3→V5→V6，
要取其中权值最大者，也就是最早发生时间，取V1→V3→V5→V6，ve(V6)=ve(V5)+9=37；
由于到V6的路径有五条，分别是V1→V4→V6→V7、V1→V2→V4→V6→V7、V1→V3→V4→V6→V7、V1→V3→V5→V6→V7、V1→V3→V5→V7，
要取其中权值最大者，也就是最早发生时间，取V1→V3→V5→V6→V7，ve(V7)=ve(V6)+2=39。

③设vl(V)为顶点V代表的事件的最迟发生时间，最迟发生时间是在不推迟整个工程完成的前提下，该事件最迟必须发生的时间，依照逆拓扑序列的先后顺序求各顶点所对应事件的最迟发生时间，且由事件的最早发生时间。
【逆回，初值为最值，取权值最小为事件的最迟发生时间】
设vl(V7)=ve(V7)=39，按照逆拓扑序列依次：
vl(V6)=vl(V7)-2=39-2=37；
由于回V5的路径有两条，分别是V5←V7和V5←V6，要取其中权值最小者，也就是最迟发生时间，应该取V5←V6，所以vl(V5)=vl(V6)-9=37-9=28；
vl(V4)=vl(V6)-6=37-6=31；
由于回V3的路径有三条，分别是V3←V4、V3←V5，要取其中权值最小者，也就是最迟发生时间，应该取V3←V5，所以vl(V3)=vl(V5)-20=28-20=8；
vl(V2)=vl(V4)-5=31-5=26；
由于回V1的路径有三条，分别是V1←V4、V1←V3，V1←V2，要取其中权值最小者，也就是最迟发生时间，应该取V1←V3，所以vl(V1)=vl(V3)-8=8-8=0。

④为图中的活动进行编号，如下图：

求每个活动的最早发生时间，设e(a)为当前活动i的最早发生时间，由于事件代表一个新活动的开始或旧活动的结束，所以活动的最早发生时间等于该弧的起点的顶点的ve()。
【弧上起点最早发生时间为活动的最早发生时间】
活动a1的最早发生时间等于活动a1的起点的顶点的ve()，等于V1→V2这条弧的起点的顶点的ve()，即顶点V1的ve()，e(a1)=ve(V1)=0；
活动a2的最早发生时间等于活动a2的起点的顶点的ve()，等于V1→V4这条弧的起点的顶点的ve()，即顶点V1的ve()，e(a2)=ve(V1)=0；
活动a3的最早发生时间等于活动a3的起点的顶点的ve()，等于V1→V3这条弧的起点的顶点的ve()，即顶点V1的ve()，e(a3)=ve(V1)=0；
活动a4的最早发生时间等于活动a4的起点的顶点的ve()，等于V2→V4这条弧的起点的顶点的ve()，即顶点V2的ve()，e(a4)=ve(V2)=10；
活动a5的最早发生时间等于活动a5的起点的顶点的ve()，等于V3→V4这条弧的起点的顶点的ve()，即顶点V3的ve()，e(a5)=ve(V3)=8；
活动a6的最早发生时间等于活动a6的起点的顶点的ve()，等于V3→V5这条弧的起点的顶点的ve()，即顶点V3的ve()，e(a6)=ve(V3)=8；
活动a7的最早发生时间等于活动a7的起点的顶点的ve()，等于V4→V6这条弧的起点的顶点的ve()，即顶点V4的ve()，e(a7)=ve(V4)=20；
活动a8的最早发生时间等于活动a8的起点的顶点的ve()，等于V5→V6这条弧的起点的顶点的ve()，即顶点V5的ve()，e(a3)=ve(V5)=28；
活动a9的最早发生时间等于活动a9的起点的顶点的ve()，等于V5→V7这条弧的起点的顶点的ve()，即顶点V5的ve()，e(a9)=ve(V5)=28；
活动a10的最早发生时间等于活动a10的起点的顶点的ve()，等于V6→V7这条弧的起点的顶点的ve()，即顶点V6的ve()，e(a10)=ve(V6)=37。

⑤求每个活动的最迟发生时间，设l(a)为当前活动i的最迟发生时间，活动的最迟发生时间是事件的最迟发生时间减去以它为结束点的活动的持续时间。
【弧上终点最迟发生时间减去弧上权值为活动的最迟发生时间】
活动a1的最迟发生时间等于该弧的终点的顶点的vl()减去该弧上的持续时间（权值），活动a1对应V1→V2，即V2的vl(V2)-a1，l(a1)=vl(V2)-10=26-10=16；
活动a2，对应V1→V4，所以V4的最迟发生时间减去a2，即vl(V4)-a2，l(a2)=vl(V4)-20=31-20=11；
活动a3，对应V1→V3，所以V3的最迟发生时间减去a3，即vl(V3)-a3，l(a3)=vl(V3)-8=8-8=0；
活动a4，对应V2→V4，所以V4的最迟发生时间减去a4，即vl(V4)-a4，l(a4)=vl(V4)-5=31-5=26；
活动a5，对应V3→V4，所以V4的最迟发生时间减去a5，即vl(V4)-a5，l(a5)=vl(V4)-7=31-7=24；
活动a6，对应V3→V5，所以V5的最迟发生时间减去a6，即vl(V5)-a6，l(a6)=vl(V5)-20=28-20=8；
活动a7，对应V4→V6，所以V6的最迟发生时间减去a7，即vl(V6)-a7，l(a7)=vl(V6)-6=37-6=31；
活动a8，对应V5→V6，所以V6的最迟发生时间减去a8，即vl(V6)-a8，l(a8)=vl(V6)-9=37-9=28；
活动a9，对应V5→V7，所以V7的最迟发生时间减去a9，即vl(V7)-a9，l(a9)=vl(V7)-2=39-2=37；
活动a10，对应V6→V7，所以V7的最迟发生时间减去a10，即vl(V7)-a10，l(a10)=vl(V7)-2=39-2=37。

故每个活动的最早开始时间和最迟开始时间如下表：

（3）若一个活动的时间余量为0，则说明该活动必须要如期完成，否则会拖延整个工程的进度，所以l(a)-e(a)=0，即l(a)=e(a)的活动ai是关键活动，从而得到关键路径。

根据表中可得，所以V1到V7的所有关键路径为（V1，V3），（V3，V5），（V5，V6），（V6，V7)。

2、对下图求出其关键路径，写出求解过程。

解：①由图可以求得该图的拓扑有序序列和逆拓扑有序序列，
拓扑有序序列和逆拓扑有序序列分别为{V0，V1，V2，V3，V4，V5，V6，V7}，{V7，V6，V5，V4，V3，V2，V1，V0}。

②设ve(V)为顶点V代表的事件的最早发生时间，依照拓扑序列的先后顺序求各顶点所对应事件的最早发生时间。
ve(V0)=0；
ve(V1)=ve(V0)+6=0+6=6；
ve(V2)=ve(V0)+3=0+3=3；
ve(V3)=ve(V0)+8=0+8=8；
到V4有两条路径，取其中权值最大者，所以，ve(V4)=ve(V1)+10=6+10=16；
ve(V5)=ve(V4)+9=16+9=25；
到V6有三条路径，取其中权值最大者，所以，
ve(V6)=ve(V4)+6=16+6=22；
到V7有五条路径，取其中权值最大者，所以，
ve(V7)=ve(V6)+8=22+8=30。

③设vl(V)为顶点V代表的事件的最迟发生时间，最迟发生时间是在不推迟整个工程完成的前提下，该事件最迟必须发生的时间，依照逆拓扑序列的先后顺序求各顶点所对应事件的最迟发生时间，且由事件的最早发生时间。
vl(V7)=ve(V7)=30；
V6→V7，所以vl(V6)=ve(V7)-8=30-8=22；
V5→V7，所以vl(V5)=ve(V7)-2=30-2=28；
V4出发有两条路径，V4→V5、V4→V6，取其中权值最小者，
所以vl(V4)=vl(V6)-6=22-6=16；
vl(V3)=vl(V6)-2=22-2=20；
vl(V2)=vl(V4)-10=16-10=6；
vl(V1)=vl(V4)-10=16-10=6；
V0出发有三条路径，V0→V1、V0→V2、V0→V3，取其中权值最小者，
所以vl(V0)=vl(V1)-6=6-6=0。

最早发生时间和最迟发生时间相同的活动就是关键路径，
即图中的关键路径为V0→V1→V4→V6→V7。文章来源地址https://www.toymoban.com/news/detail-753313.html

到了这里，关于【数据结构】——图的相关习题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！