Consider a directed graph, G(N,A), where N and A are the set of nodes and arcs, respectively. Associated with each arc (i,j) in A is a cost c(i,j). Let |N|=n and |A|=m. The problem is to find a rooted directed spanning tree, G(N,S) where S is a subset of A such that the sum of c(i,j) for all (i,j) in S is minimized. The rooted directed spanning tree is defined as a graph which connects, without any cycle, all nodes with n-1 arcs, i.e., each node, except the root, has one and only one incoming arc.
The PRIM algorithm , which solves the undirected MST problem, is shorthanded to solve the directed counterpart. The following example exhibits that the iterative greedy decision may no longer sequentially give the optimal solution.
Chu and Liu , Edmonds , and Bock  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 . In the sequel, we shall briefly illustrate the Chu-Liu/Edmonds algorithm, following by a comprehensive example (due to ). Reader can also refer to   for an efficient implementation, O(mlogn) and O(n^2) for dense graph, of this algorithm.Chu-Liu/Edmonds Algorithm
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 minimum extra cost replacing arc (2,3) for arc (4,3) and hence the cycle is eliminated. (There is an error in the picture below. Arc (2,6) should be selected instead of Arc (1,6).)