(9)|(9) 基本的图算法 (9)基本的图算法

图的表示 【(9)|(9) 基本的图算法】图的记号是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 (reverse the direction of all edges); 3. call DFS(G),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)

证明: (分类讨论)如果若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, 同理成立;

(3) SCC算法能够得到G

证明: 可以把各个求出的分量看做n个结点, 如果算法第三行对G进行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棵独立的树;