算法导论19.1 Exercises 答案

19.1-1

仿照图19.1(b)，并查集的整个合并过程如下：

\(\begin{array}{l|lllllllllll} \text{Edge processed}\\\hline \text{initial sets} &\{a\}&\{b\}&\{c\}&\{d\}&\{e\}&\{f\}&\{g\}&\{h\}&\{i\}&\{j\}&\{k\}\\ (d,i) &\{a\}&\{b\}&\{c\}&\{d,i\}&\{e\}&\{f\}&\{g\}&\{h\}&&\{j\}\\ (f,k) &\{a\}&\{b\}&\{c\}&\{d,i\}&\{e\}&\{f,k\}&\{g\}&\{h\}&&\{j\}\\ (g,i) &\{a\}&\{b\}&\{c\}&\{d,g,i\}&\{e\}&\{f,k\}&&\{h\}&&\{j\}\\ (b,g) &\{a\}&\{b,d,g,i\}&\{c\}&&\{e\}&\{f,k\}&&\{h\}&&\{j\}\\ (a,h) &\{a,h\}&\{b,d,g,i\}&\{c\}&&\{e\}&\{f,k\}&&&&\{j\}\\ (i,j) &\{a,h\}&\{b,d,g,i,j\}&\{c\}&&\{e\}&\{f,k\}&&&&\\ (d,k) &\{a,h\}&\{b,d,f,g,i,j,k\}&\{c\}&&\{e\}&&&&&\\ (b,j) &\{a,h\}&\{b,d,f,g,i,j,k\}&\{c\}&&\{e\}&&&&&\\ (d,f) &\{a,h\}&\{b,d,f,g,i,j,k\}&\{c\}&&\{e\}&&&&&\\ (g,j) &\{a,h\}&\{b,d,f,g,i,j,k\}&\{c\}&&\{e\}&&&&&\\ (a,e) &\{a,e,h\}&\{b,d,f,g,i,j,k\}&\{c\}&&&&&&&\\ \end{array}\)

由此最终产生了三个连通块：\(\{a,e,h\},\{b,d,f,g,i,j,k\},\{c\}\)。

19.1-2

充分性：假设节点\(x,y\)在无向图中属于同一连通分量，那么意味着从\(x\)到\(y\)中有一条路径\(v_1,v_2,\dots,v_k\)，其中\(v_1=x,v_k=y\)。随着过程CONNECTED-COMPONENTS的进行，这条路径上相邻的两个节点都被合并到一个集合中，因此最终\(x\)和\(y\)同属一个集合。

必要性：在一开始时，\(x,y\)属于各自的集合。假设对某条边\((u,v)\)进行了UNION操作后，\(x,y\)从不属于一个集合到属于一个集合，那么记录下边\((u,v)\)。不失一般性，假设对边\((u,v)\)进行UNION操作前，\(x,u\)同属一个集合，\(y,v\)同属令一个集合，对这两个集合递归进行。由于一开始每个节点所在集合只有自己，因此由此记录下来的边是一条从\(x\)到\(y\)的路径，因此\(x\)和\(y\)在同一连通分量中。

19.1-3

由于每条边都需要进行两次FIND-SET操作，因此整个调用过程一共需要\(2|E|\)次FIND-SET操作。一开始整个图有\(|V|\)个不同的集合，由于它具有\(k\)个连通分量，因此根据题目19.1-2的结论，CONNECTED-COMPONENTS结束后一共有\(k\)个不相交集合；每进行一次UNION操作，不相交集合个数减少\(1\)，因此UNION操作的个数为\(|V|-k\)。