So I'm enrolled in -- by far -- the hardest class I've ever taken for my Comp Sci major (as of yet). It's a Design/Analysis class for Algorithms...
Has anyone implemented the Kruskal, Prim, or Dijkstra Algorithms for Minimum Spaninng Trees in Java? I'm having a very difficult time implementing these alogrithms because of the poor explanation by my professor. Searching around on google, I can't get anything more than the poor psuedo-code my instructor provided.
Quote:
T := {}
for i := 1 to n -1 {
do
(x,y) := getNextedge(G) using greedy selection mechanism
while (not cycle(x,y,G)
addEdge(x, y, T);
}
// assume G is a connected graph with N nodes
|
That's ALL the information I was provided, and was asked to implement it. That said, I'm not looking for a complete solution, although that wouldn't be refused.
I've implemented it with a java class Edge which is aware of its weight and its connecting nodes. It entirely works, except the "cycle()" method. I'm not sure how to make the program aware of a cycle? Each edge has no knowledge of the next edge to be added other than its verticies and weight.
AAAAAAH .. any help is appreciated, as it is approaching one week late as I've tried to implement it different ways..