graph algorithms

Question 1

difference between BFS and DFS

Answer 1

BFS

1. BFS stands for Breadth-First Search.
2. BFS(Breadth-First Search) uses a Queue data structure for finding the shortest path.
3. BFS can be used to find single-source shortest path in an unweighted graph, because in BFS, we reach a vertex with minimum number of edges from a source vertex.
4. BFS is more suitable for searching vertices which are closer to the given source.
5. BFS considers all neighbors first and therefore not suitable for decision-making trees used in games or puzzles.
6. The Time complexity of BFS is O(V + E) when Adjacency List is used, where V stands for vertices and E stands for edges.

DFS
1. DFS stands for Depth First Search.
2. DFS(Depth First Search) uses Stack data structure.
In DFS, we might traverse through more edges to reach a destination vertex from a source.
3. DFS is more suitable when there are solutions away from the source.
4. DFS is more suitable for game or puzzle problems. We make a decision, then explore all paths through this decision. And if this decision leads to win situation, we stop.
5. The Time complexity of DFS is also O(V + E) when Adjacency List is used, where V stands for vertices and E stands for edges.
Here, children are visited before the siblings

Question 2

Difference between Prim’s and Kruskal’s algorithm for MST

Answer 2

Prim’s Algorithm

1. It starts to build the Minimum Spanning Tree from any vertex in the graph.
2. It traverses one node more than one time to get the minimum distance.
3. Prim’s algorithm has a time complexity of O(V^2), V being the number of vertices, and can be improved up to O(E log V) using Fibonacci heaps.
4. Prim’s algorithm gives connected components as well as it works only on a connected graph.
5. Prim’s algorithm runs faster in dense graphs.
6. Prim’s algorithm uses List Data Structure.

Kruskal’s Algorithm

1. It starts to build the Minimum Spanning Tree from the vertex carrying minimum weight in the graph.
2. It traverses one node only once.
3. Kruskal’s algorithm’s time complexity is O(E log V), V being the number of vertices.
4. Kruskal’s algorithm can generate forest(disconnected components) at any instant as well as it can work on disconnected components
5. Kruskal’s algorithm runs faster in sparse graphs.
6. Kruskal’s algorithm uses Heap Data Structure.

Question 3

What is the input and output for Dijkstra’s algorithm?

Answer 3

Input: graph = G(V, E) with positive weights.
output: dist array (the shortest distance from the source to each vertex) and prev array(indicating the previous vertex that the shortest path uses to get to each vertex).

Question 4

What is the running time of Dijkstra’s algorithm using min-heap (aka priority queue) data structure?

Answer 4

O((V+E)*logV)

Question 5

What is the main idea for Dijkstra’s algorithm?

Answer 5

The main idea of Dijkstra’s algorithm is to find the distances to the nearest nodes, then gradually expand the frontier of the search and determine the shortest paths to nodes that are further and further away. Since edge weights must be positive, there will never be a case where the shortest path must first go through a far away vertex (the path would already be longer than another one that had been found).

Question 6

What is the main idea for the Depth First Search algorithm?

Answer 6

The DFS algorithm is a recursive algorithm that uses the idea of backtracking.

This recursive nature of DFS can be implemented using stacks. The basic idea is as follows:

1. Pick a starting node and push all its adjacent nodes into a stack.
2. Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack.
3. Repeat this process until the stack is empty. 4. However, ensure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you visit the same node more than once, you may end up in an infinite loop.