Graph Traversal BFS and DFS

When it comes to traversing graphs, there are two main algorithms that come to mind: breadth-first search (BFS) and depth-first search (DFS).

Both have their own strengths and weaknesses, so which one you choose to use depends on the situation.

Lets go in details of each one by one

BFS graph traversal is a technique for traversing a graph in which each vertex is visited in turn, with each visit discovering all unvisited vertices that are reachable from the current vertex.

The technique can be implemented using a queue data structure, and is often used in conjunction with a search algorithm to find specific elements within a graph.

BFS was first described by E. F. Moore in his 1959 paper “A method for obtaining shortest paths from a given source in a graph”.

BFS has a wide range of applications:

• Including network routing,
• Garbage collection,
• Model checking.
• Analysing the structure of social networks.

The basic idea behind BFS is to start from a given vertex and explore all of its neighbours before moving on to the next vertex. This is done using a queue, which stores the vertices that have been visited but not yet explored.

The Algorithm proceeds as follows:

1. Start at a given vertex v.

2. Mark v as visited and enqueue it into the queue.

3. While the queue is not empty:

4. Dequeue a vertex u from the queue.

5. For each unvisited neighbour w of u:

6. Mark w as visited.

7. Enqueue w into the queue.

Time complexity of BFS Graph Traversal is O(|V|+|E|)

Space complexity of BFS Graph Traversal is O(|V|+|E|)

Where |V| is the number of vertices and |E| is the number of edges.

Space complexity is because the algorithm explores every vertex and every edge in the worst case. Since the queue can store at most |V| vertices and |E| edges.

DFS graph traversal is a method of traversing a graph in which each vertex is visited in turn, starting from some arbitrary vertex, v. The edges incident to v are explored recursively until all incident edges have been explored or a goal vertex is reached.

Basic uses of DFS are:

• Finding all nodes reachable from a given starting node
• Testing if a graph is connected
• Finding the shortest path between two nodes
• Finding all cycles in a graph
• Topological sorting
• Finding strongly connected components

The basic idea of a depth-first search is to go as deep as possible into the graph before backtracking and visiting other vertices.

The Algorithm proceeds as follows

1. Choose a starting node and push it onto the stack
2. While the stack is not empty, pop the top node off the stack and visit it
3. Push all of the node’s unvisited neighbours onto the stack
4. Mark the current node as visited
5. Repeat steps 2–4 until all nodes have been visited

Time complexity of a DFS graph traversal is O(V+E),

Space complexity of DFS graph traversal is O(V+E)

Where V is the number of vertices and E is the number of edges.

In general cases DFS needs a lot more storage than BFS as it has to maintain a long stack

HERE IS A VIDEO VISUALISATION OF THE TWO WITH EXAMPLE

BFS(Left) - DFS(right)

Here are the implementation of both in python