Depth First Search Algorithm

There are many ways to traverse a graph and a tree.

One of the best ways for traversing a graph is by using the Depth First Search algorithm.

In a graph, the DFS selects a random node or an index as a root.

Once it picks a root, it explores as far as possible along each branch of the tree or a graph. 

When it visits a node, it marks that node as visited so that it does not have to revisit the same node again.

This DFS algorithm continues visiting connected nodes until there is no unmarked adjacent node.

After it searches all the adjacent nodes, it backtracks and repeats the process for a new node.

Down below is an example C++ implementation of DFS.

The algorithm is simple.

Check the Visited node as visited (ex. Visitied[Current_Node_Index] = true)

Traverse all the adjacent and unvisited nodes and call the recursive function with the index of the adjacent node.

If there are unconnected nodes from the root node, you may find them from the array or the list that are marked as unvisited.

References:

    

    https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/