Redirected
recategorized by
2,279 views
1 votes
1 votes

Consider the graph given below:

Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is

  1. AD, AE, AG, GC, GB, BF
  2. GC, GB, BF, GA, AD, AE
  3. GC, AD, GB, GA, BF, AE
  4. AD, AG, GC, AE, GB, BF
recategorized by

2 Answers

1 votes
1 votes

Kruskal's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a safe edge to add to the growing forest by finding, of all the edges that connects any two trees in the forest, an edge $(u,v)$ of least weight. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

In the given graph edge weight of $\text{BD}$ is not given. But if we see the options, $\text{BD}$ is not in any of them and so we can assume its weight is infinity (or a large value).

The smallest edge weight is $2$ and any of an edge with weight $2$ can be picked by Kruskal’s algorithm which are $\text{AD}$ or $\text{GC}.$ These $2$ edges are not in a cycle and so both must be the first two edges selected by Kruskal’s algorithm. Only option C satisfies.

0 votes
0 votes

Kruskal's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a safe edge to add to the growing forest by finding, of all the edges that connects any two trees in the forest, an edge $(u,v)$ of least weight. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

The given graph is 

We can see that $DB's$ weight is not given.

We know that, for any weighted graph, if the weight of an certain edge isn't given, then the weight'll be $1$(default)

Edge No. Vertex Pair Edge Weight
E1 (B,D) 1
E2 (G,C) 2
E3 (A,D) 2
E4 (B,G) 3
E5 (A,G) 3
E6 (A,E) 4
E7 (D,G) 4
E8 (B,C) 4
E9 (B,F) 4
E10 (D,E) 5
E11 (C,F) 5
E12 (A,C) 6

Graph

Add edge E1

Add edge E2

Add edge E3

Add edge E4

Edge E5 will not counted, as it'll create cycle.

Add edge E6

Edge E7,E8 will not counted, as it'll create a cycle.

Add edge E9

Edge E10, E11, E12 will not connected, they'll make a cycle.

∴ $\color{green}{\text{Total Cost}}= 1+2+2+3+4+4$

$\qquad\qquad = \color{gold}{16}$

$\color{violet}{\text{The List of the edges of the tree in the order in which they are choosen is}}$ $\color{maroon}{\text{BD, GC, AD, BG, AE, BF}}$

Answer:

Related questions

1 votes
1 votes
2 answers
1
Arjun asked Nov 5, 2017
3,067 views
Which speed up could be achieved according to Amdahl's Law for infinte number of processes if $5\%$ of a program is sequential and the remaining part is ideally parallel?...
0 votes
0 votes
1 answer
2
Arjun asked Nov 5, 2017
2,519 views
Which of the given wireless technologies used in IoT, consumes the least amount of power?ZigbeeBluetoothWi-FiGSM/CDMA
0 votes
0 votes
2 answers
3
Arjun asked Nov 5, 2017
4,592 views
Which of the following is not a Clustering method?K-Means methodSelf Organizing feature map methodK- nearest neighbor methodAgglomerative method