MST.cpp is the outline of a C++ LEDA
program that creates a creates a graph with weighted edges, and then
calls functions that implement Kruskal's and Prim's algorithms for
finding a minimal cost spanning tree.
The comments for the functions have been retained, you have to fill
in the C++ code (lines marked //DELETED indicate where
one of more lines of code have been deleted).
Note the use of the LEDA
node_array and
list classes.
Here's sample output:
geoff@duck:~/c++> MST 5 8 [0](A) : [1]==(4)==[0][2]==(5)==[0][4]==(4)==[0] [1](B) : [1]==(2)==[2][1]==(3)==[3][1]==(4)==[0][4]==(2)==[1] [2](C) : [1]==(2)==[2][2]==(5)==[0][3]==(1)==[2] [3](D) : [1]==(3)==[3][3]==(1)==[2][4]==(3)==[3] [4](E) : [4]==(2)==[1][4]==(3)==[3][4]==(4)==[0] MST by Kruskal Try add [3]==(1)==[2] Accepted Try add [4]==(2)==[1] Accepted Try add [1]==(2)==[2] Accepted Try add [1]==(3)==[3] Rejected Try add [4]==(3)==[3] Rejected Try add [4]==(4)==[0] Accepted [0](A) : [4]==(4)==[0] [1](B) : [4]==(2)==[1][1]==(2)==[2] [2](C) : [3]==(1)==[2][1]==(2)==[2] [3](D) : [3]==(1)==[2] [4](E) : [4]==(2)==[1][4]==(4)==[0] MST by Prim Add [4]==(4)==[0] Add [4]==(2)==[1] Add [1]==(2)==[2] Add [3]==(1)==[2] [0](A) : [4]==(4)==[0] [1](B) : [4]==(2)==[1][1]==(2)==[2] [2](C) : [1]==(2)==[2][3]==(1)==[2] [3](D) : [3]==(1)==[2] [4](E) : [4]==(4)==[0][4]==(2)==[1]There's an executable version available on
duck in
~geoff/c++ for you to experiment with.
Remember, you have to work on
duck, and to compile programs using the LEDA library
you have to use this pattern:
g++ YourCode.cpp -I/mnt/disk1/LEDA-3.8a/incl -L/mnt/disk1/LEDA-3.8a -lG -lL