Question

Suppose we have a graph G = (V, E) with weights on the edges of E, and we are interested in computing a Minimum Spanning Tree (MST) of G. Suppose we modify the DFS algorithm so that when at a vertex v, we next visit the unvisited neighbor u such that the weight of (u, v) is minimized. Does this produce a MST of G? prove that it does or provide a counter example.

Answer 1

• We are given a graph G(V,E) and we are interested i computing the MST(minimum spanning tree) of G.
• Some properties(of MST) to keep in mind before solving:​​​​​​​​​​​​​​​​​​​​

  MST contains all the the vertices of the graph.

MST contains (n-1) edges in it, where n is number of vertices in graph.

It has the minimum possible weight ( sum of weight of all edges ) of all possible spanning trees of the graph.

• MST is possible for connected graph so given G should be connected i.e, we can reach any vertex from any other vertex of the graph.
• Now we come to the problem that can we modify our dfs() function to always recur to that unvisited vertex( neighbor u) of v for which Weight(u--v) is minimum.

​​​​​​​ So it is not always possible to get MST by modifying our dfs() function as mentioned above, the counter example is given below.

Suppose we have a connected undirected graph G, in which there are 4 vertices and 5 edges in it.

Edges are : 1-2,1-4,2-4,2-3,3-4 and their weights 2,4,1,3,5 respectively.

  

Yraph a Weights of edges 00- کار با ما کنم vo ③ 9 →

So our MST will contain 4 vertices and 3(n-1) edges.

We can start the dfs function from any vertex so our answer changes depending on the initial vertex.

1. if we start from vertex 1, then set of edges obtained by our dfs() function is 1-2,2-4,4-3 and then stop as all neighbors of 3 are visited. so we get total 3 edges with all 4 vertices.

so total weight becomes 2+1+5=8.

2.if we start from vertex 2, then set of edges obtained by our dfs() function is 2-4,4-1 and then stop as all neighbors of 1 i.e, 2 and 4 are visited.So we get 2 edges and 3 vertices which is not a spanning tree.​​​​​​

3. if we start from vertex 3, then set of edges obtained by our dfs() function is 3-2,2-4,4-1 and then stop as all neighbors of 1 are visited. so we get total 3 edges with all 4 vertices.

so total weight becomes 3+1+4=8.

4. if we start from vertex 4, then set of edges obtained by our dfs() function is 4-2,2-1 and then stop as all neighbors of 1(i.e, 2 and 4) are visited. so we get total 2 edges with all 3 vertices which is not a spanning tree.

• So we get spanning trees in point 1 and 3 with weights 8 and 8 respectively. so according to this modfied dfs , we get our minimum spanning tree weight as 8.But there is a spanning tree possible of <8 of total weight i.e, 6 where set of edges are 1-2, 2-3, 2-4 with weights 2,3,1 respectively which have 4 vertices and 3 edges.
• So we proved by the above example that it is not always possible to get MST from the modification of dfs() stated above in the problem.

​​​​​​​Here is the pseudo code in c++ for the modified dfs() function in which ans is our vector<pair<int,int>> to store the final edges in MST(if obtained) and adj is adjacency list representation of graph:

void dfs( int v )

{
// mark this node as visited.
vis[v]=true;
// take initial weight to be INT_MAX.
int weight=INT_MAX;
// variable to store which neighbor of v has minimum weighted edge with v.
int neighbor;
// iterate to all neighbors of v.
for(auto u:adj[v])

{
// if unvisited.
if(!vis[u])

{
// compare weight of edge to previous minimum weight of edge obtained.
if(weight>W[{min(u,v),max(u,v)}])

{
weight=W[{min(u,v),max(u,v)}];
//save this neighbor u as we will recur for this.
neighbor=u;
}
}
}
// add this edge in answer vector to store edges of MST(if obtained).
ans.push_back({min(neighbor,v),max(neighbor,v)});
//recur for unvisited neighbor u such that W(u-v) is minimum.
dfs(neighbor);
return;
}

So this was my answer to your problem if it helped(maybe very little) you in any way then please upvote my solution and if you have any query regarding this please feel free to comment.

Thank you and have a wonderful day.