Directed Minimum Spanning Tree Chu-LiuEdmonds Algorithm.docxVIP

Directed Minimum Spanning Tree: Chu-Liu/Edmonds Algorithm我们的现代数据库大作业要求实现一个图查询系统，包括基于属性的子图查询、可达性查询（可选）、最短路径查询（可选）、TopK最短路径查询（可选）、图形化展示（可选）等功能。分成子图同构查询小组以及可达性及TopK路径查询小组。小组长之前研究了Efficiently answering reachability queries on very large directed graphs这篇论文，关于Path-tree计算可达性的，其中需要构造最大生成树(无需固定root)，于是负责打酱油的我就开始琢磨单连通有向图的最大生成树算法Edmonds Algorithm了。??Edmonds Algorithm介绍Solving The Directed MST ProblemChu and Liu [2], Edmonds [3], and Bock [4] have independently given efficient algorithms for finding the MST on a directed graph. The Chu-Liu and Edmonds algorithms are virtually identical; the Bock algorithm is similar but stated on matrices instead of on graphs. Furthermore, a distributed algorithm is given by Humblet [5]. In the sequel, we shall briefly illustrate the Chu-Liu/Edmonds algorithm, following by a comprehensive example (due to [1]). Reader can also refer to [6] [7] for an efficient implementation,?O(mlogn)?and?O(n^2)?for dense graph, of this algorithm.Chu-Liu/Edmonds AlgorithmDiscard the arcs entering the root if any; For each node other than the root, select the entering arc with the smallest cost; Let the selected?n-1?arcs be the set?S.If no cycle formed,?G(N,S)?is a MST. Otherwise, continue.For each cycle formed, contract the nodes in the cycle into a pseudo-node?(k), and modify the cost of each arc which enters a node?(j)?in the cycle from some node?(i)outside the cycle according to the following equation.c(i,k)=c(i,j) - (c(x(j),j) - min_{j}(c(x(j),j))where?c(x(j),j)?is the cost of the arc in the cycle which enters?j.For each pseudo-node, select the entering arc which has the smallest modified cost; Replace the arc which enters the same?realnode in?Sby the new selected arc.Go to step 2 with the contracted graph.The key idea of the algorithm is to find the replacing arc(s) which has the minimum?extra cost?to eliminate cycle(s) if any. The given equation exhibits the associated extra cost. The following example illustrates that the contraction technique finds the