Introduction
Minimum
Total Weight
Spanning Tree algorithm is a method of deriving smallest possible total
edges weight from a graph.
In a graph, nodes can have multiple edges carrying different
weights. There can be multiple paths to travel from one node to another
node, looping may occur among the nodes.
Graph after the Minimum
Total Weight Spanning Tree algorithm, all the nodes will still be
joined but with the smallest possible total edges weight. And all looping
among the nodes will be removed.
In computer networks and telecommunications networks, Ethernet
switches & terminal nodes have multiple network wired connections among
switches & terminal nodes for hardware redundancy purpose. When one
wire connections broken, data can still able be transmitted using another
hardware connection. However, such redundancy arrangement can cause switching loop
problem. A switching
loop happens in computer networks when there is more than one path
between two endpoints. The loop creates broadcast storms as the switches
will repeatedly rebroadcast the broadcast messages flooding the network. In
a looped network, frame can loop forever.
Both MTWST & Shortest Path derivation can be implemented to
remove any looped network.
MTWST
comparison against Shortest Path algorithm
·
Both
graphs will not have any looping among nodes after the derivation
·
There
are no starting node and destination node in Minimum Total Weight Spanning
Tree. In contrast, Shortest Path graph need to define a root node /
starting node.
·
In
Shortest Path graph, root node to other nodes will always be the shortest
travelling distance; paths among other nodes may not.
In MTWST graph, paths among nodes may not be the
shortest path. But the graph will have the minimum total weight.
·
MTWST
graph derivation consist of Shortest Path derivation. When there are edges
on target node and destination node, MTWST will need to run Shortest Path
derivation to check is there a path present between target node and
destination node before adding the edge (target node-to-destination node)
into MTWST graph. Hence MTWST will run multiple times of Shortest Path
derivations, thus required certain level of computation powers.
Example graph #1: with looping paths
Example graph #1: Shortest Path derivation
Example graph #1: Minimum Total Weight Spanning Tree derivation
Minimum Total
Weight Spanning Tree derivation steps
1.
Sort all nodes’ edges in ascending
order, from smallest weight to largest weight. We can use priority queue to
do the work.
2.
Remove the smallest edges from the
top of priority queue and add into MTWST graph, repeat until all the edges
are removed from the priority queue
3.
Only add edges that do not form
looping among nodes into MTWST graph, those edges that connect disengaged
nodes. The method of filtering is to use Shortest Path derivation to check
is there a present path between two endpoints / nodes of the selected edge.
If path is present, the edge will not be added into MTWST graph.
C# Console App Source Code
2-ways edges with
different weights
Version ‘0’: MinSpanningTree4.cpp graph1.txt graph2.txt graph3.txt
Version ‘1’: During
checking, if we found a path from source node to destination node we can
stop further checking to reduce computation. MinSpanningTree5_breakExecution.cpp graph1.txt graph2.txt graph3.txt
Version ‘2’: use
‘Map / Dictionary’ instead of List. MinSpanningTree9_HashTable.cpp graph1.txt graph2.txt graph3.txt
All bi-directional
edges with same weights
Version ‘3’: simplify. MinSpanningTree6_ edgesSameWeight.cpp graph1.txt graph2.txt graph3.txt
Version ‘4’: use ‘Map’
instead of List. MinSpanningTree10_ edgesSameWeight.cpp
graph1.txt graph2.txt graph3.txt
|