Depth First Search [DFS]
Graph traversal algorithms are also called graph search algorithm. Two such algorithms for traversing the graphs : Depth First Search [DFS] Breadth First Search [BFS] Depth First Search [DFS]: DFS algorithm works in a manner similar to a preorder traversal of the trees. We encountered the following types of edge: Tree edge: encounter new vertex. Back edge: from descendant to ancestor. Forward edge: from ancestor to descendant. Cross edge: between a tree or subtree. To track the vertices two colours are enough: false → Vertex is unvisited. true → Vertex is visited. Source code in Java: import java.util.LinkedList; import java.util.Iterator; /** * * @author Rohan */ public class Graph { private int V; // No. of vertices // Array of lists for Adjacency List Representation private LinkedList<Integer> adj[]; /...