图的连通性问题

无向图的连通分量

图是否连通的判断：是否仅调用一次搜索过程。
图的连通分量：每次调用得到的顶点序列恰为各连通分量的顶点集。调用搜索过程的次数就是连通分量的个数。

图中两个顶点之间的简单路径

顶点u到顶点v的简单路径：路径中的顶点均不相同。
[算法思想] 有无：从顶点u开始，进行深度(或广度)优先搜索，如果能搜索到顶点v，则表明从顶点u到顶点v有一条路径。是否是简单路径：由于在搜索过程中每个顶点只访问一次，所以这条路径必定是一条简单路径。记录：在搜索过程中，把搜索的线路记录下来，搜索到v退出即可得到简单路径。
记录搜索线路：设置一个数组pre[n]，当从某个顶点vi找到其邻接点vj进行访问时，将pre[j]置i，即pre[j]=i。这样，当退出搜索后，就能根据pre数组从顶点v追溯到顶点u，从而输出这条从u到v的简单路径。
访问标识：pre[j]=-1表示vj未访问，否则表示vj已访问。

图的生成树与最小生成树

(1) 连通图的生成树
连通图的生成树：所有顶点均由边连接在一起，但不存在回路的子图。

连通图的生成树是一个极小连通分量。n个顶点的连通图的生成树有n-1条边。连通图可以有不同的生成树。

极小+连通分量：
子图多余n-1条边，则一定有回路，不是极小连通分量，不是生成树。子图少于n-1条边，则一定是非连通图，不是生成树。子图有n-1条边也并非一定连通，不一定是生成树。

两种特殊的生成树：深度优先生成树、广度优先生成树


生成森林：非连通图每个连通分量的生成树

(2) 最小生成树
① 最小生成树（MST）
在一个连通网的所有生成树中，各边代价之和最小的那棵生成树。
最小代价生成树简称最小生成树
各边代价之和：各边权值之和
② MST的性质
设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。如果顶点u∈U，v∈V-U，且(u,v)是一条具有最小权值的边，则存在一棵包含边(u,v)的最小生成树。

问题提出：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路。
如何在最节省经费的前提下建立这个通讯网？
问题分析：在n条带权的边中选取n-1条(不构成回路)，使“权值之和”为最小，即构造网的一棵最小生成树。

(3) 普里姆(Prim)算法：加点法
假设N=(V,{E})是连通网，TE为最小生成树中边的集合。
① 初始U={u0} (u0∈V)，TE=∅；
② 在所有u∈U，v∈V-U的边中选一条代价最小的边(u0,v0)并并入集合TE，同时将v0并入U；
③ 重复②，直到U=V。
注：prim算法的最小生成树不唯一。


(4) 克鲁斯卡尔(Kruskal)算法：加边法
假设N=(V,{E})是连通网。
① 将n个顶点看成n个连通分量(集合)；
② 按权值从小到大的顺序选择边，若该边依附的顶点位于不同的连通分量，则加入此边，否则舍去此边，选取下一条代价最小的边；
③ 重复②，直到所有顶点都处于同一连通分量。

有向无环图的应用

有向无环图(DAG)：是指一个无环的有向图。
有向无环图的应用：可用来描述工程或系统的进行过程。

拓扑结构

(1) AOV-网
用顶点表示活动，用弧表示活动的优先关系的有向无环图，称为顶点表示活动的网，简称AOV-网。
应用：工程应该按什么样的活动序列进行，才能保证工程的顺利进行？


(2) 拓扑排序
把AOV-网中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。
拓扑排序的基本思想：
① 从有向图中选一个无前驱的结点输出;
② 将此结点和以它为起点的边删除;
③ 重复①、②，直到不存在无前驱的结点。


AOV-网的先行关系具有传递性。
AOV-网的拓扑序列不是唯一的。


有向图中是否有回路：拓扑排序输出结点数小于有向图中的顶点数。

关键路径

(1) AOE-网
用顶点表示事件，用弧表示活动，用弧的权值表示活动所需要的时间的有向无环图，称为边表示活动的网，简称AOE-网。
应用：那些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？
(2) 关键路径
源点：AOE-网中存在唯一的、入度为0的顶点。
汇点： AOE-网中存在唯一的、出度为0的顶点。
关键路径：从源点到汇点具有最大长度的路径。
关键活动：关键路径上的活动。

关键路径：v0、v1、v4、v6、v8
v0、v1、v4、v7、v8
关键活动：a1、a4、a7、a10
a4、a5、a8、a11
意义：只有缩短工程关键路径上关键活动持续时间，才能加快工程进度。
(3) 时间的几个定义
① 事件vi的最早发生时间ve(i)
是从源点到顶点vi的最长路径长度。
从源点开始，按拓扑顺序递推：
ve(0)=0
ve(i)=max{ve(k)+duk(<k,i>)}
其中<k,i>∈T，1≤i≤n-1
T为所有以i为弧头的弧<k,i>的集合，dut(<k,i>)表示弧<k,i>对应活动的持续时间。

各事件的最早发生时间？
ve(0)=0
ve(1)=max{ve(0)+dut(<0,1>)}=6
ve(2)=max{ve(0)+dut(<0,2>)}=4
ve(3)=max{ve(0)+dut(<0,3>)}=5
ve(4)=max{ve(1)+dut(<1,4>), ve(2)+dut(<2,4>)}=7
ve(5)=max{ve(3)+dut(❤️,5>)}=7
ve(6)=max{ve(4)+dut(<4,6>)}=16
ve(7)=max{ve(4)+dut(<4,7>), ve(5)+dut(<5,7>)}=14
ve(8)=max{ve(6)+dut(<6,8>), ve(7)+dut(<7,8>)}=18
② 事件vi的最晚发生时间vl(i)
在保证汇点按其最早发生时间的前提下，事件vi的最晚发生时间。
从汇点开始，按逆拓扑顺序递推：
vl(n-1)=ve(n-1)
vl(i)=min{vl(k)-duk(<i,k>)}
其中<i,k>∈S，1≤i≤n-1
S为所有以i为弧尾的弧<i,k>的集合，dut(<i,k>)表示弧<i,k>对应活动的持续时间。

各事件的最晚发生时间？
vl(8)=ve(8)=18
vl(7)=min{vl(8)-dut(<7,8>)}=14
vl(6)=min{vl(8)-dut(<6,8>)}=16
vl(5)=min{vl(7)-dut(<5,7>)}=10
vl(4)=min{vl(6)-dut(<4,6>),vl(7)-dut(<4,7>)}=7
vl(3)=min{vl(5)-dut(❤️,5>)}=8
vl(2)=min{vl(4)-dut(<2,4>)}=6
vl(1)=min{vl(4)-dut(<1,4>)}=6
vl(0)=min{vl(1)-dut(<0,1>),vl(2)-dut(<0,2>),vl(3)-dut(<0,3>)}=0
③ 活动ai的最早开始时间e(i)
如果活动ai对应的弧为<j,k>，则e(i)等于从源点到顶点j的最长路径，即e(i)=ve(j)。


各活动的最早发生时间？
e(a1)=ve(0)=0
e(a2)=ve(0)=0
e(a3)=ve(0)=0
e(a4)=ve(1)=6
e(a5)=ve(2)=4
e(a6)=ve(3)=5
e(a7)=ve(4)=7
e(a8)=ve(4)=7
e(a9)=ve(5)=7
e(a10)=ve(6)=16
e(a11)=ve(7)=14
④ 活动ai的最晚开始时间l(i)
如果活动ai对应的弧为<j,k>，其持续时间为dut(<j,k>)，则有l(i)=vl(k)-dut(<j,k>)。


各活动的最晚发生时间？
l(a11)=vl(8)-dut(<7,8>)=14
l(a10)=vl(8)-dut(<6,8>)=16
l(a9)=vl(7)-dut(<5,7>)=10
l(a8)=vl(7)-dut(<4,7>)=7
l(a7)=vl(6)-dut(<4,6>)=7
l(a6)=vl(5)-dut(❤️,5>)=8
l(a5)=vl(4)-dut(<2,4>)=6
l(a4)=vl(4)-dut(<1,4>)=6
l(a3)=vl(3)-dut(<0,3>)=3
l(a2)=vl(2)-dut(<0,2>)=2
l(a1)=vl(1)-dut(<0,1>)=0
④ 活动ai的松弛时间（时间余量）
ai的最晚开始时间与ai的最早开始时间之差，即l(i)-e(i)。


e(ai)
e(a1)=ve(0)=0
e(a2)=ve(0)=0
e(a3)=ve(0)=0
e(a4)=ve(1)=6
e(a5)=ve(2)=4
e(a6)=ve(3)=5
e(a7)=ve(4)=7
e(a8)=ve(4)=7
e(a9)=ve(5)=7
e(a10)=ve(6)=16
e(a11)=ve(7)=14
l(ai)
l(a11)=vl(8)-dut(<7,8>)=14
l(a10)=vl(8)-dut(<6,8>)=16
l(a9)=vl(7)-dut(<5,7>)=10
l(a8)=vl(7)-dut(<4,7>)=7
l(a7)=vl(6)-dut(<4,6>)=7
l(a6)=vl(5)-dut(❤️,5>)=8
l(a5)=vl(4)-dut(<2,4>)=6
l(a4)=vl(4)-dut(<1,4>)=6
l(a3)=vl(3)-dut(<0,3>)=3
l(a2)=vl(2)-dut(<0,2>)=2
l(a1)=vl(1)-dut(<0,1>)=0
l(ai)-e(ai)=0的情形：
a1
a4
a7
a8
a10
a11
得到关键路径

最短路径问题

在已建立好的连通网中，从A城市到B城市走哪条路最省时间或最经济？
这就是最短路径问题。
源点：路径开始的顶点
终点：路径最后的顶点
最短路径的分类：
单源最短路径
每一对顶点间的最短路径

单源最短路径

从某个源点到其余各顶点的最短路径。

迪杰斯特拉(Dijkstra)算法：求解顶点v0到其余各顶点的最短路径。
算法思想：按最短路径长度递增的顺序逐个产生各最短路径。
定理：下一条最短路径=Min(弧(v0,vx),中转路径)
算法步骤：
① 令S={V0}，T={其余顶点}, 计算出v0到T中各结点的路径值;
② 选取最短路径并把对应顶点vk加入到S，此时顶点vk为中转结点;
③ 修正路径值：最短路径=Min(弧(v0,vx),中转路径)
④ 重复②③，直到S中包含所有顶点，即S=V为止。

每一对顶点间的最短路径

方法1：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。
T(n)=O(n*n2)= O(n3)
方法2：弗洛伊德(Floyd)算法。
算法思想：逐个顶点试探法。
算法步骤：
① 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值;否则为∞;
② 逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之;否则,维持原值。
③ 所有顶点试探完毕，算法结束。
弗洛伊德算法:逐个顶点试探法
D：最短路径长度
P：最短路径





欢迎大家加我微信交流讨论（请备注csdn上添加）