1. Do DFS and BFS find the same connected components of for a given graph? 2. :
ID: 3814253 • Letter: 1
Question
1. Do DFS and BFS find the same connected components of for a given graph?
2. : What is the necessary condition that DFS or BFS can find a path between any two vertices? If there is a path between two given vertices, do DFS and BFS always find the same path or not?
3. The test weighted graph is undirected. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph? The test graph is positive weighted. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph with negative weights?
4. Are a shortest path tree and a minimum spanning tree the same?
Explanation / Answer
1) Do DFS and BFS find the same connected components of for a given graph?
Answer:
In a forest graph the connected components of the graph is the subset of all the verices which have a connected path between them, it means there is a way to reach to every vertex of the component.
To find the connected component we can apply the DFS or BFS algorithm. To do that we initially
Start by labeling all vertices as unvisited. Then, iterate over the nodes in any order based on the DFS(Stack) and BFS(Queue) approach. For each node, if it's not already labeled as being in a connected component, run DFS/BFS from that node and mark all reachable nodes as being in the same connected component. If the node was already marked, skip it. This then discovers all connected component of the graph.
Here both DFS/BFS will give same connected component as they both ensures the connectivity between the nodes.
2)
What is the necessary condition that DFS or BFS can find a path between any two vertices? If there is a path between two given vertices, do DFS and BFS always find the same path or not?
Answer:
Both the graph traversals promises a complete traversal of the graph, visiting every vertex of the graph.
DFS uses the STACK Data structure for traversal whereas BFS uses the Queue Data structure. BFS uses more momory depending on the branching factor though BFS is a complete and optimal to find the shortest path between any two vertices in lowest depth possible.
In case of DFS, it is space efficient but it may find the a sub-optimal solution to find the path between two vertices, it stops at sub-optimal solution before finding the optimal solution.
3) The test weighted graph is undirected. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph? The test graph is positive weighted. Can you apply Dijkstra’s algorithm to find shortest paths for a weighted digraph with negative weights?
Answer:
Yes we can apply the Dijkstra’s algorithm to find the shortest paths for a weighted directed graph. It would be more similar to Prim's algorithm as it ensure's the connectivity between the node while creating the shortest path.
We start the algorithm with a given root, and maintain two sets where one (SPT) will contain the nodes included in the shortest path tree and the other one (VISITED) will keep whether the node has been visited yet or not. Initially the first set would be empty and second set will have 0 as with all the nodes.
V(0) = Node V has not visited yet
V(1) = Node V has visited.
Steps:
1) Assign the distane value as 0 for the source vertex so that it is picked first and infinite for all the other nodes.
2) while the SPT set doesn't include all the nodes we have to repeat the inner steps
a) Select a connected vertex u which is not visited and has mimimum distance value.
b) include u in SPT set.
c) Update distance value of all the adjacent vertices of u. to do that we need to iterate through all the adjacent nodes, for every node vertex v, if sum of distance value of u from source and weight e(u,v) is less than distance value of v then update the distance value of v.
Dijkstra’s Algorithm For negative weight:
As based on the above steps we decide the next vertex based on the mimimum weight. But in case of negative weighted graph there can be a situation when sum of path would come as negative sum and based on minimum selection we can pick that path and it can lead to cycle of negative sum.
Therefor Dijkstra’s algorithm is not designed for negative weithed graph because it may lead to negative cycle.
4)
Are a shortest path tree and a minimum spanning tree the same?
Answer:
Spanning tree of a graph G(V,E) is the tree E=(V,E') where E' is subset of E and E covers all the vertices. The cost of spanning tree is the sum of all the weight on the edges in the tree and minimum spanning tree is a tree with minimum cost.
A Shorted path tree is a tree of a graph G(V,E) which covers all the vertices V with E' edges and here E' is subset of E. Here it ensures the path is minimum.
Therefor both Shortest path tree and mimimum spanning tree is same.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.