Answer Happy

1. Write a program to perform one chosen algorithm for finding
MST (minimum spanning tree) in graph. Use user input to initialize
the graph.
For more practice you can do exercise:
2. Write a program to draw a figures. Use loops. User gives a
number of lines.
Theoretical background
A weighted graph is a graph in which each branch is given a
numerical weight. A weighted graph is therefore a special type of
labeled graph in which the labels are numbers (which are usually
taken to be positive).
An undirected graph is a graph in which the edges do not point
in any direction (the edges are bidirectional).
A connected graph is a graph in which there is always a path
from a vertex to any other vertex.
A spanning tree is a sub-graph of an undirected connected graph,
which includes all the vertices of the graph with a minimum
possible number of edges. If a vertex is missed, then it is not a
spanning tree. The edges may or may not have weights assigned to
them.
The total number of spanning trees with n vertices that can be
created from a complete graph is equal to n(n-2).
If we have n = 4, the maximum number of possible spanning trees
is equal to 44-2 = 16. Thus, 16 spanning trees can be formed from a
complete graph with 4 vertices.
Spanning tree is used in:
- computer network routing protocol
- cluster analysis
- civil network planning
A minimum spanning tree is a spanning tree in which the sum of
the weight of the edges is as minimum as possible.
Minimum spanning tree is used:
- to find paths in the map
- to design networks like telecommunication networks, water
supply networks, and electrical grids
- in handwriting recognition
- in image segmentation
The minimum spanning tree from a graph is found using the
following algorithms:
- Prim's Algorithm (applied in laying cables of electrical
wiring, in network designed)
- Kruskal's Algorithm
Prim's algorithm is a minimum spanning tree algorithm that takes
a graph as input and finds the subset of the edges of that graph
which form a tree that includes every vertex has the minimum sum of
weights among all the trees that can be formed from the graph
Prim’s algorithm use greedy approach to find the minimum
spanning tree. In Prim’s algorithm we grow the spanning tree from a
starting position. We add vertex to the growing spanning tree.
Algorithm Steps:
1. Maintain two disjoint sets of vertices. One containing
vertices that are in the growing spanning tree and other that are
not in the growing spanning tree.
2. Select the cheapest vertex that is connected to the growing
spanning tree and is not in the growing spanning tree and add it
into the growing spanning tree. This can be done using Priority
Queues. Insert the vertices, that are connected to growing spanning
tree, into the Priority Queue.
3. Check for cycles. To do that, mark the nodes which have been
already selected and insert only those nodes in the Priority Queue
that are not marked.
4. Consider the example below:
In Prim’s Algorithm, we will start with an arbitrary node (it
doesn’t matter which one) and mark it. In each iteration we will
mark a new vertex that is adjacent to the one that we have already
marked. As a greedy algorithm, Prim’s algorithm will select the
cheapest edge and mark the vertex. So we will simply choose the
edge with weight 1. In the next iteration we have three
options, edges with weight 2, 3 and 4. So, we will select the
edge with weight 2 and mark the vertex. Now again we have three
options, edges with weight 3, 4 and 5. But we can’t choose edge
with weight 3 as it is creating a cycle. So we will select the edge
with weight 4 and we end up with the minimum spanning tree of total
cost 7 ( 1 + 2 +4).
Prim's Algorithm pseudocode
The pseudocode for prim's algorithm shows how we create two sets
of vertices U and V-U. U contains the list of vertices that have
been visited and V-U the list of vertices that haven't. One by one,
we move vertices from set V-U to set U by connecting the least
weight edge.
T = ∅;
U = { 1 };
while (U ≠ V)
let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V -
U;
T = T ∪ {(u, v)}
U = U ∪ {v}
Example of implementation:
#include
#include
using namespace std;
#define INF 9999999
// number of vertices in graph
#define V 5
// create a 2d array of size 5x5
//for adjacency matrix to represent graph
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}};
Int main() {
int no_edge; // number of edge
// create a array to track selected vertex
// selected will become true otherwise false
int selected[V];
// set selected false initially
memset(selected, false, sizeof(selected));
// set number of edge to 0
no_edge = 0;
// the number of egde in minimum spanning tree will be
// always less than (V -1), where V is number of vertices in
//graph
// choose 0th vertex and make it true
selected[0] = true;
int x; // row number
int y; // col number
// print for edge and weight
cout << "Edge"
<< " : "
<< "Weight";
cout << endl;
while (no_edge < V - 1) {
//For every vertex in the set S, find the all adjacent
vertices
// calculate the distance from the vertex selected at step
1.
// if the vertex is already in the set S, discard it
otherwise
//choose another vertex nearest to selected vertex at step
1.
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[j]) { // not in selected and
there is an edge
if (min > G[j]) {
min = G[j];
x = i;
y = j;
}
}
}
}
}
cout << x << " - " << y << " : "
<< G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;
}
Kruskal’s algorithm builds the spanning tree by adding edges one
by one into a growing spanning tree. Kruskal's algorithm follows
greedy approach as in each iteration it finds an edge which has
least weight and add it to the growing spanning tree.
Algorithm Steps:
1. Sort the graph edges with respect to their weights.
2. Start adding edges to the MST from the edge with the smallest
weight until the edge of the largest weight.
3. Only add edges which doesn't form a cycle , edges which
connect only disconnected components.
So now the question is how to check if 2 vertices are connected
or not ?
This could be done using DFS which starts from the first vertex,
then check if the second vertex is visited or not. But DFS will
make time complexity large as it has an order of O(V+E), where V is
the number of vertices, E is the number of edges. So the best
solution is "Disjoint Sets": Disjoint sets are sets whose
intersection is the empty set so it means that they don't have any
element in common.
Consider following example:
n Kruskal’s algorithm, at each iteration we will select the edge
with the lowest weight. So, we will start with the lowest weighted
edge first i.e., the edges with weight 1. After that we will select
the second lowest weighted edge i.e., edge with weight 2. Notice
these two edges are totally disjoint. Now, the next edge will be
the third lowest weighted edge i.e., edge with weight 3, which
connects the two disjoint pieces of the graph. Now, we are not
allowed to pick the edge with weight 4, that will create a cycle
and we can’t have any cycles. So we will select the fifth lowest
weighted edge i.e., edge with weight 5. Now the other two edges
will create cycles so we will ignore them. In the end, we end up
with a minimum spanning tree with total cost 11 ( = 1 + 2 + 3 +
5).
Kruskal algorithm pseudocode
Any minimum spanning tree algorithm revolves around checking if
adding an edge creates a loop or not.
The most common way to find this out is an algorithm called
Union find. The Union-find algorithm divides the vertices into
clusters and allows us to check if two vertices belong to the same
cluster or not and hence decide whether adding an edge creates a
cycle.
KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by
weight(u, v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
Example of implementation:
#include
#include
#include
using namespace std;
#define edge pair
class Graph {
private:
vector > G; // graph
vector > T; // mst
int *parent;
int V; // number of vertices/nodes in graph
public:
Graph(int V);
void AddWeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void kruskal();
void print();
};
Graph::Graph(int V) {
parent = new int[V];
//i 0 1 2 3 4 5
//parent 0 1 2 3 4 5
for (int i = 0; i < V; i++)
parent = i;
G.clear();
T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
// If i is the parent of itself
if (i == parent)
return i;
else
// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
return find_set(parent);
}
void Graph::union_set(int u, int v) {
parent = parent[v];
}
void Graph::kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end()); // increasing weight
for (i = 0; i < G.size(); i++) {
uRep = find_set(G.second.first);
vRep = find_set(G.second.second);
if (uRep != vRep) {
T.push_back(G); // add to tree
union_set(uRep, vRep);
}
}
}
void Graph::print() {
cout << "Edge :"
<< " Weight" << endl;
for (int i = 0; i < T.size(); i++) {
cout << T.second.first << " - " <<
T.second.second << " : "
<< T.first;
cout << endl;
}
}
int main() {
Graph g(6);
g.AddWeightedEdge(0, 1, 4);
g.AddWeightedEdge(0, 2, 4);
g.AddWeightedEdge(1, 2, 2);
g.AddWeightedEdge(1, 0, 4);
g.AddWeightedEdge(2, 0, 4);
g.AddWeightedEdge(2, 1, 2);
g.AddWeightedEdge(2, 3, 3);
g.AddWeightedEdge(2, 5, 2);
g.AddWeightedEdge(2, 4, 4);
g.AddWeightedEdge(3, 2, 3);
g.AddWeightedEdge(3, 4, 3);
g.AddWeightedEdge(4, 2, 4);
g.AddWeightedEdge(4, 3, 3);
g.AddWeightedEdge(5, 2, 2);
g.AddWeightedEdge(5, 4, 3);
g.kruskal();
g.print();
return 0;
}
#include
using namespace std;
const int V=6;
int minKey(int key[], bool visited[]){
int min = 99, min_index;
for (int v = 0; v
if(visited[v] == false && key[v] < min){
min = key[v];
min_index = v;
}
}
return min_index;
}
int print_MST(int parent[], int cost[V][V]){
int minSum=0;
cout<<"Edge \tWeight\n";
for (int i =1; i
cout<
minSum+=cost[i][parent[i]];
}
cout<<"Total cost is "<
}
void find_MST(int cost[V][V]){
int parent[V], key[V];
bool visited[V];
for(int i = 0; i
key[i] = 99;
visited[i]=false;
parent[i]=-1;
}
key[0]=0;
parent[0]=-1;
for (int x =0; x< V - 1; x++){
int u = minKey(key, visited);
visited = true;
for(int v=0;v
{
if(cost[v]!=0 && visited[v] == false &&
cost[v] < key[v]){
parent[v]=u;
key[v] = cost[v];
}
}
}
print_MST(parent, cost);
}
int main()
{
int cost[V][V];
cout<<"Enter the vrtices for a graph with 6
vertices:";
for (int i=0; i
for (int j=0; j
cin>>cost[i][j];
}
}
find_MST(cost);
return 0;
}
a) ) b) 0 0 o 000 00 000 0000 00000 c) 1 2 3 4 5 2345 3 45 45 5 o o d) e) 00000 Oo oo оо Oo oo 00000 5 4 3 2 1 1 2 3 4 5 54321 1 2 3 4 5 5 4 3 2 1

Prim's Algorithm 4 3 2 2 5 5 3 2 2 5 5

Kruskal's Algorithm