Consider the following graph. With the indicated edge weights, start from vertex

Question

Consider the following graph. With the indicated edge weights, start from vertex x, use the Breadth First Search (BFS) algorithm (described in the textbook) to compute the BFS tree. Show intermediate results similar to the textbook example, and show the final BFS tree. In cases when several candidate vertices have the same minimal costs, choose a vertex according to its alphabetical order. Based on the same graph shown in A1, use the Kruskal's algorithm to compute the Minimum Spanning Tree (MST). Show intermediate results similar to the textbook example, and show the final MST.

Explanation / Answer

Answer for the given question:

Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree (See method 2 of this post). The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.

Steps:

1. Start from X is having three adjacent nodes y,v,w

X ----->Y = 4
X------->V = 4
X------> W = 1

after visiting all the adjacent nodes to X move to node W

2. Start from W is having U, V and X, X is already visited
and U to V there is cycle no need to traverse

Only one chance is

W----> U = 6

3. after visiting all the adjacent nodes to W move to node U

U have the adjacent nodes T,V,W and W is already visited and
U to V there is a cycle no need to visit.

U----> T = 2

all nodes are visited

X--->W---->U---->T = 9

this is minimum cost

Answer for Question 2 using Kruskal's algorithm:

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

Total Number of nodes in a given graph is 6
The resulting Minimum spanning tree will have the 5 edges

1. Start from X is having adjacent nodes Y, V, W
X--->Y = 4
X---->V = 7
X---->W = 1

Consider X---->W = 1

2. Start from W is having V,U,X and compare all these nodes takes less weight
W-----> X = 1
W----->U = 6
W----->V =4

Consider X------>W---->V =5

3. Start from V is having Y,U,W and compare all these nodes takes less weight
V---->Y =2
V---->U =3
V----->T =4
Consider X------>W---->V---->Y =7

4. Start from Y is having V,T,X and compare all these nodes takes less weight
Y---->T =5
Y---->V =2
Y----->X =4
Consider X------>W---->V---->Y---->T =12

4. Start from T is having Y,U,V and compare all these nodes takes less weight
T---->Y =5
T---->U =2
T----->V=4
Consider X------>W---->V---->Y---->T---->U =14

and removed the cycle where ever is possible while
traversing the given graph

1-4-2-5-2 = 14

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.