图的表示
图的记号是G = (V, E), 可以用两种数据结构表示: 邻接链表和邻接矩阵;
- note: 实际应用中一般必须是用一个Vertex V[VNUM]一维数组来存放结点, 用一个二维矩阵w[VNUM][VNUM]或者邻接链表来存放权重值;
邻接链表
- 构成: |V|条链表构成的数组Adj, 其中某个结点的链表是Adj[u];
- 存储空间: 有|V|条链表占据Θ(V), 这些链表的结点加起来总共要有|E| 条 或者 |2E| 个结点, 那么是Θ(E), 所以合起来就是Θ(V+E);
- 优点: 邻接链表比较紧凑节省空间, 适合稀疏图(E远小于V^2), 因此多数算法都假设图是用邻接链表来表示的.
- 缺点: 无法快速判断u, v两个结点之间是否有边(u, v), 只能在Adj[u]中搜索一下链表;
邻接矩阵
- 构成: |V| × |V| 矩阵来表示两两结点之间的边的情况;
- 存储空间: Θ(V^2)
- 优点: 在稠密图(E接近V^2)情况下, 邻接矩阵更好; 邻接矩阵能满足快速判断任意两个节点之间是否有边的需求;
- 缺点:更大的存储空间消, 高了一个阶;
广度优先搜索(BFS)
算法
BFS(G, s)
/*初始化*/
for each vertex u ∈ G.V - {s}
u.color = white;
u.pr = null;
u.d = ∞;
s.color = gray;
s.pr = null;
s.d = 0;
Q = ∅; //Queue is empty;
Enqueue(Q, s);
/*搜索*/
while (Q != ∅)
u = Dequeue(Q); //take u off from queue head;
for each v of G.Adj[u]
if (v.color == white)
v.color = gray;
v.pr = u;
v.d = u.d+1;
Enqueue(Q, v); //push v into the queue tail;
u.color = black; //u's job is done;
- 算法运行时间分析:
- 初始化阶段: Θ(V);
- while循环里, 每个节点都要出队一次, 且每个节点都要对其的边进行一番探测, 那么对有向图来说, 也就是V个节点, 探测总共E个边, 耗时Θ(V+E);
BFS性质: 其算法能够正确计算出任意结点的最短路径距离δ
(1) 最短路径距离性质: 对于边(u, v)∈E, 有δ(s, v) ≤ δ(s, u)+1;
证明: 如果s能够到达u, 也能到达v, 且存在边(u, v), 则从s到v的最短路径距离不可能比s到u的最短路径加上边还要长; 若s无法到达u, 则δ(s, u)=∞, 那么性质也成立;
接下去, 为了证明BFS算出的v.d = δ(s, v), 我们先证v.d≥, 再证≤;
(2) BFS算出的v.d ≥ δ(s, v);
证明: (数学归纳法, 对全过程进行观察)
① 初始化时: for s, s.d = δ(s,s) = 0; for each v∈G.V - {s}, v.d = ∞ >= δ(s, v);
② 在BFS运算时: assume u has u.d >= δ(s, u).
when u just does its dequeue, then we see that for edge(u, v), the BFS algorithm says
v.d = u.d+1 ≥ δ(s, u)+1 [this is our assumption] ≥ δ(s, v) [cuz edge(u,v)exists, and we have property (1)].
And after this operation, node v's color turns gray and v.d no longer changes.
Thus we prove our property(2).
(3) BFS中队列里, 队列中最多包含两个不同的d值, 且队中d值保持升序( v[i].d<=v[i+1].d);
证明: (数学归纳法)
--头部条件:
当只有s在队中时, 只有s.d = 0, 定理满足;
当s离队后, 往队中添加结点的阶段, 添加进的所有s.adj结点都有v.d = 1, 定理也满足, 即v[1]离队前满足了v[r].d=v[1].d=1 <= v[1].d+1 和 v[i].d = v[i+1].d = 1 <=v[i+1].d;
原v[1]离队后, 往队中添加新结点的阶段, 添加进的结点都满足v.d = 原v[1].d +1 = 2 <= v[2].d+1, 我们把原先的v[2]看成新v[1], 即显然仍有v[r].d<=新v[1].d+1成立; 且我们知道现在v[1]~v[k]有d = 1, v[k+1]~v[r]有d = 2, 所以必有v[i].d <= v[i+1].d;
--归纳阶段:
假设当u离队前, 定理是满足的, 把u记作v[1], 即v[r].d <= v[1].d+1成立; 同时假设v[i].d <= v[i+1].d也成立, 那么就有v[1].d <= v[2].d;
当u出队, 往队中添加元素的时候, 每个新加入的结点都有v.d = u.d+1 <= 原v[2].d+1, 把原v[2]记成新的v[1], 那么也就是说v[r].d <= v[1]+1仍然成立;
再看第二个假设, 对队列中原先部分, 继续成立; 对队列中原先和新加部分交界处, 已知原v[r].d <= 原v[1].d + 1<= 原v[2]+1, 现在新加入的v=u+1=原v[1].d+1>=原v[r].d, 因此交接部分也有v[i]<=v[i+1]成立; 而对新加部分内, 则有v[i] = v[i+1], 仍然是符合v[i]<=v[i+1];
综上, 初始条件和归纳阶段都成立, 因此定理成立;
(4) BFS求出的v.d = δ(s, v)
已知所有v∈V都是s通过BFS算法发现的结点, 即s能到达所有的v;
证明: (反证法)
假设存在v.d != δ(s, v), 由v.d>=δ(s,v)定理, 得v.d>δ(s,v);
那么这样的存在会有两种情况: 要么图中存在一部分结点的v.d>δ(s,v), 要么图中所有结点都有v.d>δ(s,v).
--后者显然不可能, 因为至少边(s->a)能使得a结点满足a.d = δ(s, a);
--看前者情况, 在s出发的一条路径上, u之前的结点正常, 而从v开始往后的结点都出现了v.d>δ(s,v), 那唯一的可能就是因为结点v被另外一个更短的路径给连接了, 此时其实是意味着BFS算法更长的路径推进得比最短路径还快了两个身位, 注意他们的头都是灰色的, 这与队列d值只能同时保持两个是矛盾的.
----也可以这么证: 在s到v的最短路径上, 前一个结点为x, 那么x.d = δ(s, x), 且δ(s, v) = δ(s, x)+1(已经明确说了这就是最短路径), 已知v.d > δ(s, v) = δ(s, x)+1 = x.d+1, 这也就是我们上述所言的v被更长的路径首先探索到的问题. 让我们从x探索的角度看下为什么这不可能:
若在x探索到v时, v是白色, 那么v.d = x.d +1, 矛盾;
若v是黑色, 而此时x还是灰色, 也就是说v比x还先要出队, 那么v.d <= x.d, 矛盾;
若v是灰色, 那么v肯定被某结点u已经先探索了, 则u比x先进了队列, 满足u.d <= x.d, 那么v.d = u.d+1 <= x.d+1, 矛盾;
综上, 在BSF算法能探测到的每个结点v, v.d = δ(s, v)必定成立;
深度优先搜索
DFS(G) {
/*初始化*/
for each vertex u in G.V
u.color = white
u.pr = null;
time = 0 //init time;
for each vertex u in G.V
if (u.color == white)
DFS-Visit(G, u);
}
DFS-Visit(G, u) {
time = time+1;
u.d = time;
u.color = gray;
for each v of G.Adj[u]
if v.color == white
v.pr = u
DFS-Visit(G, v);
u.color = black;
time = time+1;
u.f = time;
}
- 算法运行时间分析:
- 初始化每个结点: Θ(V);
- 每个结点都会有入队和出队操作, Θ(V); 所有的vertex都将其边探索到底, 导致所有的Edge都被检查, Θ(E);
- 合计Θ(V+E);
DFS的重要性质
- 括号化: 对两个结点u, v来说, 只有三种可能性: 区间分离, 区间u包含v, 区间v包含u;
- 白色路径: v是u的后代 ↔ 在发现u的时候u.d, 能存在一条结点u到v的全部由白色结点所构成的路径;
- 边的分类: 当第一次探索到边(u, v)时, v为白->树边; v为灰->后向边; v为黑->前向边或者横向边;
拓扑排序
Topological-sort(G)
count finish time for each vertex using DFS(G);
once a vertex is finished (marked black), insert it into the linkedList;
return the linkedList
- 拓扑序定义: 若图G包含边(u, v), 则u结点在序中总是在v结点前面;
- 该定义直接推导出: 图G若能生成拓扑序, 必须是有向无环图;
证明: (反证法) 如果是有环, 则有u->v, 也有v->u, 那么拓扑序中不可能既满足u结点在v前面, 又满足v结点在u前面, 形成矛盾;
- TS算法正确性: 对有向无环图, TS算法能生成拓扑排序;
证明: 因为我们算法第二行使得返回序列是按照结束时间f的逆序排列(前大后小), 因此只要证明若边(u, v)存在于G图中, 则总有u.f>v.f成立就可以;
(分类讨论)利用DFS性质中边的分类, 对任意一条存在于G中的边(u, v)进行讨论, 若该边在DFS中被探索到时,
(1) 若v结点是灰色, 则是后向边, 与给定的有向无环图条件矛盾(后向边会形成环), 因此不可能存在;
(2) 若v结点是白色, 则这是树边, 由白色路径定理, v是u的子结点, 再由括号化定理, 知道u.f > v.f, 命题成立;
(3) 若v结点是黑色, 则这是前向边或者横向边, 此时v结点已经被打上时间戳, 而u尚未结束, 那么u.f>v.f成立, 命题也成立;
所以, 只要前提条件 有向无环图成立, TS算法总能生成拓扑序;
强连通分量(Strongly connected components)
Strongly-connected-components(G)
1. call DFS(G) to compute finish time for each vertex in the graph;
2. compute G<t> (reverse the direction of all edges);
3. call DFS(G<t>), but from latest finish time to earliest at the main loop;
4. the trees that formed by second DF, are the components we look for;
正确性证明:
(1) C和C', 假如有u->u', 不可能有v'->v, 因为如果能够实现的话, 那么这两个分量任意元素都能实现互相到达对方, 那么C和C'可以合为一个分量;
(2) C和C', 如果有u->u', 那么f(C')<f(C); 而对G<T>, 则是f(C)<f(C');
证明: (分类讨论)如果若DFS从C的x节点开始, 那么最后就是x.f > max{Cnodes.f }, 则f(C)>f(C');
如果DFS从C'的y节点先开始, 那么就是先visit完C'的结点, 且C'无法到达C, 之后DFS再对C开始运算, 那么就得到f(C)>f(C');
对于G<T>, 同理成立;
(3) SCC算法能够得到G<SCC>
证明: 可以把各个求出的分量看做n个结点, 如果算法第三行对G<t>进行DFS运算能够形成n个独立的树够成的一片森林的话, 那么算法就是正确的.
数学归纳法:
算法第三行的操作是, 按照拓扑序(C.f > C'.f, 则C在前)来对n个结点进行DFS, 注意这里G中的所有边都已经被反向过;
a. 当n=1时, 显然森林只有一棵树, 命题成立;
b. 假设当n>1时, 一般地, 对拓扑序中的C和C'来说, 那么如果先对C进行DFS, 由于C没有边能到拓扑序的下一个结点C'(在G中C->C', 但是已经边被反向了), 所以C单独成了一棵树, DFS在C的运算不会对C'有任何操作. 以此类推, 算法能连续生成n棵独立的树;
