图遍历问题¶

DFS¶

DFS structure

dfs(G,v)
    Mark v as “discovered”.
    For each vertex w that edge vw is in G:
        If w is undiscovered:
            dfs(G,w)
        Otherwise:
            “Check” vw without visiting w.
    Mark v as “finished”.

前序 (Pre-Ordered)：first root, second left child-tree last right child-tree 后序 (Post-Ordered) : first left child-tree second right child-tree third root 中序 (In-Ordered): first left child-tree second root third right child-tree

白路径定理 (White Theorem)¶

在一个有向或无向图 G=(V,E) 的深度优先森林中，结点 v 是结点 u 的后裔当且仅当在搜索发现 u 的时刻 d[u]，从结点 u 出发经一条仅由白色结点组成的路径可达 v

思考：对 BFS 成立吗？（习题）白路径定理在BFS是否成立不成立。

活动区间与 Edge 类型¶

在 DFS 框架中嵌入维护遍历时间的操作。遍历时间初始化为 0，当发现新节点，遍历时间 +=1，这一事件记录为该节点发现的时间 discoverTime，每当一个节点遍历结束，同样的遍历时间 +1，这个时间记录为该节点的结束时间 finishTime，

time :=0
Color all nodes WHITE
foreach nove v in G do:
    if v.color = WHITE then
        v.parent=1
        DFS-CLOCK(v)

通过 discoverTime 和 finishTime 我们可以每一个节点的活动区间 active interval，并且可以考察这个区间之间关系和点之间祖孙关系的联系

具体如下面的定理：

定理 8.1¶

考察 DFS 图 G=(V,E) 的过程，对于任意点 v 和 w 1. w 是 v 在 DFS 树中的后继节点，当且仅当 $active(w)\subseteq active(v)$, 若 $w\neq v$, 则此处的包含为真包含 2. w 和 v 没有祖先后继关系，当且仅当 $active(w)\cap active(v)=\emptyset$ 3. 如果 vw 是图 G 中的边，则 1. vw 是 CE，当且仅当 $active(w)$ 在 $active(v)$ 前面 2. vw 是 DE，当且仅当存在第三个节点 $x$, 且满足 $active(w)\subset active(x)\subset active(v)$ 3. vw 是 TE，当且仅当 $active(w)\subset active(v)$ 且不存在第三个节点 $x$ 满足 $active(w)\subset active(x)\subset active(v)$ 4. vw 是 BE，当且仅当 $active(v)\subset active(w)$

强连通分支算法（基于 DFS）¶

对于强连通分支算法的详细说明，这篇知乎专栏很好知乎-Strong Connected Components 其对拓扑序给了一个容易理解的思路

以拓扑排序展示同一个图，所有的节点按照其完成时间的逆序被排成从左向右的一条水平线，所有边都是从左指向右。

DFS 与 DP¶

由于 DFS 的递归性质，我们可以自然的用子树作为子问题，子树可以向下做信息收集。

DAG (有向无环图)¶

构造逆拓扑序¶

构造方法¶

逆拓扑序可以通过对有向无环图(DAG)的 DFS 来构造 Reverse Topological Ordering<-> DAG

具体来说

int dfsTopo(intList[] adjVertices, int[] color, int v int[] topo, int topoNum)
{
    int w;intList remAdj; 
    color[v]=gray;
    while(remAdj!=nil){
        w=first(remAdj);
        if(color[w]==while)
            dfsTopo(adjVertices,color, w, topo, topoNum);
        remAdj=rest(remAdj);
    }
    topoNum++; topo[v]=topoNum;
    color[v]=black;
    return;
}

时间复杂度显然 $\in O(m+n)$

正确性证明¶

The procedure dfsTopo is called exactly once for a vertex, so, the numbers in topo must be distinct in the range 1,2,..., n
For any edge vw, vw can' t be a back edge (otherwise, a circle is formed, contract)
For any other edge types, we have finishTime(v)>finishTime(w), so topo(w) is assigned earlier than topo(v). Note that topoNum is incremented monotonically, so, topo(v) > topo(w), q.e.d

任务规划问题 (Task Scheduling)¶

有一系列任务，他们存在一系列依赖关系——即某个任务 a，只有在一些任务序列（b, c, d）做完之后才可以做，从图论角度解决这种任务规划问题。

无向图¶

Undirected Graph 无向图¶

无向图的 DFS tree¶

在无向图上的 DFS 本质也是有方向的：即它认为所有边都是可以“走”的这为 Undirected Graph' s DFS tree 带来了一些有趣的性质 ![[edges-in-dfs.png]]

这几种 non-tree edge 有什么性质？ - 只有 Back edge 指向的是灰色的点 - Cross edge, Forward edge 指向的都是黑色的点

而无向图在做的时候，“应达尽达”，所以如果 $\exists\text{edge }ab$, 且这条边是 Back edge 或者 Forward edge，则指向的点已经完成了遍历，那么对指向的点做遍历的时候必然已经从另一个方向遍历了这条边。

因此 Undirected Graph DFS tree 只存在 - Tree edge - Back edge

Bi-Connected¶

这里从 node 和 edge 考虑，有两种不同的双连通 - 割点（Articulation point）(2-node connected) - v is an articulation point if deleting v leads to disconnection - 桥 (Bridge)(2-edge connected)

割点¶

割点是一个对于生产应用很重要的概念-研究找它的算法，利用 DFS

割点
- Long Definition If there exist nodes w and x, such that v is in every path from w to x (w!=v, x!=v)
- DFS Definition
  - No back edges linking any vertex in some w-rooted subtree and any ancestor of v
- 这就意味着：如果 v 是割点，则对于一些 node w，它有一条边从 v 指向 w，且以 w 为根的子树都没有指向 v 的祖先的边.

思路就是检索这种 back 关系。为了方便，我们需要维护每个点的 back 值（本质上是最多能 back 到的“时间”）

Updating the value of back
- v first discovered
  - back=discoverTime(v)
- Trying to explore, but a back edge vw from v encountered
  - back=min(back, discoverTime(w))
- Backtracking from w to v
  - back=min(back,wback)
    
    The back value of v is the smallest discover time a back edge “sees” from any subtree of v.

总体而言，v 是割点当且仅当： - v 不是 root 节点 - Some subtree of v has no back edge incident with a proper ancestor of v - 这从数值上体现为：$w.back\geq discover(v)$

桥¶

Short definition
- Removing uv leading to disconnection
Long definition
- Edge uv is a bridge iff node u and v are connected only by uv
DFS definition
- Edge uv is a tree edge in DFS
- There is no subtree rooted at v to any proper ancestor of v (including u)

![[graph-bridge.png|300]]

def BRIDGE-DFS(u):
    u.color=GRAY
    time=time+1
    u.discoverTime=time
    u.back:=u.discoverTime
    foreach neighbor v of u do:
        if v.color=WHITE:
            BRIDGE-DFS(v):
            u.back=min(u.back,v.back)
            if(v.back>u.discoverTime) then:
                Output uv as a bridge
        else:
            if uv is BE:
                u.back=min(u.back,v.discoverTime)
    # v 是 u非父节点的祖先节点

BFS¶

BFS structure¶

Bfs(G,s)
    Mark s as “discovered”;
    enqueue(pending,s);
    while (pending is nonempty)
        v=front(pending);
        dequeue(pending, v);
        For each vertex w that edge vw is in G:
            If w is “undiscovered”
            Mark w as “discovered” and enqueue(pending, w)
        Mark v as “finished”;

在这部分研究一下 BFS，并探讨其 TE, BE, DE, CE 在 BFS 生成图中，和遍历过程 white, gray black 的关系实现上：以点为粒度，跳点是按点的连接关系，广度优先用一个队列（FIFO）来实现。

点的颜色变化： black <- gray in [FIFO] <- white

生成树边情况¶

对于无向图做 BFS 的 edge 情况

Edges	Directed	Undirected
TE	True	True
BE	True	False
DE	False	False
CE	True	True
无向图没有 back edge 的理由和 dfs 是相似的
- 为什么无向图 BFS 没有 Decendent Edge?
- 因为如果其是后继，则会在遍历 parent node 时直接将其压入优先队列，不可能在之后再遍历到。（层级遍历特点）

BFS 检测环¶

与 DFS 天然记录了路径，可以直接查 grey 来查环，不同，BFS 的优势是广度，层级遍历，让人想到可以先记录入度(in-degree)，再 BFS 更新，构造一个队列来做。具体可参考 BFS和DFS查环

图优化问题¶

Best-FS¶

一种框架。

MST 算法¶

Prim' s Algorithm¶

Greedy strategy For each set of fringe vertex, select the edge with the minimal weight , which is local optimal Prim算法以图团去探索边。同时避免了成环。

Prim 算法也是一个在 Best-FS 框架下的代码。利用一个优先队列来做。 我们的优先队列存的是点，所以为了成树，需要用一个 candidate edge 来标记它通过哪条边被连入最小生成树

void primMST(G,n)

    Initialize the priority queue pq as empty;

    //Select vertex s to start the tree;

    //Set its candidate edge to (-1,s,0);即初始点没有candidate edge

    insert(pq,s,0);

    while (pq is not empty)

        v=getMin(pq); deleteMin(pq);

        MST=MST `union` candidate edge of v //加入连接边

        updateFringe(pq,G,v);

    return

void updateFringe(pq,G,v)
    // 加入新点 v，所以加入新的Fringe
    for all vertices w adjcent to v //2m loops

        newWgt=w(v,w);//新的权重

        if w.status is unseen then

            Set its candidate edge to (v,w,newWgt);
            insert(pq,w,newWgt)

        else
            if newWgt<getPriorty(pq,w)
                // 更新candidate边权重
                Revise its candidate edge to (v,w,newWgt);
                decreaseKey(pq,w,newWgt)

    return

优先队列 Priority Queue 可用 Heap or List 实现

分析复杂度¶

Operations on ADT priority queue
- insert: $n$
- getMin: $n$
- deleteMin: $n$
- decreaseKey: $m$ 因为是更新边权重，所以做的次数不会超过边的个数 $m$
故
- $T(n,m)=O(nT(\text{getMin})+nT(\text{deleteMin+insert})+mT(\text{decreaseKey}))$¶

用不同的优先队列实现，会有不同的复杂度情况
如果采用二叉堆形式，所以 insert 和 getMin 都是 $\log n$，最终是 $O((n+m)\log n)$
如果用数组实现，insert cost $1$，getMin 需要 $n$，decreaseKey 需要 $1$ （对于数组，所谓的 decreaseKey 就是改一下加入的新点的该位的值），最后代价是 $n^{2}+m$ 这两种哪个好，需要看点和边的关系。

这里注意，这里仍然取 $\log n$，我们本质在对顶点建堆。

最小生成树性质¶

Minimum Spanning Tree Property： - A spanning tree T of a connected, weighted graph has MST property if and only if for any non-tree edge uv, and $T\cup \{ uv \}$ contain a cycle in which uv is one of the maximum-weight edge.

All the spanning trees having MST property have the same weight. 上图直观展示了对==MST 性质的证明==。

Kruskal Algorithm¶

From the set of edges not yet included in the partially built MST, select the edge with the minimal weight, that is, local optimal, in another sense. Kruskal 算法直观的扫描边集，从中选择权重最小的、不会导致成环的边作为新的边。也是局部最优。

具体来说，Kruskal 算法逐步得到的是 $G$ 的一个局部最小生成森林。加边过程中，算法始终保证不成环，直到最小生成森林中的所有子树全部连通。

怎么高效的 CHECK 是否有环？并查集（Union-Find set）

算法过程¶

void kruskalMST(G,n,F)//outline
    int count;
    <Bulid a minimizing priority queue, pq, of edges of G, priorized by weight>
    //上一步，只需要排序，cost O(mlogm)
    <Initialize a Union Find structure, sets, in which each vertex of G is in its own set.>
    //即每个点都有一个连通分支，如果两个同在一个连通分支中，再连边就成环了

    F=A Empty Set
    while(isEmpty(pq) == false):
        vwEdge = getMin(pq);
        deleteMin(pq);
        int vSet = find(sets, vwEdge.from);
        int wSet = find(sets,vwEdge.to);
        if (vSet != wSet)
            Add vwEdge to F
            union(sets,vSet,wSet)
    return;

分析复杂度¶

对边权值进行排序， cost $O(m\log m)$
并查集：算法需要查询一条边的两个点是否连通，所以会执行 $O(m)$ 条 FIND 和 UNION 指令
- 并查集如果用比较高效的 cFIND + wUnion 形式，复杂度接近线性(反 ackman)，所以最终复杂度就是 $O(m\log m)=O(m\log n)$
- 如果用矩阵，FIND cost 1，UNION cost $O(mn)$

前缀码¶

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 0，1 串表示各字符的最优表示方式。

给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

前缀码

对每一个字符规定一个 0,1 串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。这意味着任意字符的代码的前缀都不是合法的。（电话号码例子：你不能再拨打 11 位电话号码过程中触发 8 位的电话拨打） - 哈夫曼编码 - 编码的前缀性质使得建构编码非常简单。 - 利用 完全二叉树 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有 2 个儿子结点。则此时二叉树每个节点都对应不同的号码，且到他的路径唯一，即不包含其他代码的前缀

MST 框架：MCE¶

Prim 算法和Kruskal 算法都可以看作是在一个更抽象的框架的实例化，即 MCE（Minimum-weight Cut-crossing Edge）

[!Note] 定义-切顶点的一个划分构成一个切。给定一个连通无向图 $G=(V,E)$, 如果非空点集 $V_{1}$ 和 $V_{2}$ 满足 $V_{1}\cup V_{2}=V,V_{1}\cap V_{2}=\emptyset$，则 $V_{1}$ 和 $V_{2}$ 构成一个图 $G$ 的切

[!Note] 定义-MCE 针对图G 的某个切，即边的两个顶点分属 $V_{1}$ 和 $V_{2}$ 两个集合；另一类是切内部的边。由于图G 是连通的，所以必然存在跨越切的边（否则图就不连通了），进而必然存在（不一定唯一）最小权值的跨越切的边，简称为MCE

不难引出一个定理，（利用最小生成树性质） MCE 和最小生成树的本质关联即：

[!Note] 定理对某条边 $e$，如果存在一个切使得 $e$ 成为该切的MCE，则 $e$ 必然属于某一棵最小生成树

用反证法，如果不属于MST，则有一条更小权的cross edge 跨越切，矛盾，不难证明

由此可以更好的理解Prim 算法和kruskal 算法

从MCE 看`Prim` 算法¶

对于 Prim 算法，其 Finished 就是看作一个点集 $V_{1}$, 另外一个 Fringed 就是所有 $MCE$ 的“另一头”，所以我们的贪心选择（选择最小权值边，即MCE）是正确的。

从MCE 看`Kruskal`算法¶

引入一个小问题：（黄老师说以前考过，太ez 不敢考了🤣）

[!引入] 有一系列边，其中 $e_{1}<e_{2}<e_{3}<\dots<e_{n}$，问这些边在不在 MST 中

回答很简单。由于Kruskal 算法是正确的，所以 $e_{1}$ 一定 $\in MST$，$e_{2}\in MST$，$e_{3}加进来不成环就\in MST，否则\not\in MST$...

受这个启发，来说明 Kruskal 算法的正确性。 - Kruskal 算法的运行可以分成 $n$ 个阶段，$F^{(0)},F^{(1)},\dots,F^{(n-1)}$，假设其已经完成前 $k$ 阶段，假设选出的下一个边为 uv，从MCE 角度来看，边 uv 必然为MCE，也就是必然可以构造出一个切 $(V_{1},V_{2})$ 使得 uv 是MCE - 不失一般性，将 u 分配到 $V_{1}$，v 分配到 $V_{2}$，在 $F^{(k-1)}$，所有和 $u$ 相连通的点分配到 $V_{1}$, 与 $v$ 相连通的分配到 $V_{2}$，剩余未分配的点与 $u$ 和 $v$ 均不连通，随意分配到 $V_{1}$ 和 $V_{2}$（要保证一个连通片的在一起） - 由上述分析可以知道：如果加入 $uv$ 之前已经连通（称环），则上述不可能完成。 - 因为如果这样，则 $u$ 和 $v$ 在加入边 $uv$ 之前已经被若干权重更小的边连通（Kruskal 贪心选择性质），则加入 $uv$ 形成了环，无论如何划分顶点集，都不可能避开比 $uv$ 权重更小的边，所以 $uv$ 不是任何切中的 $MCE$，因而不可能 $\in MST$ - 这就是要求不成环的意义 - 核心就是一个字避 - 避开权值更小的边，将他们分配到切的某个点击的内部，避免跨越切，从而使得选中的边是MCE，具体避开的方法就是避免成环。

单源最短路径¶

Dijkstra 算法¶

总体设计： - 设计一个 Best-FS 算法 - 其受到 BFS 的启发，本质是把普通的队列替换成优先队列。

使用 最小堆 记录当前能选择的最小权重边，在加入边后动态更新 最小堆

算法如下： image.png|600

思考：Dijkstra 给出的单源最短路径树是 MST 吗？¶

不是。具体可看这道题的说明 Dijkstra 得到的最短路径树是否必然是一棵最小生成树，请证明你的结论。

Warshall - Floyd 算法¶

其核心思想是，最短路路径的本质就是比较在两个顶点之间中转点，比较经过与不经过中转点的距离哪个更短。类似Bellman-Ford算法，我们将此操作也称为松弛。

找出中转点-Warshall (传递闭包)¶

算法¶

void simpleTransitiveClosure(bool[][] A, int n, bool [][] R) int $i$, $j$, $k$; Copy A to R; Set all main diagonal entries, $r_{ii}$ , to true; for(k=1;k<= n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) $r_{ij}=r_{ij}\lor(r_{ik}\land r_{kj})$

顺序很重要: k, i, j （这本质是因为，Warshall 乃至 Floyd 算法都是一种动态规划的思想）
动态规划理解 $k$ 为什么在外层：比如用 $d[k][i][j]$ 表示可以通过编号 $1\dots k$ 节点的最短路径。初值 $d[0][i][j]$ 为原图的邻接矩阵。

这就是一个计算基于矩阵表示的二元关系的传递闭包的 Warshall 算法则转移方程： $$ f[k][i][j]=\min[f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]] $$ 所以只和前一位有关。所以我们进行状态转移应该保证前一位 $k-1$ 已经全部做完，所以 $k$ 应该作为循环的外层。

正确性¶

记号： - value of $r_{ij}$ changes during the execution of the body of the "for k..." loop（随着循环变换） - After initialization: $r_{ij}^{(0)}$ - After the $k^{\text{th}}$ time of execution: $r_{ij}^{(k)}$

Floyd 算法（单源最短路径 2）¶

对于 Warshall-Floyd 算法，其实只是把传递闭包的算法略作修改： void allPairsShortestPaths(float[][], int n, float [][] D) int $i$, $j$, $k$; Copy W to D;（用邻接矩阵初始化距离） for(k=1; k<= n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) $D[i][j]=\min(D[i][j],D[i][k]+D[k][j])$ （这里没有显式的写出转移来自 k-1，但由于循环执行的循序-最外层 loop 是 k，所以其实是等价的）

$k$ 是阶段，$i$ 和 $j$ 是状态 ![[Pasted image 20250515103046.png]]
缺点

图遍历问题¶

DFS¶

白路径定理 (White Theorem)¶

活动区间与 Edge 类型¶

定理 8.1¶

强连通分支算法（基于 DFS）¶

DFS 与 DP¶

DAG (有向无环图)¶

构造逆拓扑序¶

构造方法¶

正确性证明¶

任务规划问题 (Task Scheduling)¶

无向图¶

Undirected Graph 无向图¶

无向图的 DFS tree¶

Bi-Connected¶

割点¶

桥¶

BFS¶

BFS structure¶

生成树边情况¶

BFS 检测环¶

图优化问题¶

Best-FS¶

MST 算法¶

Prim' s Algorithm¶

分析复杂度¶

- \(T(n,m)=O(nT(\text{getMin})+nT(\text{deleteMin+insert})+mT(\text{decreaseKey}))\)¶

最小生成树性质¶

Kruskal Algorithm¶

算法过程¶

分析复杂度¶

前缀码¶

MST 框架：MCE¶

从MCE 看Prim 算法¶

从MCE 看Kruskal算法¶

单源最短路径¶

Dijkstra 算法¶

思考：Dijkstra 给出的单源最短路径树是 MST 吗？¶

Warshall - Floyd 算法¶

找出中转点-Warshall (传递闭包)¶

算法¶

正确性¶

Floyd 算法（单源最短路径 2）¶

从MCE 看`Prim` 算法¶

从MCE 看`Kruskal`算法¶