DFS of a Cyclic Graph Editorial

Practice Problem Link: DFS of a Cyclic Graph

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a graph compute its DFS traversal.

The graph has n nodes indexed 0 to n-1. It is given in the form of an adjacency list.

Compute the DFS from the node indexed 0. Follow the order given in the adjacency list when choosing path.

Approach

• Start from the root node and mark the node as visited.
• Add the marked node in the answer array.
• Now traverse its adjacent nodes and for every unmarked adjacent node recursively repeat the above steps.

Analysis

• Time Complexity: O(V + E)
• Auxiliary Space Complexity: O(V)

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

Implementation

C++

void dfsUtil(int root, vector<vector<int>> &adjList, vector<int> &traversal, vector<bool> &isVisited) {
	isVisited[root] = true;
	traversal.push_back(root);
	for(int i = 0; i < adjList[root].size(); i++) {
		int node = adjList[root][i];
		if (isVisited[node] == false) {
			dfsUtil(node, adjList, traversal, isVisited);
		}
	}
}
vector<int> dfs(vector<vector<int>> adjList) {
	vector<int> traversal;
	vector<bool> isVisited (adjList.size(), false);
    dfsUtil(0, adjList, traversal, isVisited);
	return traversal;
}

Java

class Solution {
	void dfsUtil(int root, ArrayList<Integer>[] adjList, ArrayList<Integer> traversal, boolean[] isVisited) {
		isVisited[root] = true;
		traversal.add(root);
		for(int i = 0; i < adjList[root].size(); i++) {
			int node = adjList[root].get(i);
			if (isVisited[node] == false) {
				dfsUtil(node, adjList, traversal, isVisited);
			}
		}
	}
    ArrayList<Integer> dfs(ArrayList<Integer>[] adjList) {
        ArrayList<Integer> traversal = new ArrayList<Integer>();
		boolean[] isVisited = new boolean[adjList.length];
		dfsUtil(0, adjList, traversal, isVisited);
		return traversal;
    }
}