Minimum Spanning Tree for Directed Graphs
I'm working on a school assignment (not intending to cheat here) that consists of implementing a graph. I have every method of the graph working properly, as best I can determine (with extensive test code), except that I cannot figure out an algorithm for doing a minimum spanning tree if the graph is directed. (My method for an undirected graph works.)
I'll try to describe my current algorithm, which, as implemented, works for many directed graphs, but not all.
I attempt to generate a minimum spanning tree for each vertex (treating that vertex as the root), by these steps (taken for each vertex):
Create a new empty graph
Add every vertex of the current graph to it
For every vertex that is not being treated as the root, I take its least-cost incoming edge, and add it to the graph.
Once a tree has been returned for each possible root, I eliminate any trees that contain cycles or have fewer than (# of vertices - 1) edges. (It is OK for this method to fail for an unconnected graph.) I then return the remaining tree, if any, that has the lowest total edge cost.
This works for all of the test graphs I have in most of my test class, but it does not work for a test graph whose adjacency matrix looks like this:
| D | A | C | B |
-+++++
D||| 2 ||
-+++++
A||| 7 | 1 |
-+++++
C| 1 ||||
-+++++
B| 6 | 2 |||
-+++++
I don't think it can be easily modified to work for this case either, so I need a totally different approach.
I'm currently reading and trying to understand the Gabow/Myers paper from 1978, but I'm having trouble with it. (I purposely chose an older algorithm thinking it might be easier to understand than a sleeker, more modern one.)
Several papers seem to mention that you can get to a directed spanning tree via depth-first traversal, but as I understand depth-first traversal, the minimum spanning trees of the directed graphs I can solve are not depth-first traversals of the graphs at all. I assume they mean something that I just can't see.
I'm not looking for code, but if someone can suggest an algorithm that I might be able to understand, I would appreciate it. Or a hint would be great too. I will of course continue to pursue this on my own in the meantime.
Here is the API specification for what I've coded. I'm including it only so that you can see, if you are interested, what has already been coded. I have completed all of the methods described in the API and they all work as best I can tell.
http://jody140.dsl.frii.net/cs/cs3/Graph/
