$$已更完$$

github中有详尽代码可作参考

返回目录

最小生成树

对于一个带权连通无向图 $G=(V,E)$,生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同,设 $\Re$为 $G$的所有生成树的集合,若 $T$为 $\Re$中边的权值之和最小的那棵生成树，则 $T$称为 $G$的最小生成树( $MST$).

最小生成树的性质：

• 最小生成树不是唯一的,即最小生成树的树形不唯一, $\Re$中可能有多个最小生成树.当图 $G$中各边权值互不相同时, $G$的最小生成树是唯一的;若无向连通图 $G$的边数比顶点数少 $1$,即 $G$本身是一棵树时,则 $G$的最小生成树就是它本身.
• 最小生成树的边的权值之和总是唯一的,虽然最小生成树不唯一,但其对应的边的权值之和总是唯一的且是最小的.
• 最小生成树的边数为顶点数减 $1$.

Prim算法

该算法的时间复杂度为 $O(\left| V \right|^2)$,不依赖于 $\left| E \right|$,它可通过使用优先队列把时间复杂度优化为 $O(\left| E\right| \log_{2}{\left| V \right|})$,它适用于求解边稠密的图.

该算法可以称为加点法,每次迭代选择代价最小的边对应的点,将满足条件的加入到最小生成树中.算法从某个顶点 $s$出发,逐渐覆盖整个连通网的所有顶点.

1. 图的所有顶点集合为 $V$,初始令顶点的集合 u={s},剩余的顶点集合 $v=V-u$;
2. 在两个集合 $u,v$能够组成的边中,选择一条代价最小的边 $e=(u_0,v_0)$,并把这条边加入到最小生成树中,把 $v_0$加入到集合 $u$中;
3. 重复上述步骤,直到最小生成树有 $n-1$条边或者有 $n$个顶点为止.

Kruskal算法

该算法的时间复杂度为 $O(\left| E \right| \log_{2} \left| E \right|)$,适用于边稀疏而顶点较多的图.

该算法可以称为 加边法 ,初始化最小生成树边数为 $0$,每迭代一次选择一条满足条件的最小代价边,加入到最小生成树的边集合中.

1. 把图中的所有边按代价从小到大排序;
2. 把图中的 $n$个顶点看成独立的 $n$棵树组成的森林;
3. 按权值从小到大选择边,所选的边连接的两个顶点 $u_i,v_i$属于两棵不同的树,使之成为最小生成树的一条边,并将这两棵树合并作为一棵树(此处用到并查集);
4. 重复 $(3)$,直到所有顶点都在同一棵树上或者有 $n-1$条边为止.

最短路径

从图中某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径.

单源最短路径问题(Single Source Shortest Path, $SSSP$问题),给定一张有向图 $G=(V,E)$, $V$是点集, $E$是边集, $\left| V \right|=n$, $\left| E\right|=m$,结点以 $[1,n]$之间的连续整数编号, $(x,y,z)$描述一条从 $x$出发,到达 $y$,长度为 $z$的有向边.设 $1$号点为起点,求长度为 $n$的数组 $dist$,其中 $dist[i]$表示从 $1$到结点 $i$的最短路径的长度.

Dijkstra算法

$Dijkstra$算法步骤如下：

1. 初始化起点 $start$的 $dist[start]=0$,其余结点的 $dist$的值为正无穷大( $+ \infty$);
2. 找出一个未被标记的且 $dist[x]$最小的结点 $x$,然后标记结点 $x$;
3. 扫描结点 $x$的所有出边 $(x,y,z)$,若 $dist[y]>dist[x]+z$,则使用 $dist[x]+z$更新 $dist[y]$;
4. 重复上述 $2 \sim 3$两个步骤,直到所有结点都被标记.

$Dijkstra$算法基于贪心的思想,它只适用于所有边的长度都是非负数的图.当边长 $z$都是非负数时,全局最小值不可能再被其他结点更新,故在第一步选出的结点 $x$必然满足: $dist[x]$已经是起点到 $x$的最短路径.我们不断选择全局最小值进行标记和扩展,最终可得到起点 $start$到每一个结点的最短路径的长度.

举例：

• 用一个 $dis$数组保存源点到其余各个结点的距离, $dis[i]$表示源点到结点 $i$的距离,初始时 $dis$数组的各个元素为无穷大( $+ \infty$);用一个数组 $flag$标记是否找到了源点到该结点的最短距离,初始时 $flag$数组的各个元素清为 $0$;

• 假设源点是 $1$,将其 $dis[1]$设置为 $0$(源点到源点距离为 $0$);

• 遍历 $dis$数组,找到一个结点,这个结点是：没有确定最短路径的结点中距离源点最近的点.假设该结点编号为 $i$,此时就找到了源点到该结点的最短距离, $flag[i]$设置为 $1$;

• 遍历 $i$所有可以到达的结点 $j$,如果 $dis[j]>dis[i]+w[i][j]$( $w[i][j]$表示 $i \to j$的距离),则更新 $dis[j]$为 $dis[i]+w[i][j]$;

• 重复 $3 \sim 4$步骤,直到所有结点的 $flag$都标记为 $1$.

• 此时 $dis$数组中,就保存了源点到其余各个结点的最短距离.

Floyd算法

为了求出图中任意两点间的最短路径,当然可以把每个点作为起点,求解 $N$次单源最短路径问题.不过,在任意两点间最短路问题中,图一般比较稠密.使用 $Floyd$算法可以在 $O(n^3)$的时间内完成求解.

1. 初始化邻接矩阵(二维数组) $dist[][]$,其中 $dist[i][j]$表示顶点 $i$到顶点 $j$的权值,若顶点 $i$和顶点 $j$不相邻,则 $dist[i][j]=+ \infty$,若顶点 $i$等于顶点 $j$,则 $dist[i][j]=0$;
2. 以第 $1$个顶点为中介点,若 $dist[i][j]>dist[i][1]+dist[1][j]$,更新 $dist[i][j]$;
3. 依次以第 $2,3,\cdots,k,\cdots,n$个顶点为中介点,若 $dist[i][j]>dist[i][k]+dist[k][j]$,更新 $dist[i][j]$.

举例：

设 $dist[k,i,j]$表示经过若干个编号不超过k的结点,从 $i$到 $j$的最短路长度.该问题可划分为两个子问题,经过编号不超过 $k-1$的结点从 $i$到 $j$,或者从 $i$到 $k$,再到 $j$,可得:

$\color{Red}{dist[k,i,j]=min(dist[k-1,i,j],dist[k-1,i,k]+dist[k-1,k,j])}$

初值为 $dist[0,i,j]=A[i,j]$,其中 $A$为该图的邻接矩阵.

可以看到, $Floyd$算法的本质是动态规划, $k$是阶段,应置于最外层循环中, $i$和 $j$是附加状态,应置于内层循环.故不应该采用 $i,j,k$的顺序执行循环,会得到错误的答案. $k$这一维可省略(三维变成二维),最初,可直接用 $dist$保存邻接矩阵,然后执行动态规划的过程.当最外层循环到 $k$时,内层有转移方程: $\color{Red}{dist[i,j]=min(dist[i,j],dist[i,k]+dist[k,j])}$.

有向无环图描述表达式

若一个有向图中不存在环,则称为有向无环图,简称 $DAG$图.

将表达式转化为有向无环图步骤:

1. 把各个操作数不重复地排成一排;
2. 标出各个运算符的生效顺序(先后顺序有点出入无所谓);
3. 按顺序加入运算符,注意分层;
4. 从底向上逐层检查同层的运算符是否可以合体.

以(a*b)*(a*b)*(a*b)*c为例

• 第一步:把各个操作数不重复地排成一排

• 第二步:标出各个运算符的生效顺序(先后顺序有点出入无所谓)

• 第三步:按顺序加入运算符,注意分层

• 第四步:从底向上逐层检查同层的运算符是否可以合体

拓扑排序

在图论中,拓扑排序是一个有向无环图的所有顶点的线性序列,且该序列必须满足以下两个条件:

• 每个顶点出现且出现一次;
• 若存在一条从顶点 $A$到顶点 $B$的路径,那么在序列中顶点 $A$出现在顶点 $B$的前面.

有向无环图( $DAG$)才有拓扑排序,非 $DAG$无拓扑排序.例如下图中存在拓扑排序( $A,B,C,D$或 $A,C,B,D$可说明拓扑排序不唯一)

又如下图中不存在拓扑排序(存在 $B,C,D$构成的环,可说明拓扑排序可判断有向图是否有环)

拓扑排序的求法及步骤

• 该图中选择一个没有前驱(即入度为 $0$的顶点并记录该顶点;
• 从图中删除该顶点和所有以它为起点的有向边;
• 重复上述步骤,直到当前的图为空或者当前图中不存在没有前驱（入度为0）的顶点为止,如果满足后一种情况说明有向图必然存在环.

关键路径

在带权有向图,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为用边表示活动的网络,简称 $AOE$网(Activity On Edge NetWork).在 $AOV$网中的边无权值,仅表示顶点之间的前后关系.

在 $AOE$网具有以下两个性质:

• 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;
• 只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所发表的事件才能发生.

在 $AOE$网中仅有一个入度为 $0$的顶点,称为开始顶点(源点),它表示整个工程的开始;网中也仅存在一个出度为 $0$的顶点,称为结束顶点(汇点),它表示整个工程的结束.

从源点到汇点的有向路径可能有多条,所有路径中,具有最大路径长度的路径称为关键路径,而把关键路径上的活动称为关键活动.完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长.

• 事件 $v_k$的最早发生时间 $ve(k)$

它是指从源点 $v_1$到顶点 $v_k$的最长路径长度.事件 $v_k$的最早发生时间决定了所有从 $v_k$开始的活动能够开工的最早时间.

• $ve(源点)=0$;

• $\color{Red}{ve(k)=max(ve(j)+weight(v_j,v_k))}$, $v_k$为 $v_j$的任意后继, $weight(v_j,v_k)$表示 $\left< v_j,v_k \right>$上的权值.

计算 $ve()$值时,按从前往后的顺序进行,可以在拓扑排序的基础上计算:

• 初始时,令 $ve[1,\cdots,n]=0$;
• 输入一个入度为 $0$的顶点 $v_j$时,计算它所有直接后继顶点 $v_k$的最早发生时间,若 $ve[j]+weight(v_j,v_k)>ve[k]$,则 $ve[k]=ve[k]+weight(v_j,v_k)$.以此类推,直至输出全部顶点.

• 事件 $v_k$的最迟发生时间 $vl(k)$

它是指不推迟整个工程完成的前提下,即保证它的后继事件 $v_j$在其最迟发生时间 $vl(j)$能够发生时,该事件最迟必须发生的时间.

• $vl(汇点)=ve(汇点)$;
• $\color{Red}{vl(k)=min(vl(j)-weight(v_k,v_j))}$, $v_k$为 $v_j$的任意前驱.

计算 $vl()$值时,按从后往前的顺序进行,可以在逆拓扑排序(在上述拓扑排序中,增设一个栈以记录拓扑序列,拓扑排序结束后从栈顶至栈底为逆拓扑有序序列)的基础上计算.

• 初始时,令 $vl(1,\cdots,n)=ve[n]$;
• 栈顶顶点 $v_j$出栈,计算其所有直接前驱顶点 $v_k$的最迟发生时间,若 $vl[j]-weight(v_k,v_j) < vl[k]$,则 $vl[k]=vl[j]-weight(v_k,v_j)$.以此类推,直至输出全部栈中顶点.

• 活动 $a_i$的最早开始时间 $e(i)$

它是指该活动弧的起点所表示的事件的最早发生时间. 若边 $\left< v_k, v_j \right>$表示活动 $a_i$,则有 $\color{Red}{e(i)=ve(k)}$.

• 活动 $a_i$的最迟开始时间 $l(i)$

它是指该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差.若边 $\left< v_k, v_j \right>$表示活动 $a_i$,则有 $\color{Red}{l(i)=vl(j)-weight(v_k,v_j)}$.

• 一个活动 $a_i$的最迟开始时间 $l(i)$和其最早开始时间 $e(i)$的差额 $\color{Red}{d(i)=l(i)-e(i)}$

它是指活动完成的时间余量,即在不增加完成整个工程所需总时间的情况下,活动 $a_i$可以拖延的时间.若一个活动的时间余量为零,则说明该活动必须要如期完成,否则就会拖延整个工程的进度,故称 $l(i)-e(i)=0$即 $l(i)=e(i)$的活动 $a_i$是关键活动.

求解关键路径的步骤:

1. 从源点出发,令 $ve(源点)=0$,按拓扑有序求其余顶点(事件)的最早发生时间 $ve()$.
2. 从汇点出发,令 $vl(汇点)=ve(汇点)$,按逆拓扑有序求其余顶点(事件)的最迟发生时间 $vl()$.
3. 根据各顶点(事件)的 $ve()$值求所有弧(活动)的最早开始时间 $e()$.
4. 根据各顶点(事件)的 $vl()$值求所有弧(活动)的最迟开始时间 $l()$.
5. 求 $AOE$网中所有活动的差额 $d()$,找出所有 $d()=0$的活动构成关键路径.

举例：

拓扑序列为 $\color{Red}{V_1,V_2,V_3,V_4,V_5,V_6}$(其中 $V_2,V_3$可相互交换, $V_4,V_5$可相互交换)

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $V_1$,由于 $V_1$是源点,故 $ve(1)=0$;

• 对于事件 $V_2$,仅存在从 $V_1$到 $\color{Red}{V_2}$的边 $a_1=3$,故 $ve(2)=ve(1)+a_1=3$;

• 对于事件 $V_3$,仅存在从 $V_1$到 $\color{Red}{V_3}$的边 $a_2=2$,故 $ve(3)=ve(1)+a_2=2$;

• 对于事件 $V_4$,存在从 $V_2$到 $\color{Red}{V_4}$的边 $a_3=2$和从 $V_3$到 $\color{Red}{V_4}$的边 $a_5=4$, 两者取最大值,故 $ve(4)=max(ve(2)+a_3,ve(3)+a_5)=max(5,6)=6$;

• 对于事件 $V_5$,仅存在从 $V_2$到 $\color{Red}{V_5}$的边 $a_4=3$,故 $ve(5)=ve(2)+a_4=6$;

• 对于事件 $V_6$,存在从 $V_3$到 $\color{Red}{V_6}$的边 $a_6=3$、从 $V_4$到 $\color{Red}{V_6}$的边 $a_7=2$和从 $V_5$到 $\color{Red}{V_6}$的边 $a_8=1$,三者取最大值,故 $ve(6)=max(ve(3)+a_6,ve(4)+a_7,ve(5)+a_8)=max(5,8,7)=8$.

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $V_6$,由于 $V_6$是汇点,故 $vl(6)=ve(6)=8$;
• 对于事件 $V_5$,仅存在从 $\color{Green}{V_5}$到 $V_6$的边 $a_8=1$,故 $vl(5)=vl(6)-a_8=7$;
• 对于事件 $V_4$,仅存在从 $\color{Green}{V_4}$到 $V_6$的边 $a_7=2$,故 $vl(4)=vl(6)-a_7=6$;
• 对于事件 $V_3$,存在从 $\color{Green}{V_3}$到 $V_6$的边 $a_6=3$和从 $\color{Green}{V_3}$到 $V_4$的边 $a_5=4$,两者取最小值,故 $vl(3)=min(vl(6)-a_6,vl(4)-a_5)=min(5,2)=2$;
• 对于事件 $V_2$,存在从 $\color{Green}{V_2}$到 $V_4$的边 $a_3=2$和从 $\color{Green}{V_2}$到 $V_5$的边 $a_4=3$,两者取最小值,故 $vl(2)=min(vl(4)-a_3,vl(5)-a_4)=min(4,4)=4$;
• 对于事件 $V_1$,存在从 $\color{Green}{V_1}$到 $V_2$的边 $a_1=3$和从 $\color{Green}{V_1}$到 $V_3$的边 $a_2=2$,两者取最小值,故 $vl(1)=min(vl(2)-a_1,vl(3)-a_2)=min(1,0)=0$.

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $a_1$,弧起点为 $V_1$,弧终点为 $V_2$,故 $e(1)=ve(1)=0$, $l(1)=vl(2)-a_1=1$;

• 对于活动 $a_2$,弧起点为 $V_1$,弧终点为 $V_3$,故 $e(2)=ve(1)=0$, $l(2)=vl(3)-a_2=0$;

• 对于活动 $a_3$,弧起点为 $V_2$,弧终点为 $V_4$,故 $e(3)=ve(2)=3$, $l(3)=vl(4)-a_3=4$;

• 对于活动 $a_4$,弧起点为 $V_2$,弧终点为 $V_5$,故 $e(4)=ve(2)=3$, $l(4)=vl(5)-a_4=4$;

• 对于活动 $a_5$,弧起点为 $V_3$,弧终点为 $V_4$,故 $e(5)=ve(3)=2$, $l(5)=vl(4)-a_5=2$;

• 对于活动 $a_6$,弧起点为 $V_3$,弧终点为 $V_6$,故 $e(6)=ve(3)=2$, $l(6)=vl(6)-a_6=5$;

• 对于活动 $a_7$,弧起点为 $V_4$,弧终点为 $V_6$,故 $e(7)=ve(4)=6$, $l(7)=vl(6)-a_7=6$;

• 对于活动 $a_8$,弧起点为 $V_5$,弧终点为 $V_6$,故 $e(8)=ve(5)=6,l(8)=vl(6)-a_8=7$.

最后计算 最迟开始时间 $l()$和其最早开始时间 $e()$的差额 $\color{Red}{d()=l()-e()}$(根据 $l()$是否与 $e()$相等)

• 对于活动 $a_1$, $e(1) \neq l(1)$,故活动 $a_1$不是关键活动;
• 对于活动 $a_2$, $e(2) = l(2)$,故活动 $a_2$是关键活动;
• 对于活动 $a_3$, $e(3) \neq l(3)$,故活动 $a_3$不是关键活动;
• 对于活动 $a_4$, $e(4) \neq l(4)$,故活动 $a_4$不是关键活动;
• 对于活动 $a_5$, $e(5) = l(5)$,故活动 $a_5$是关键活动;
• 对于活动 $a_6$, $e(6) \neq l(6)$,故活动 $a_6$不是关键活动;
• 对于活动 $a_7$, $e(7) \neq l(7)$,故活动 $a_7$是关键活动;
• 对于活动 $a_8$, $e(8) \neq l(8)$,故活动 $a_8$不是关键活动.

综上,故 $a_2,a_5,a_7$为关键活动, $(V_1,V_3,V_4,V_6)$为关键路径.

关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可以通过加快关键活动来缩短整个工程的工期.但也不能任意缩短关键活动,因为一旦缩短到一定的程度,该关键活动就能变成非关键活动.

网中关键路径并不唯一,且对于有几条关键网络的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的.

已知带权连通无向图 $G=(V,E)$,其中 V={ $v_1,v_2,v_3,v_4,v_5,v_6,v_7$ }, E={ $(v_1,v_2)10,(v_1,v_3)2,(v_3,v_4)2,(v_3,v_6)11,$ $(v_2,v_5)1,(v_4,v_5)4,(v_4,v_6)6,(v_5,v_7)7,(v_6,v_7)3$}(注:顶点偶对括号外的数据表示边上的权值),从源点 $v_1$到顶点 $v_7$的最短路径上经过的顶点序列是().

A. $v_1,v_2,v_5,v_7$

B. $\color{Red}{v_1,v_3,v_4,v_6,v_7}$

C. $v_1,v_3,v_4,v_5,v_7$

D. $v_1,v_2,v_5,v_4,v_6,v_7$

• 选项 $A$,对于顶点序列 $v_1,v_2,v_5,v_7$,路径和为 $10+1+7=18$;
• 选项 $B$,对于顶点序列 $v_1,v_3,v_4,v_6,v_7$,路径和为 $2+2+6+3=13$;
• 选项 $C$,对于顶点序列 $v_1,v_3,v_4,v_5,v_7$,路径和为 $2+2+4+7=15$;
• 选项 $D$,对于顶点序列 $v_1,v_2,v_5,v_4,v_6,v_7$,路径和为 $10+1+4+6+3=24$;

故最短路径为 $v_1 \to v_3 \to v_4 \to v_6 \to v_7$.

下图所示有向图的所有拓扑序列共有()个.

A. $4$

B. $6$

C. $\color{Red}{5}$

D. $7$

拓扑排序序列可能如下(共 $5$种):

• $ABCDEFG$
• $ABCDFEG$
• $ABCFDEG$
• $ABDCEFG$
• $ABDCFEG$

下列关于图的说法中,正确的是( $\color{Red}{C}$).

Ⅰ. 有向图中顶点 $V$的度等于其邻接矩阵中第 $V$行中 $1$的个数

Ⅱ. 无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵

Ⅲ. 在带权图 $G$的最小生成树 $G_1$中,某条边的权值可能会超过未选边的权值

Ⅳ. 若有向无环图的拓扑序列唯一,则可以唯一确定该图

A. Ⅰ、Ⅱ和Ⅲ

B. Ⅲ和Ⅳ

C. Ⅲ

D. Ⅳ

• 对于Ⅰ,邻接矩阵中第 $V$行中 $1$的个数表示有向图中顶点 $V$的出度,邻接矩阵中第 $V$列中 $1$的个数表示有向图中顶点 $V$的入度,而有向图中顶点的度为入度和出度的和,故Ⅰ错误;
• 对于Ⅱ,无向图可看作特殊的有向图,故有向图不一定是非对称矩阵,故Ⅱ错误;
• 对于Ⅲ,最小生成树中的 $n-1$条边并不能保证是图中权值最小的 $n-1$条边,因为权值最小的 $n-1$条边并不一定使得图连通,故Ⅲ正确;

• 对于Ⅳ,有向无环图的拓扑序列唯一并不能唯一确定该图,故Ⅳ错误.

若某带权图为 $G=(V,E)$,其中V={ $v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10}$ }, E={ $\left< v_1,v_2 \right> 5, \left< v_1,v_3 \right> 6 , \left< v_2,v_5 \right> 3, \left< v_3,v_5 \right> 6, \left< v_3,v_4 \right> 3,$ $\left< v_4,v_5\right>3,\left< v_4,v_7\right>1,\left< v_4,v_8\right>4,\left< v_5,v_6 \right>4, \left< v_5,v_7 \right>2,\left< v_6,v_{10} \right>4,$ $\left< v_7,v_9\right>5,\left< v_8,v_9\right>2,\left< v_9,v_{10}\right>2$ }(注:边括号外的数据表示边上的权值),则 $G$的关键路径的长度为().

A. $19$

B. $20$

C. $\color{Red}{21}$

D. $22$

关键路径为 $(v_1,v_3,v_4(可省略),v_5,v_7,v_9,v_{10})$,关键路径长度为 $6+6(或3+3)+2+5+2=21$.

下面关于求关键路径的说法中,不正确的是( $\color{Red}{C}$)

A. 求关键路径是以拓扑排序为基础的

B. 一个事件的最早发生时间与该事件为始的弧的活动的最早开始时间相同

C. 一个事件的最迟发生时间是以该事件尾的弧的活动的最迟开始时间与该活动的持续时间的差

D. 关键活动一定位于关键路径上

一个事件的最迟发生时间 $=min$ {以该事件为尾(出发)的弧的活动的最迟开始时间 }或 $min$ { 以该事件为尾(出发)的弧所指的事件的最迟发生时间与该弧的活动的持续时间之差 }.

2010统考真题：对下图进行拓扑排序,可得不同拓扑序列的个数是().

A. $4$

B. $\color{Red}{3}$

C. $2$

D. $1$

拓扑排序序列可能如下(共 $3$种):

• $aebcd$
• $abced$
• $abecd$

2012统考真题：对下图所示的有向带权图,若采用 $Dijkstra$算法从源点 $a$到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是 $b$,第二条最短路径的目标顶点是 $c$,后续得到的其余各最短路径的目标顶点依次是().

A. $d,e,f$

B. $e,d,f$

C. $\color{Red}{f,d,e}$

D. $f,e,d$

可通过下表可看出最后选择的目标顶点依次是 $f,d,e$.

2013统考真题：下列 $AOE$网表示一项包含 $8$个活动的工程,通过同时加快若干活动的进度可以缩短整个工程的工期.下列选项中,可以加快其进度就可以缩短工程工期的是().

A. $c和e$

B. $d和c$

C. $\color{Red}{f和d}$

D. $f和h$

拓扑序列为 $1,3,2,4,5,6$(其中 $4,5$可交换)

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $1$,由于 $1$是源点,故 $ve(1)=0$;
• 对于事件 $3$,仅存在从 $1$到 $\color{Red}{3}$的边 $b=8$,故 $ve(3)=ve(0)+b=8$;
• 对于事件 $2$,存在从 $1$到 $\color{Red}{2}$的边 $a=3$和从 $3$到 $\color{Red}{2}$的边 $d=4$, 两者取最大值,故 $ve(2)=max(ve(1)+a,ve(3)+d)=max(3,12)=12$;
• 对于事件 $4$,仅存在从 $2$到 $\color{Red}{4}$的边 $c=9$,故 $ve(4)=ve(2)+c=21$;
• 对于事件 $5$,存在从 $2$到 $\color{Red}{5}$的边 $e=6$和从 $3$到 $\color{Red}{5}$的边 $f=10$, 两者取最大值,故 $ve(5)=max(ve(2)+e,ve(3)+f)=max(18,18)=18$;
• 对于事件 $6$,存在从 $4$到 $\color{Red}{6}$的边 $g=6$和从 $5$到 $\color{Red}{6}$的边 $h=9$,两者取最大值,故 $ve(6)=max(ve(4)+g,ve(5)+h)=max(27,27)=27$.

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $6$,由于 $6$是汇点,故 $vl(6)=ve(6)=27$;
• 对于事件 $5$,仅存在从 $\color{Green}{5}$到 $6$的边 $h=9$,故 $vl(5)=vl(6)-h=18$;
• 对于事件 $4$,仅存在从 $\color{Green}{4}$到 $6$的边 $g=6$,故 $vl(4)=vl(6)-g=21$;
• 对于事件 $2$,存在从 $\color{Green}{2}$到 $4$的边 $c=9$和从 $\color{Green}{2}$到 $5$的边 $e=6$,两者取最小值,故 $vl(2)=min(vl(4)-c,vl(5)-e)=min(12,12)=12$;
• 对于事件 $3$,存在从 $\color{Green}{3}$到 $5$的边 $f=10$和从 $\color{Green}{3}$到 $2$的边 $d=4$,两者取最小值,故 $vl(3)=min(vl(5)-f,vl(2)-d)=min(8,8)=8$;
• 对于事件 $1$,存在从 $\color{Green}{1}$到 $2$的边 $a=3$和从 $\color{Green}{1}$到 $3$的边 $b=8$,两者取最小值,故 $vl(1)=min(vl(2)-a,vl(3)-b)=min(9,0)=0$.

计算事件的最早发生时间和最迟发生时间如下表:

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $a$,弧起点为 $1$,弧终点为 $2$,故 $e(a)=ve(1)=0$, $l(a)=vl(2)-a=9$;
• 对于活动 $b$,弧起点为 $1$,弧终点为 $3$,故 $e(b)=ve(1)=0$, $l(b)=vl(3)-b=0$;
• 对于活动 $c$,弧起点为 $2$,弧终点为 $4$,故 $e(c)=ve(2)=12$, $l(c)=vl(4)-c=12$;
• 对于活动 $d$,弧起点为 $3$,弧终点为 $2$,故 $e(d)=ve(3)=8$, $l(d)=vl(2)-d=8$;
• 对于活动 $e$,弧起点为 $2$,弧终点为 $5$,故 $e(e)=ve(2)=12$, $l(e)=vl(5)-e=12$;
• 对于活动 $f$,弧起点为 $3$,弧终点为 $5$,故 $e(f)=ve(3)=8$, $l(f)=vl(5)-f=8$;
• 对于活动 $g$,弧起点为 $4$,弧终点为 $6$,故 $e(g)=ve(4)=21$, $l(g)=vl(6)-g=21$;
• 对于活动 $h$,弧起点为 $5$,弧终点为 $6$,故 $e(h)=ve(5)=18$, $l(h)=vl(6)-h=18$.

计算活动的最早开始时间和最迟开始时间如下表:

故可得出全部关键活动为 $b,d,c,g$和 $b,d,e,h$和 $b,f,h$.只有关键路径上的活动时间同时减少时,才能缩短工期.而当 $f$和 $d$同时减少会缩短工期.

2012统考真题：若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是( $\color{Red}{C}$).

A. 存在,且唯一

B. 存在,且不唯一

C. 存在,可能不唯一

D. 无法确定是否存在

对角线以下的元素均为零,表明只有从顶点 $i$到顶点 $j$( $i < j$)可能有边,而从顶点 $j$到顶点 $i$一定无边,即有向图是一个无环图,故一定存在拓扑序列.

对于下图对应的拓扑序列为 $1,2,3$或 $1,3,2$,故此时存在不唯一的拓扑序列;若对角线以上的元素均为 $1$,以下元素全为 $0$,则拓扑序列唯一.

2014统考真题：对下图所示的有向图进行拓扑排序,得到的拓扑序列可能是().

A. $3,1,2,4,5,6$

B. $3,1,2,4,6,5$

C. $3,1,4,2,5,6$

D. $\color{Red}{3,1,4,2,6,5}$

该图的拓扑序列为 $3,1,4,2,6,5$( $2,6$可交换顺序)

2015统考真题：求下面的带权图的最小(代价)生成树时,可能是 $Kruskal$算法第 $2$次选中但不是 $Prim$算法(从 $V_4$开始)第 $2$次选中的边是().

A. $(V_1,V_3)$

B. $(V_1,V_4)$

C. $\color{Red}{(V_2,V_3)}$

D. $(V_3,V_4)$

对于 $Kruskal$算法第一步会选择 $(V_1,V_4)$,第二歩会选择 $(V_1,V_3)$或 $\color{Red}{(V_2,V_3)}$或者 $(V_3,V_4)$;而对于 $Prim$算法第一步会选择 $(V_1,V_4)$,第二歩会选择 $(V_1,V_3)$或者$(V_3,V_4)$.

2016统考真题：使用 $Dijkstra$算法求下图中从顶点 $1$到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是().

A. $5,2,3,4,6$

B. $\color{Red}{5,2,3,6,4}$

C. $5,2,4,3,6$

D. $5,2,6,3,4$

可通过下表可看出目标顶点(除去起点)依次是 $5,2,3,6,4$

2018统考真题：下列选项中,不是如下有向图的拓扑序列的是().

A. $1,5,2,3,6,4$

B. $5,1,2,6,3,4$

C. $5,1,2,3,6,4$

D. $\color{Red}{5,2,1,6,3,4}$

存在的拓扑序列如下(共 $4$种)

• $1,5,2,3,6,4$
• $1,5,2,6,3,4$
• $5,1,2,3,6,4$
• $5,1,2,6,3,4$

拓扑排序每次选取入度为 $0$的结点输出,不难发现拓扑序列前两位一定是 $1,5$或 $5,1$(因为只有 $1$和 $5$的入度均为 $0$,且其他结点都不满足仅有 $1$或仅有 $5$作为前驱),故 $D$错误.

2019统考真题：下图所示的 $AOE$网表示一项包含 $8$个活动的工程,活动 $d$的最早开始时间和最迟开始时间分别是()

A. $3和7$

B. $12和12$

C. $\color{Red}{12和14}$

D. $15和15$

拓扑序列为 $1,3,2,4,5,6$(其中 $4,5$可交换)——该图和前面2013统考真题差别在于 $2$到 $4$的边权有变化,且 $b,c,d$编号有出入

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $1$,由于 $1$是源点,故 $ve(1)=0$;
• 对于事件 $3$,仅存在从 $1$到 $\color{Red}{3}$的边 $c=8$,故 $ve(3)=ve(0)+c=8$;
• 对于事件 $2$,存在从 $1$到 $\color{Red}{2}$的边 $a=3$和从 $3$到 $\color{Red}{2}$的边 $b=4$, 两者取最大值,故 $ve(2)=max(ve(1)+a,ve(3)+b)=max(3,12)=12$;
• 对于事件 $4$,仅存在从 $2$到 $\color{Red}{4}$的边 $d=7$,故 $ve(4)=ve(2)+d=19$;
• 对于事件 $5$,存在从 $2$到 $\color{Red}{5}$的边 $e=6$和从 $3$到 $\color{Red}{5}$的边 $f=10$, 两者取最大值,故 $ve(5)=max(ve(2)+e,ve(3)+f)=max(18,18)=18$;
• 对于事件 $6$,存在从 $4$到 $\color{Red}{6}$的边 $g=6$和从 $5$到 $\color{Red}{6}$的边 $h=9$,两者取最大值,故 $ve(6)=max(ve(4)+g,ve(5)+h)=max(27,27)=27$.

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $6$,由于 $6$是汇点,故 $vl(6)=ve(6)=27$;
• 对于事件 $5$,仅存在从 $\color{Green}{5}$到 $6$的边 $h=9$,故 $vl(5)=vl(6)-h=18$;
• 对于事件 $4$,仅存在从 $\color{Green}{4}$到 $6$的边 $g=6$,故 $vl(4)=vl(6)-g=21$;
• 对于事件 $2$,存在从 $\color{Green}{2}$到 $4$的边 $d=7$和从 $\color{Green}{2}$到 $5$的边 $e=6$,两者取最小值,故 $vl(2)=min(vl(4)-d,vl(5)-e)=min(14,12)=12$;
• 对于事件 $3$,存在从 $\color{Green}{3}$到 $5$的边 $f=10$和从 $\color{Green}{3}$到 $2$的边 $b=4$,两者取最小值,故 $vl(3)=min(vl(5)-f,vl(2)-b)=min(8,8)=8$;
• 对于事件 $1$,存在从 $\color{Green}{1}$到 $2$的边 $a=3$和从 $\color{Green}{1}$到 $3$的边 $c=8$,两者取最小值,故 $vl(1)=min(vl(2)-a,vl(3)-c)=min(9,0)=0$.

计算事件的最早发生时间和最迟发生时间如下表:

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $a$,弧起点为 $1$,弧终点为 $2$,故 $e(a)=ve(1)=0$, $l(a)=vl(2)-a=9$;
• 对于活动 $b$,弧起点为 $3$,弧终点为 $2$,故 $e(b)=ve(3)=8$, $l(b)=vl(2)-b=8$;
• 对于活动 $c$,弧起点为 $1$,弧终点为 $3$,故 $e(c)=ve(1)=0$, $l(c)=vl(3)-c=0$;
• 对于活动 $d$,弧起点为 $2$,弧终点为 $4$,故 $e(d)=ve(2)=12$, $l(d)=vl(4)-d=14$;
• 对于活动 $e$,弧起点为 $2$,弧终点为 $5$,故 $e(e)=ve(2)=12$, $l(e)=vl(5)-e=12$;
• 对于活动 $f$,弧起点为 $3$,弧终点为 $5$,故 $e(f)=ve(3)=8$, $l(f)=vl(5)-f=8$;
• 对于活动 $g$,弧起点为 $4$,弧终点为 $6$,故 $e(g)=ve(4)=19$, $l(g)=vl(6)-g=21$;
• 对于活动 $h$,弧起点为 $5$,弧终点为 $6$,故 $e(h)=ve(5)=18$, $l(h)=vl(6)-h=18$.

计算活动的最早开始时间和最迟开始时间如下表:

故由表知,活动 $d$的最早开始时间和最迟开始时间分别为 $12,14$.

2019统考真题：用有向无环图描述表达式 $(x+y)((x+y)/x)$,需要的顶点个数至少是().

A. $\color{Red}{5}$

B. $6$

C. $8$

D. $9$

首先将该表达式转换成有向二叉树,然后将有向二叉树去重转换成有向无环图,故化简后至少需要 $5$个顶点.

2020统考真题：已知无向图 $G$如下所示,使用克鲁斯卡尔( $Kruskal$)算法求图 $G$的最小生成树,加到最小生成树的边依次是().

A. $\color{Red}{(b,f),(b,d),(a,e),(c,e),(b,e)}$

B. $(b,f),(b,d),(b,e),(a,e),(c,e)$

C. $(a,e),(b,e),(c,e),(b,d),(b,f)$

D. $(a,e),(c,e),(b,e),(b,f),(b,d)$

由该图知,加到最小生成树的边依次 $(b,f),(b,d),(a,e),(c,e),(b,e)$.

2021统考真题：给定如下有向图,该图的拓扑有序序列的个数是().

A. $\color{Red}{1}$

B. $2$

C. $3$

D. $4$

该图的拓扑有序序列仅为 $A,B,C,D,E,F$,故只有 $1$个.

2021统考真题：使用 $Dijkstra$算法求下图中从顶点 $1$到其余各顶点的最短路径,将当前找到的从顶点 $1$到顶点 $2,3,4,5$的最短路径长度保存在数组 $dist$中,求出第二条最短路径后, $dist$中的内容更新为().

A. $26,3,14,6$

B. $25,3,14,6$

C. $\color{Red}{21,3,14,6}$

D. $15,3,14,6$

由表知求出第二条最短路径后, $dist$中的内容更新为 $21,3,14,6$

2022统考真题：下图是一个有 $10$个活动的 $AOE$网,时间余量最大的活动是().

A. $c$

B. $\color{Red}{g}$

C. $h$

D. $j$

拓扑序列为 $1,2,3,4,5,6$

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $1$,由于 $1$是源点,故 $ve(1)=0$;
• 对于事件 $2$,仅存在从 $1$到 $\color{Red}{2}$的边 $a=2$,故 $ve(2)=ve(1)+a=2$;
• 对于事件 $3$,存在从 $1$到 $\color{Red}{3}$的边 $b=5$和从 $2$到 $\color{Red}{3}$的边 $c=1$, 两者取最大值,故 $ve(3)=max(ve(1)+b,ve(2)+c)=max(5,3)=5$;
• 对于事件 $4$,存在从 $2$到 $\color{Red}{4}$的边 $d=3$和从 $3$到 $\color{Red}{4}$的边 $e=3$, 两者取最大值,故 $ve(4)=max(ve(2)+d,ve(3)+e)=max(5,8)=8$;
• 对于事件 $5$,存在从 $3$到 $\color{Red}{5}$的边 $f=4$和从 $4$到 $\color{Red}{5}$的边 $h=1$, 两者取最大值,故 $ve(5)=max(ve(3)+f,ve(4)+h)=max(9,9)=9$;
• 对于事件 $6$,存在从 $3$到 $\color{Red}{6}$的边 $g=1$、从 $4$到 $\color{Red}{6}$的边 $i=4$和从 $5$到 $\color{Red}{6}$的边 $j=1$, 三者取最大值,故 $ve(3)=max(ve(3)+g,ve(4)+i,ve(5)+j)=max(6,12,10)=12$;

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $6$,由于 $6$是汇点,故 $vl(6)=ve(6)=12$;
• 对于事件 $5$,仅存在从 $\color{Green}{5}$到 $6$的边 $j=1$,故 $vl(5)=vl(6)-j=11$;
• 对于事件 $4$,存在从 $\color{Green}{4}$到 $5$的边 $h=1$和从 $\color{Green}{4}$到 $6$的边 $i=4$,两者取最小值,故 $vl(4)=min(vl(5)-h,vl(6)-i)=min(10,8)=8$;
• 对于事件 $3$,存在从 $\color{Green}{3}$到 $4$的边 $e=3$、从 $\color{Green}{3}$到 $5$的边 $f=4$和从 $\color{Green}{3}$到 $6$的边 $g=1$,三者取最小值,故 $vl(3)=min(vl(4)-e,vl(5)-f,vl(6)-g)=min(5,8,11)=5$;
• 对于事件 $2$,存在从 $\color{Green}{2}$到 $4$的边 $d=3$和从 $\color{Green}{2}$到 $3$的边 $c=1$,两者取最小值,故 $vl(2)=min(vl(4)-d,vl(3)-c)=min(5,4)=4$;
• 对于事件 $1$,存在从 $\color{Green}{1}$到 $2$的边 $a=2$和从 $\color{Green}{1}$到 $3$的边 $b=5$,两者取最小值,故 $vl(1)=min(vl(2)-a,vl(3)-b)=min(2,0)=0$;

计算事件的最早发生时间和最迟发生时间如下表:

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $a$,弧起点为 $1$,弧终点为 $2$,故 $e(a)=ve(1)=0$, $l(a)=vl(2)-a=2$;
• 对于活动 $b$,弧起点为 $1$,弧终点为 $3$,故 $e(b)=ve(1)=0$, $l(b)=vl(3)-b=0$;
• 对于活动 $c$,弧起点为 $2$,弧终点为 $3$,故 $e(c)=ve(2)=2$, $l(c)=vl(3)-c=4$;
• 对于活动 $d$,弧起点为 $2$,弧终点为 $4$,故 $e(d)=ve(2)=2$, $l(d)=vl(4)-d=5$;
• 对于活动 $e$,弧起点为 $3$,弧终点为 $4$,故 $e(e)=ve(3)=5$, $l(e)=vl(4)-e=5$;
• 对于活动 $f$,弧起点为 $3$,弧终点为 $5$,故 $e(f)=ve(3)=5$, $l(f)=vl(5)-f=7$;
• 对于活动 $g$,弧起点为 $3$,弧终点为 $6$,故 $e(g)=ve(3)=5$, $l(g)=vl(6)-g=11$;
• 对于活动 $h$,弧起点为 $4$,弧终点为 $5$,故 $e(h)=ve(4)=8$, $l(h)=vl(5)-h=10$;
• 对于活动 $i$,弧起点为 $4$,弧终点为 $6$,故 $e(i)=ve(4)=8$, $l(i)=vl(6)-i=8$;
• 对于活动 $j$,弧起点为 $5$,弧终点为 $6$,故 $e(j)=ve(5)=9$, $l(j)=vl(6)-j=11$.

计算活动的最早开始时间、最迟开始时间和时间余量(两者作差)如下表(关键路径为 $1,3,4,6$):

6.4.1

下面是一种称为破圈法的求解最小生成树的方法:

所谓破圈法,是指任取一圈,去掉圈上权最大的边,反复执行这一步骤,直到没有圈为止.

试判断这种方法是否正确,若正确,说明理由;若不正确,举出反例(注:圈就是回路).

正确.

证明如下:

设 $T$为图 $G$的最小生成树, $T’$为破圈法得到的生成树

假设 $T’$不是最小生成树,则 $\exists e=uv \in T$且 $e \notin T’$

则 $T’+e$,中含有一个圈 $C$,由破圈法得到 $T’$的过程易知 $e \in C$为圈 $C$中权值最大的边

此外,图 $T-e$包含两个连通片,设为 $T_1$和 $T_2$,且 $u \in T_1$, $v \in T_2$,则 $C$中必定存在一条边 $e’=u’v’$,其中 $u’ \in T_1$, $v’ \in T_2$,且 $e’$的权值小于等于 $e$的权值

1. 若 $e’$的权值小于 $e$的权值,则 $T-e+e’$是图 $G$的一个权值比 $T$小的生成树,与 $T$是最小生成树矛盾

2. 若 $e’$与 $e$的权值相等,则 $T-e+e’$也是图 $G$的一棵最小生成树,且相比于 $T,T-e+e’$与 $T’$的公共边数多一

a. 若 $T-e+e’$与 $T’$相同(公共边一样),则 $T’$与 $T-e+e’$权值相同,因此是最小生成树,与假设矛盾

b. 若 $T-e+e’$与 $T’$不同,则 $\exists e’‘=u’‘v’‘ \in T-e+e’$且 $e \in T’$,不断重复上述整个过程,每次可得到另一棵相比于 $T-e+e’$,与 $T’$的公共边数多一的最小生成树,直到得到一棵与 $T’$公共边完全相同的最小生成树,即说明 $T’$是最小生成树,与题设矛盾

书上的证明:

扩展:

破圈法的时间复杂度：需要删除 $E-(V-1)$条边,即重复寻找 $E-(V-1)$个圈,如果利用 $DFS$寻找圈,时间复杂度为 $O(E+V)$,可以在 $DFS$过程中记录当前路径上权值最大的边,一般连通图 $E > V$,故时间复杂度为 $O(E^2)$.

6.4.2

已知有向图如下图所示.

1. 写出该图的邻接矩阵表示并据此给出从顶点 $1$出发的深度优先遍历序列.
2. 写该有向图的强连通分量的数目.
3. 给出该图的任意两个拓扑序列.
4. 若将该图视为无向图,分别用 $Prim$算法和 $Kruskal$算法求最小生成树.

(1) 邻接矩阵如下:

深度优先遍历序列为 $1,2,3,5,7,4,6$

有向图强连通分量:在有向图 $G$中,如果两个顶点 $v_i,v_j$间( $v_i > v_j$)有一条从 $v_i$到 $v_j$的有向路径,同时还有一条从 $v_j$到 $v_i$的有向路径,则称两个顶点强连通.

(2) 当某个顶点只有出弧而没有入弧时,其他顶点无法到达这个顶点,不可能与其他顶点和边构成强连通分量(这个单独的顶点构成一个强连通分量).

• 顶点 $1$无入弧构成第一个强连通分量,删除顶点 $1$及所有以之为尾(出边)的弧;
• 顶点 $2$无入弧构成一个强连通分量,删除顶点 $2$及所有以之为尾的弧(出边)的弧;

• $\cdots$

• 顶点 $7$无入弧构成一个强连通分量,删除顶点 $7$及所有以之为尾的弧(出边)的弧.

综上,每个顶点都是一个强连通分量.故强连通分量数目为 $7$.

(3) $1,2,4,6,3,5,7$或 $1,4,6,2,3,5,7$或 $1,4,2,6,3,5,7$

(4) 假设是 $Prim$算法(以 $3$号结点开始),第一步选择边 $(1,3)$,第二歩选择边 $(1,2)$,第三步选择边 $(3,6)$,第四步选择边 $(3,5)$(此时不会选择 $(2,3)$,会构成环),第五步选择边 $(5,7)$,最后选择 $(4,6)$(此时不会选择 $(2,5)$,会构成环).

若是 $Kruskal$算法,此处选择比较随意,假设最先选择权值最小的边 $(5,7)$,然后选择权值最小的边 $(3,6)$,接着选择权值最小的边 $(1,2)$,接着选择边 $(1,3)$,接着选择边 $(3,5)$(此时不会选择 $(2,3)$,会构成环),最后选择边 $(4,6)$(此时不会选择 $(2,5)$,会构成环).

6.4.3

对下图所示的无向图,按照 $Dijkstra$算法,写出从顶点 $1$到其他各个顶点的最短路径和最短路径长度(顺序不能颠倒).

其中上方表示从 $1$出发的路径,下方表示对应的路径和

6.4.4

下图所示为一个用 $AOE$网表示的工程.

1. 画出此图的邻接表表示.

2. 完成次工程至少需要多少时间?

3. 指出关键路径.

4. 哪些活动加速可以缩短完成工程所需的时间?

(1) 邻接表如下

计算关键路径(为 $2,3,4$问作准备)

拓扑序列为 $1,2,3,4,5,6,7,8,9$( $4,5$可交换)

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $V_1$,由于 $V_1$是源点,故 $ve(1)=0$;
• 对于事件 $V_2$,仅存在从 $V_1$到 $\color{Red}{V_2}$的边 $a_1=2$,故 $ve(2)=ve(1)+a_1=2$;
• 对于事件 $V_3$,存在从 $V_1$到 $\color{Red}{V_3}$的边 $a_2=5$和从 $V_2$到 $\color{Red}{V_3}$的边 $a_5=2$, 两者取最大值,故 $ve(3)=max(ve(1)+a_2,ve(2)+a_5)=max(5,4)=5$;
• 对于事件 $V_4$,仅存在从 $V_2$到 $\color{Red}{V_4}$的边 $a_4=3$,故 $ve(4)=ve(2)+a_4=5$;
• 对于事件 $V_5$,存在从 $V_1$到 $\color{Red}{V_5}$的边 $a_3=5$和从 $V_3$到 $\color{Red}{V_5}$的边 $a_6=1$, 两者取最大值,故 $ve(5)=max(ve(1)+a_3,ve(3)+a_6)=max(5,6)=6$;
• 对于事件 $V_6$,存在从 $V_4$到 $\color{Red}{V_6}$的边 $a_8=2$和从 $V_3$到 $\color{Red}{V_6}$的边 $a_7=3$, 两者取最大值,故 $ve(6)=max(ve(4)+a_8,ve(3)+a_7)=max(7,8)=8$;
• 对于事件 $V_7$,存在从 $V_5$到 $\color{Red}{V_7}$的边 $a_9=6$和从 $V_6$到 $\color{Red}{V_7}$的边 $a_{11}=3$, 两者取最大值,故 $ve(7)=max(ve(5)+a_9,ve(6)+a_{11})=max(12,11)=12$;
• 对于事件 $V_8$,仅存在从 $V_6$到 $\color{Red}{V_8}$的边 $a_{10}=4$,故 $ve(8)=ve(6)+a_{10}=12$;
• 对于事件 $V_9$,存在从 $V_7$到 $\color{Red}{V_9}$的边 $a_{12}=4$和从 $V_8$到 $\color{Red}{V_9}$的边 $a_{13}=2$, 两者取最大值,故 $ve(9)=max(ve(7)+a_{12},ve(8)+a_{13})=max(16,14)=16$.

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $V_9$,由于 $V_9$是汇点,故 $vl(9)=ve(9)=16$;
• 对于事件 $V_8$,仅存在从 $\color{Green}{V_8}$到 $V_9$的边 $a_{13}=2$,故 $vl(8)=vl(9)-a_{13}=14$;
• 对于事件 $V_7$,仅存在从 $\color{Green}{V_7}$到 $V_9$的边 $a_{12}=4$,故 $vl(7)=vl(9)-a_{12}=12$;
• 对于事件 $V_6$,存在从 $\color{Green}{V_6}$到 $V_8$的边 $a_{10}=4$和从 $\color{Green}{V_6}$到 $V_7$的边 $a_{11}=3$,两者取最小值,故 $vl(6)=min(vl(8)-a_{10},vl(7)-a_{11})=min(10,9)=9$;
• 对于事件 $V_5$,仅存在从 $\color{Green}{V_5}$到 $V_7$的边 $a_9=6$,故 $vl(5)=vl(7)-a_9=6$;
• 对于事件 $V_4$,仅存在从 $\color{Green}{V_4}$到 $V_6$的边 $a_8=2$,故 $vl(4)=vl(6)-a_8=7$;
• 对于事件 $V_3$,存在从 $\color{Green}{V_3}$到 $V_5$的边 $a_6=1$和从 $\color{Green}{V_3}$到 $V_6$的边 $a_7=3$,两者取最小值,故 $vl(3)=min(vl(5)-a_6,vl(6)-a_7)=min(5,6)=5$;
• 对于事件 $V_2$,存在从 $\color{Green}{V_2}$到 $V_3$的边 $a_5=2$和从 $\color{Green}{V_2}$到 $V_4$的边 $a_4=3$,两者取最小值,故 $vl(2)=min(vl(3)-a_5,vl(4)-a_4)=min(3,4)=3$;
• 对于事件 $V_1$,存在从 $\color{Green}{V_1}$到 $V_2$的边 $a_1=2$、从 $\color{Green}{V_1}$到 $V_3$的边 $a_2=5$和从 $\color{Green}{V_1}$到 $V_5$的边 $a_3=5$,三者取最小值,故 $vl(1)=min(vl(2)-a_1,vl(3)-a_2,vl(5)-a_3)=min(1,0,1)=0$.

计算事件的最早发生时间和最迟发生时间如下表:

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $a_1$,弧起点为 $1$,弧终点为 $2$,故 $e(a_1)=ve(1)=0$, $l(a_1)=vl(2)-a_1=1$;
• 对于活动 $a_2$,弧起点为 $1$,弧终点为 $3$,故 $e(a_2)=ve(1)=0$, $l(a_2)=vl(3)-a_2=0$;
• 对于活动 $a_3$,弧起点为 $1$,弧终点为 $5$,故 $e(a_3)=ve(1)=0$, $l(a_3)=vl(5)-a_3=1$;
• 对于活动 $a_4$,弧起点为 $2$,弧终点为 $4$,故 $e(a_4)=ve(2)=2$, $l(a_4)=vl(4)-a_4=4$;
• 对于活动 $a_5$,弧起点为 $2$,弧终点为 $3$,故 $e(a_5)=ve(2)=2$, $l(a_5)=vl(3)-a_5=3$;
• 对于活动 $a_6$,弧起点为 $3$,弧终点为 $5$,故 $e(a_6)=ve(3)=5$, $l(a_6)=vl(5)-a_6=5$;
• 对于活动 $a_7$,弧起点为 $3$,弧终点为 $6$,故 $e(a_7)=ve(3)=5$, $l(a_7)=vl(6)-a_7=6$;
• 对于活动 $a_8$,弧起点为 $4$,弧终点为 $6$,故 $e(a_8)=ve(4)=5$, $l(a_8)=vl(6)-a_8=7$;
• 对于活动 $a_9$,弧起点为 $5$,弧终点为 $7$,故 $e(a_9)=ve(5)=6$, $l(a_9)=vl(7)-a_9=6$;
• 对于活动 $a_{10}$,弧起点为 $6$,弧终点为 $8$,故 $e(a_{10})=ve(6)=8$, $l(a_{10})=vl(8)-a_{10}=10$;
• 对于活动 $a_{11}$,弧起点为 $6$,弧终点为 $7$,故 $e(a_{11})=ve(6)=8$, $l(a_{11})=vl(7)-a_{11}=9$;
• 对于活动 $a_{12}$,弧起点为 $7$,弧终点为 $9$,故 $e(a_{12})=ve(7)=12$, $l(a_{12})=vl(9)-a_{12}=12$;
• 对于活动 $a_{13}$,弧起点为 $8$,弧终点为 $9$,故 $e(a_{13})=ve(8)=12$, $l(a_{13})=vl(9)-a_{13}=14$.

计算活动的最早开始时间和最迟开始时间如下表:

(2) 完成此工程至少需要时间的为 $\color{Red}{16}$(即事件 $V_9$的最早发生时间或最迟发生时间)

(3) 关键路径为 $\color{Red}{(V_1,V_3,V_5,V_7,V_9)}$

(4) 活动 $\color{Red}{a_2,a_6,a_9,a_{12}}$加速可以缩短完成工程所需的时间.

6.4.5

下表给出了某工程各工序之间的优先关系和各工序所需的时间(其中-表示无先驱工序),请完成以下各题:

1. 画出相应的 $AOE$网.
2. 列出各事件的最早发生时间和最迟发生时间.
3. 求出关键路径并指明完成该工程所需的最短时间.

(1) $AOE$图如下:

计算关键路径

拓扑序列为 $1,2,3,4,5,6$( $2,3$可交换, $4,5$可交换)

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $V_1$,由于 $V_1$是源点,故 $ve(1)=0$;
• 对于事件 $V_2$,仅存在从 $V_1$到 $\color{Red}{V_2}$的边 $A=3$,故 $ve(2)=ve(1)+A=3$;
• 对于事件 $V_3$,仅存在从 $V_1$到 $\color{Red}{V_3}$的边 $B=2$,故 $ve(3)=ve(1)+B=2$;
• 对于事件 $V_4$,存在从 $V_2$到 $\color{Red}{V_4}$的边 $C=2$和从 $V_3$到 $\color{Red}{V_4}$的边 $E=4$, 两者取最大值,故 $ve(4)=max(ve(2)+C,ve(3)+E)=max(5,6)=6$;
• 对于事件 $V_5$,仅存在从 $V_2$到 $\color{Red}{V_5}$的边 $D=3$,故 $ve(5)=ve(2)+D=6$;
• 对于事件 $V_6$,存在从 $V_2$到 $\color{Red}{V_6}$的边 $F=3$、从 $V_4$到 $\color{Red}{V_6}$的边 $G=2$和从 $V_5$到 $\color{Red}{V_6}$的边 $H=1$, 三者取最大值,故 $ve(6)=max(ve(2)+F,ve(4)+G,ve(5)+H)=max(6,8,7)=8$.

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $V_6$,由于 $V_6$是汇点,故 $vl(6)=ve(6)=8$;
• 对于事件 $V_5$,仅存在从 $\color{Green}{V_5}$到 $V_6$的边 $H=1$,故 $vl(5)=vl(6)-H=7$;
• 对于事件 $V_4$,仅存在从 $\color{Green}{V_4}$到 $V_6$的边 $G=2$,故 $vl(4)=vl(6)-G=6$;
• 对于事件 $V_3$,仅存在从 $\color{Green}{V_3}$到 $V_4$的边 $E=4$,故 $vl(3)=vl(4)-E=2$;
• 对于事件 $V_2$,存在从 $\color{Green}{V_2}$到 $V_4$的边 $C=2$、从 $\color{Green}{V_2}$到 $V_5$的边 $D=3$和从 $\color{Green}{V_2}$到 $V_6$的边 $F=3$,三者取最小值,故 $vl(2)=min(vl(4)-C,vl(5)-D,vl(6)-F)=min(4,4,5)=4$;
• 对于事件 $V_1$,存在从 $\color{Green}{V_1}$到 $V_2$的边 $A=3$和从 $\color{Green}{V_1}$到 $V_3$的边 $B=2$,两者取最小值,故 $vl(1)=min(vl(2)-A,vl(3)-B)=min(1,0)=0$.

(2) 计算事件的最早发生时间和最迟发生时间如下表:

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $A$,弧起点为 $1$,弧终点为 $2$,故 $e(A)=ve(1)=0$, $l(A)=vl(2)-A=1$;
• 对于活动 $B$,弧起点为 $1$,弧终点为 $3$,故 $e(B)=ve(1)=0$, $l(B)=vl(3)-B=0$;
• 对于活动 $C$,弧起点为 $2$,弧终点为 $4$,故 $e(C)=ve(2)=3$, $l(C)=vl(4)-C=4$;
• 对于活动 $D$,弧起点为 $2$,弧终点为 $5$,故 $e(D)=ve(2)=3$, $l(D)=vl(5)-D=4$;
• 对于活动 $E$,弧起点为 $3$,弧终点为 $4$,故 $e(E)=ve(3)=2$, $l(E)=vl(4)-E=2$;
• 对于活动 $F$,弧起点为 $2$,弧终点为 $6$,故 $e(F)=ve(2)=3$, $l(F)=vl(6)-F=5$;

• 对于活动 $G$,弧起点为 $4$,弧终点为 $6$,故 $e(G)=ve(4)=6$, $l(G)=vl(6)-G=6$;

• 对于活动 $H$,弧起点为 $5$,弧终点为 $6$,故 $e(H)=ve(5)=6$, $l(H)=vl(6)-H=7$.

计算活动的最早开始时间和最迟开始时间如下表:

(3) 关键路径为 $\color{Red}{(V_1,V_3,V_4,V_6)}$,完成该工程所需的最短时间为 $\color{Red}{8}$(即事件 $V_6$的最早发生时间或最迟发生时间)

6.4.6

试说明利用 $DFS$如何实现有向无环图拓扑排序.

$DFS$ 总是沿着一条路搜索到底，然后逐层回退，因此 $DFS$也适合拓扑排序，并且可以在回退的过程中保存下拓扑排序的逆序 .

int vis[MaxVertexNum];//1代表正在访问,-1代表访问结束,0代表未访问
int ans[MaxVertexNum],tot;

bool dfs_topsort(ALGraph G,int root)
{
    vis[root]=1;//正在访问
    for(int j=FirstNeighbor(G, root);j!=-1;j=NextNeighbor(G, root, j))
    {
        if(vis[j]==1)//如果后继比前驱先访问,说明存在环
            return false;
        if(vis[j]==0&&dfs_topsort(G, j)==false)//如果后继未被访问,访问后继返回假,也是失败
            return false;
    }

    vis[root]=-1;
    ans[tot++]=root;//在递归结束才加入拓扑序列数组中,最深层次先返回
    return true;
}

for(int i=1;i<=alg.vexnum;i++)
    if(vis[i]==0)
        dfs_topsort(alg,i);
for(int i=tot-1;i>=0;i--)
    cout << alg.vertices[ans[i]].data << " ";
cout << endl;

书上做法:

6.4.7

一连通无向图,边非负权值,问用 $Dijkstra$最短路径算法能否给出一棵生成树,该树是否一定是最小生成树?说明理由.

$Dijkstra$最短路径算法能够给出一棵生成树,但该树不一定为最小生成树.虽然 $Dijkstra$算法和 $Prim$算法的思路与步骤较为相似,但两者的更新算法不一致,而其余部分完全一致.( $Dijkstra$算法是局部最优, $Prim$算法是全局最优)

• 在 $Dijkstra$算法中,对应的 $min$更新算法为:

if(dist[j]>dist[k]+g[k][j])
    dist[j]=dist[k]+g[k][j];

• 在 $Prim$算法中,对应的 $min$更新算法为:

if(dist[j]>g[k][j])
    dist[j]=g[k][j]

对于以下的带权连通无向图

用 $Dijkstra$算法构造的一棵生成树为:

用 $Prim$算法构造的一棵生成树为:

在 $Dijkstra$算法的执行过程中,从 $1$到 $3$的最短路径选择的是 $1 \to 3$,而不是 $1 \to 4 \to 3$(或 $1 \to 2 \to 3$),原因是 $dist[3]=dist[4]+g[4][3]=dist[2]+g[2][3]$,即 $1$到 $3$的初始最短距离与 $1$到 $4$的最短路径加上 $4$到 $3$的距离(或$1$到 $2$的最短路径加上 $2$到 $3$的距离)相等,因为在更新过程中保留 $1 \to 3$的最短路径为 $1 \to 3$而非 $1 \to 4 \to 3$(或 $1 \to 2 \to 3$).构造的生成树的边权值之和为 $1+4+6=11$,远大于用 $Prim$算法构造的最小生成树边权值之和 $1+2+4=7$.

6.4.8

2009统考真题：带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径.假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:

1. 设最短路径初始时仅包含初始顶点,令当前顶点 $u$为初始顶点.
2. 选择离 $u$最近且尚未在最短路径中的一个顶点 $v$,加入最短路径,修改当前顶点 $u=v$.
3. 重复步骤 2,直到 $u$是目标顶点为止.

请问上述方法能否求得到最短路径？若该方法可行,请证明;否则,请举例说明.

该方法不一定能求得最短路径.

对于下图所示的带权图,若按照题中的原则,从 $A$到 $C$的最短路径是 $A \to B \to C$,实际上是 $A \to D \to C$.

6.4.9

2011统考真题：已知有 $6$个顶点(顶点编号为 $0 \sim 5$)的有向带权图 $G$,其邻接矩阵 $A$为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中.

要求:

1. 写出图 $G$的邻接矩阵 $A$.
2. 画出有向带权图 $G$.
3. 求图 $G$的关键路径,并计算该关键路径的长度.

(1) 图 $G$的邻接矩阵如下

（2) 有向带权图 $G$如下

(3)计算关键路径

拓扑序列为 $0,1,2,3,4,5$( $3,4$可交换)

首先计算事件最早发生时间 $ve()$(考虑到达 $V_i$的边)

• 对于事件 $0$,由于 $0$是源点,故 $ve(0)=0$;
• 对于事件 $1$,仅存在从 $0$到 $\color{Red}{1}$的边 $a_{01}=4$,故 $ve(1)=ve(0)+a_{01}=4$;
• 对于事件 $2$,存在从 $0$到 $\color{Red}{2}$的边 $a_{02}=6$和从 $1$到 $\color{Red}{2}$的边 $a_{12}=5$, 两者取最大值,故 $ve(2)=max(ve(0)+a_{02},ve(1)+a_{12})=max(6,9)=9$;
• 对于事件 $3$,仅存在从 $2$到 $\color{Red}{3}$的边 $a_{23}=4$,故 $ve(3)=ve(2)+a_{23}=13$;
• 对于事件 $4$,仅存在从 $2$到 $\color{Red}{4}$的边 $a_{24}=3$,故 $ve(4)=ve(2)+a_{24}=12$;
• 对于事件 $5$,存在从 $3$到 $\color{Red}{5}$的边 $a_{35}=3$和从 $4$到 $\color{Red}{5}$的边 $a_{45}=3$, 两者取最大值,故 $ve(5)=max(ve(3)+a_{35},ve(4)+a_{45})=max(16,15)=16$.

然后计算事件最迟发生时间 $vl()$(考虑从 $V_i$出发的边)

• 对于事件 $5$,由于 $5$是汇点,故 $vl(5)=ve(5)=16$;
• 对于事件 $4$,仅存在从 $\color{Green}{4}$到 $5$的边 $a_{45}=3$,故 $vl(4)=vl(5)-a_{45}=13$;
• 对于事件 $3$,仅存在从 $\color{Green}{3}$到 $5$的边 $a_{35}=3$,故 $vl(3)=vl(5)-a_{35}=13$;
• 对于事件 $2$,存在从 $\color{Green}{2}$到 $3$的边 $a_{23}=4$和从 $\color{Green}{2}$到 $4$的边 $a_{24}=3$,两者取最小值,故 $vl(2)=min(vl(3)-a_{23},vl(4)-a_{24})=min(9,10)=9$;
• 对于事件 $1$,仅存在从 $\color{Green}{1}$到 $2$的边 $a_{12}=5$,故 $vl(1)=vl(2)-a_{12}=4$;
• 对于事件 $0$,存在从 $\color{Green}{0}$到 $1$的边 $a_{01}=4$和从 $\color{Green}{0}$到 $2$的边 $a_{02}=6$,两者取最小值,故 $vl(0)=min(vl(1)-a_{01},vl(2)-a_{02})=min(0,3)=0$.

计算事件的最早发生时间和最迟发生时间如下表:

接着计算活动最早开始时间 $e()$和最迟开始时间 $l()$(最早看弧起点,最迟看弧终点)

• 对于活动 $a_{01}$,弧起点为 $0$,弧终点为 $1$,故 $e(a_{01})=ve(0)=0$, $l(a_{01})=vl(1)-a_{01}=0$;
• 对于活动 $a_{02}$,弧起点为 $0$,弧终点为 $2$,故 $e(a_{02})=ve(0)=0$, $l(a_{02})=vl(2)-a_{02}=3$;
• 对于活动 $a_{12}$,弧起点为 $1$,弧终点为 $2$,故 $e(a_{12})=ve(1)=4$, $l(a_{12})=vl(2)-a_{12}=4$;
• 对于活动 $a_{23}$,弧起点为 $2$,弧终点为 $3$,故 $e(a_{23})=ve(2)=9$, $l(a_{23})=vl(3)-a_{23}=9$;
• 对于活动 $a_{24}$,弧起点为 $2$,弧终点为 $4$,故 $e(a_{24})=ve(2)=9$, $l(a_{24})=vl(4)-a_{24}=10$;
• 对于活动 $a_{35}$,弧起点为 $3$,弧终点为 $5$,故 $e(a_{35})=ve(3)=13$, $l(a_{35})=vl(5)-a_{35}=13$;
• 对于活动 $a_{45}$,弧起点为 $4$,弧终点为 $5$,故 $e(a_{45})=ve(4)=12$, $l(a_{45})=vl(5)-a_{45}=13$;

计算活动的最早开始时间和最迟开始时间如下表:

综上,关键路径为 $\color{Red}{(0,1,2,3,5)}$,关键路径长度为 $\color{Red}{16}$(即事件 $5$的最早发生时间或最迟发生时间)

6.4.10

2014统考真题：某网络中的路由器运行 $OSPF$路由协议,下表是路由器 $R1$维护的主要链路状态信息( $LSI$), $R1$构造的网络拓扑图(见下图)是根据题下表及 $R1$的接口名构造出来的网络拓扑.

请回答下列问题

1. 本题中的网络可抽象为数据结构中的哪种逻辑结构?
2. 针对表中的内容,设计合理的链式存储结构,以保存表中的链路状态信息( $LSI$).要求给出链式存储结构的数据类型定义,并画出对应表的链式存储结构示意图(示意图中可仅以 $ID$标识结点).
3. 按照 $Dijkstra$算法的策略,依次给出 $R1$到达子网 $192.1.x.x$的最短路径及费用.

(1) 无向图/网状结构/非线性结构

(2)

typedef struct LinkNode 
{ 
    unsigned int ID; //所连路由器的 Router ID 
    unsigned int IP; //本地 IP 地址 
}LinkNode; //Link 的结构 
typedef struct NetNode 
{ 
    unsighed int Prefix; //IP 前段 
    unsighed int Mask; //掩码 
}NetNode; //Net 的结构 
typedef struct ArcNode 
{ 
    int Flag; //当 Flag=1 时， 表示 Link； 当 Flag=2 时，表示 Net 
    union 
    { 
        LinkNode Lnode; 
        NetNode Nnode; 
    }LinkORNet; //用 union 定义 Link 结点和 Net 结点 
    unsighed int Metric; //费用 
    struct ArcNode * Next; //用于指向下一个弧结点的指针 
}ArcNode; //弧结点的结构 
typedef struct HNode 
{ 
    unsighed int RouterID; //路由器的 Router ID 
    ArcNode * LN_link; //用于指向弧结点的指针 
    struct HNode * Next; //用于指向下一个表头结点的指针 
}HNode; //表头结点的结构 

(3) 计算结构如下图所示.

6.4.11

2017统考真题：使用 $Prim$算法求带权连通图的最小(代价)生成树( $MST$).请回答下列问题:

1. 对下列图 $G$,从顶点 $A$开始求 $G$的 $MST$,依次给出按算法选出的边.
2. 图 $G$的 $MST$是唯一的吗?
3. 对任意的带权连通图,满足什么条件时,其 $MST$是唯一的?

(1)

• 选择 $(A,D)$
• 选择 $(D,E)$
• 选择 $(C,E)$(不能选择 $(A,E)$,会构成环)
• 选择 $(B,C)$

(2) 图 $G$的 $MST$是唯一的.由于该最小生成树包括了图中权值最小的 $4$条边,其他边除 $(A,E)$外都比 $4$条边大,但若用 $(A,E)$替换同权值的 $(C,E)$, $A,D,E$三个顶点构成了回路.因此不能替换,所以此图的 $MST$唯一.

(3) 当带权连通图的任意一个环中所包括的边的权值均不相同时,其 $MST$是唯一的.

6.4.12

2018统考真题：拟建设一个光通信骨干网络连通 $BJ,CS,XA,QD,JN,NJ,TL$和 $WH$等 $8$个城市.下图中无向边上的权值表示两个城市之间备选光缆的铺设费用.(猜测 $8$个城市分别是 北京,长沙,西安,青岛,济南,南京,铁岭,武汉)

1. 仅从铺设费用角度出发,给出所有可能的最经济的光缆铺设方案(用带权图表示),并计算相应方案的总费用.
2. 该图可采用图的哪种存储结构?给出求解问题 $1$所用的算法名称.
3. 假设每个城市采用一个路由器按 $1$中得到的最经济方案组网,主机 $H1$直接连接在 $TL$的路由器上,主机 $H2$直接连接在 $BJ$的路由器上,若 $H1$向 $H2$发送一个 $TTL=5$的 $IP$分组,则 $H2$是否可以收到该 $IP$分组?

(1) 方案如下,两种方案的总费用均为为 $2\times 5 + 3\times 2=16$.

(2) 存储结构为邻接矩阵(或邻接表) ,算法名称为 $Kruskal$算法(或 $Prim$算法).

(3) $IP$分组每经过一个路由器 $R$的转发,其头部中的生存时间 $TTL$字段的值减 $1$,当 $TTL$字段的值减少到 $0$时路由器会丢弃该 $IP$分组并给源主机发送时间超过类型的 $ICMP$差错报告报文.

• 对于方案 $1$,主机 $H1$给 $H2$发送 $IP$分组, $IP$分组的转发路径为 $H1 \to R_{TL} \to R_{JN} \to R_{QD} \to R_{WH} \to R_{XA} \to R_{BJ} \to H2$, $IP$分组从 $H1$发出时其 $TTL=5$,当该分组转发进入 $R_{XA}$路由器时,其 $TTL=0$,该分组会被 $R_{XA}$路由器丢弃,因此 $H2$不能收到该 $IP$分组.

• 对于方案 $2$,主机 $H1$给 $H2$发送 $IP$分组, $IP$分组的转发路径为 $H1 \to R_{TL} \to R_{BJ} \to H2$, $IP$分组从 $H1$发出时其 $TTL=5$,中途只需经过 $R_{TL}$和 $R_{BJ}$两个路由器,因此主机 $H2$可以收到该 $IP$分组.