Minimum spanning tree in undirected graph
Download
source code and project.
- Files in the project
- project.c
c source code - data.txt
Please referring general help for details. - run.bat
Please referring general help for details.
- project.c
- Compile and execute
- Compile
You only need to compile project.c - Execute
If executable (compiled) file is project.exe executing command isPlease referring general help for more.**project.exe data.txt**
- Compile
- Understand source code
- Read data file
Please referring general help for details.
- 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 - Field
*chNodeNeighbor* which is connected neighbor node of chNode and works as flag for identifying which sets the node belongs to, please see below.
- Field
- Key process:
**fixed set**and**tentative set**(see example)- 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; - 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.
If some nodes can not be moved, the tree is not a closed tree. - minimum weight from a tentative node to fixed set.
- initialize all nodes in tentative set and their weight to start node
as infinite.
- 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.
- Read data file
Example:Lets use graph above as example to explain the loop fruther more: Steps (referring table bellow, function is GetMinimumWeightToFixedSet(...)):-
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.
- 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) - 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) - 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) - 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) - 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) - 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) - once again
so we move M**Fixed**A(A) B(G) E(G) F(A) H(A) G(H) M(G) **Tentative**K(0) - 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**
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): |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||