Minimum spanning tree in undirected graph

Download source code and project.


  • Files in the project
    1. project.c
      c source code
    2. data.txt
      Please referring general help for details.
    3. run.bat
      Please referring general help for details.
            
  • Compile and execute
    1. Compile
      You only need to compile project.c
    2. Execute
      If executable (compiled) file is project.exe
      executing command is project.exe data.txt
      Please referring general help for more.
         
  • Understand source code
    1. Read data file
      Please referring general help for details.
          
    2. struct Path
      The program uses an array of the struct in size of 26 - Path path[26] - to store node A to Z.
      • Field iExist 
        which indicates if the node exists, i.e. if node U is not in graph, U.iExist=0. otherwise U.iExist=1;
      • Field chNode  
        which         stores name of a node. i.e. for node W, W.chNode=W;
      • Field chNodeNeighbor
        which is connected neighbor node of chNode and works as flag for identifying which sets the node belongs to, please see below. 
       
    3. Key process: fixed set and tentative set (see example)
      1. initialize all nodes in tentative set and their weight to start node as infinite.
        node.chNodeNeighbor=0;
        put any node in to fixed set:
        any.chNodeNeighbor=any;
      2. find minimum weight from tentative set to fixed set and 2 nodes involved,
        one of the 2 nodes is in tentative set and another is in fixed set.
        then move the tentative node to fixed set by:
        nodeInTentativeSet.chNodeNeighbor=nodeInFixedSet;

        what does minimum weight between the 2 sets mean?
        lets explain step by step:
        • minimum weight from a tentative node to fixed set.
          it is minimum weight among weights of the node to all fixed nodes.
        • minimum weight between 2 sets
          it is minimum one among minimum weights of all tentative nodes to fixed set.
        This is a loop until all nodes are moved to fixed set.
        If some nodes can not be moved, the tree is not a closed tree.

    4. Conclusion
      Key for obtaining minimum spanning tree is that all nodes are divided in to two sets, fixed and  tentative sets.
      All nodes are initialized in tentative set except start node, then to find shortest edge from tentative set to fixed set and move related node to fixed set until all nodes are moved      .


Example:
Lets use graph above as example to explain the loop fruther more:
 
Steps (referring table bellow, function is GetMinimumWeightToFixedSet(...)):
  
  1. Initialize all nodes (in function StartSearch(...))
    chNodeNeighbor=0; (it means all nodes are in tentative set)
    Fixed                
    Tentative A(0) B(0) E(0) F(0) H(0) G(0) K(0) M(0)
    note: X(Y) means neighbor node of X is Y.
     
  2. move any node, i.e. A to fixed set:
    A.chNodeNeighbor=A
    so node A is moved to fixed set:
    Fixed A(A)              
    Tentative   B(0) E(0) F(0) H(0) G(0) K(0) M(0)
     
  3. find minimum wight between 2 sets and related nodes.
    H to A is 8
    B to A is 12
    F to A is 5
    minimum weight is 5, tentative node is F, fixed node is A, so move F to fixed set
    Fixed A(A)     F(A)        
    Tentative   B(0) E(0)   H(0) G(0) K(0) M(0)
      
  4. find minimum weight between 2 sets and related nodes again.
    H to A is 8
    B to A is 12
    E to F is 18
    So we move H to fixed set:
    Fixed A(A)     F(A) H(A)      
    Tentative   B(0) E(0)     G(0) K(0) M(0)
     
  5. find minimum weight between 2 sets and related nodes again.
    we use (integer,character) to represent (minimum weight, node in fixed set). 
    B to fixed set is: (9,A)
    E to fixed set is: (18,F)
    G to fixed set is: (4,H)
    K to fixed set is: (47,H)
    Now we can move G to fixed set
    Fixed A(A)     F(A) H(A) G(H)    
    Tentative   B(0) E(0)       K(0) M(0)
     
  6. once again
    B to fixed set is: (3,G)
    E to fixed set is: (7,G)
    K to fixed set is: (47,H)
    M to fixed set is: (13,G)
    so we move B to fixed set
    Fixed A(A)     F(A) H(A) G(H)    
    Tentative     E(0)       K(0) M(0)
      
  7. once again:
    we move E to fixed set  
    Fixed A(A) B(G) E(G) F(A) H(A) G(H)    
    Tentative             K(0) M(0)
     
  8. once again
    so we move M
    Fixed A(A) B(G) E(G) F(A) H(A) G(H)   M(G)
    Tentative             K(0)  
     
  9. K to fixed set is (34,M)
    so we move K 
    Fixed A(A) B(G) E(G) F(A) H(A) G(H) K(M) M(G)
    Tentative                
    10. Congratulations! all nodes have been moved to fixed set, it means the tree is a closed tree also.

Now we have minimum spanning tree (ignore A - A):
B - G
E - G
F - A
H - A
G - H
K - M
M - G
and add all weight of edges between nodes above to get weight of the tree, which is 74