# What's an efficient algorithm for walking to a minimum spanning tree?

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$.

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$.
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$.