Given a connected directed acyclic graph $G(V, E)$, is there an algorithm for changing a spanning tree to a minimum spanning tree through a series of edge swaps?

We can use Prim's or Kruskal's algorithm to produce the minimum spanning tree from scratch, but I think we can find an asymptotically more efficient algorithm for finding a minimum spanning tree if we know for instance that we have some constant $k$ more edges than we have vertices, so $|E| = |V| + k$.


1 Answer 1


Are you familiar with Matroids? A Matroid is a construct M(G, I) with a ground set $G$ and independent set $I \subseteq 2^{G}$. Graphic matroids are defined with $G = E$, the edge set of the graph; and independence is acyclicity. That is, if a subset of edges is acyclic, it is in $I$.

Greedy basis algorithms are based on this edge-substitution procedure. In fact, this is how the proofs of correctness of Prim's, Kruskal's, and Dijkstra's algorithms are done. It is important to note that a Matroid allows us to deal with graphs in the same way that we deal with vector spaces. Hence, the term "basis" is quite accurate here. It refers to a maximally independent set.

So we will adapt a standard greedy basis algorithm. Start by sorting $G$, the ground set. Now for each $e \in G$, check if $e \in T$. If it is in $T$, discard $e$. Otherwise, check to see which edge $e^{\prime} \in T$ is incident to the same two vertices as $e$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .