# Grpahs Traversals

## Graphs Traversal

Graph traversals are techniques used to visit and explore all the nodes in a graph. They are fundamental operations for understanding and analyzing graphs. Two common graph traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).

## Depth-First Search(DFS)

Depth-First Search (DFS):

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a selected node and visits its adjacent nodes, then recursively visits the unvisited nodes in the same manner until there are no more unvisited nodes.

Here is the step-by-step process of DFS:

Choose a starting node and mark it as visited.

Explore one of the unvisited neighbors of the current node.

If an unvisited neighbor is found, mark it as visited and recursively apply DFS to that neighbor.

Repeat step 3 until there are no more unvisited neighbors.

Backtrack to the previous node and continue exploring other unvisited neighbors.

Repeat steps 2-5 until all reachable nodes are visited.

DFS can be implemented using either an explicit stack or by utilizing the call stack during recursive function calls. The algorithm keeps track of the visited nodes to avoid revisiting them and to prevent infinite loops in graphs with cycles.

DFS does not guarantee the shortest path between nodes and does not visit nodes in the order of their distance from the starting node. It explores one branch of the graph as deeply as possible before moving to the next branch. DFS is useful for tasks such as finding connected components, detecting cycles, and traversing trees.

The time complexity of DFS is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.

## Breadth-First Search(BFS)

Breadth-First Search (BFS):

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order. It starts at a selected node and visits all its neighbors before moving to the next level of nodes. In other words, it explores the nearest neighbors first before moving to the next level.

Here is the step-by-step process of BFS:

Choose a starting node and enqueue it (add it to a queue) and mark it as visited.

Dequeue a node from the queue and visit it.

Enqueue all the unvisited neighbors of the current node.

Mark the dequeued node as visited.

Repeat steps 2-4 until the queue is empty.

If there are still unvisited nodes in the graph, choose another unvisited node as the starting node and repeat steps 1-5.

BFS uses a queue data structure to keep track of the nodes to visit. The algorithm ensures that it explores all the nodes in the same level before moving to the next level. This property makes BFS suitable for finding the shortest path between two nodes, as it guarantees that it visits nodes in increasing order of their distance from the starting node.

BFS can be used to solve various graph-related problems such as finding connected components, detecting cycles, determining reachability between nodes, and finding the shortest path in unweighted graphs.

The time complexity of BFS is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.

BFS - A B C D E F G