DFS

Complete

Summary

Depth first search(DFS)

recursive, implicit stack
iterative, stack

Time complexity

using an adjacency list
average case: - at every vertex, visit self and check all neighbours

worse case: - complete graph
best case: - single path/tree
using adjacency matrix/edge list

be careful when choosing between graph DS

Concept

Algorithm

recursively call DFS on every neighbour of the current node
avoid cycles by tracking visited nodes

java

List<List<Integer>> AL; // O(V+E) only using adjacency list
List<Boolean> visited = new ArrayList<>(Collections.nCopies(V, false)); // keep track of visited vertices

void dfs(int u) {
	visited.set(u, true);   // visit self, currently like preorder traversal
	// do something
			
	for (int v : AL.get(u)) // for all neighbouring vertices
		if (!visited.get(v))
			dfs(v);             // call DFS recursively if not yet visited
}

only one neighbour is pushed onto the implicit stack at any time, it has to be popped before the next neighbour is pushed, the stack grows linearly

DFS spanning tree

4-pan: dfs(0)

curr | stack
_    | [ 0 ]
0    | [ 0, 1 ]
1    | [ 0, 1, 3 ]
3    | [ 0, 1, 3, 2 ]
2    | [ 0, 1, 3 ]
3    | [ 0, 1, 3, 4 ]
4    | [ 0, 1, 3 ]
3    | [ 0, 1 ]
1    | [ 0 ]
0    | [ ]

DFS on disconnected graphs

still
use to count connected components

java

List<List<Integer>> al; // O(V+E) only using adjacency list
List<Boolean> visited;  // keep track of visited vertices

void dfs(int u) {
	visited.set(u, true);   // visit self, currently like preorder traversal
	// do something
			
	for (int v : al.get(u)) // for all neighbouring vertices
		if (!visited.get(v))
			dfs(v);             // call DFS recursively if not yet visited
}

for (int i = 0; i < visited.length(); i++)
	if (!visited.get(i))
		dfs(i); // if there are any vertices not connected to the first vertex, this will find and call DFS on them

Cycle detection

tree edge - essential edge in the DFS spanning tree
back edge - an edge to a node that has been visited, forming a cycle
forward edge - an extra edge to an node that has been fully visited, therefore no cycle

java

List<Integer> visited = new ArrayList<>(Collections.nCopies(V, 0)); // 0 not visited

boolean dfs_cycle(int u) {
	visited.set(u, 1); // 1 (partially) visited, done preorder

	boolean hasCycle = false;
	for (int v: al.get(u)) {
		if (visited.get(v) == 0)
			hasCycle |= dfs_cycle(v);
		else if (visited.get(v) == 1)
			hasCycle = true;
			
		if (hasCycle)
			break;
	}
	visited.set(u, 2); // 2 (fully) visited, done postorder
	return hasCycle;
}

3 vertex DAG: dfs_cycle(0)

3-cycle: dfs_cycle(0)

5 vertex directed: dfs_cycle(0)

Application

Leetcode: Keys and Rooms

adjacency list

java

List<List<Integer>> al;
List<Boolean> visited;

void dfs(int u) {
	visited.set(u, true); // track visitation
	for (int v : al.get(u)) // for all neighbours
		if (!visited.get(v))
			dfs(v); // run dfs if not already visited
}

public boolean canVisitAllRooms(List<List<Integer>> rooms) {
	am = rooms;
	int n = am.size();
	visited = new ArrayList<>(Collections.nCopies(n, false));

	dfs(0);
	return !visited.contains(false);
}

Leetcode: Reorder Routes to Make All Paths Lead to the City Zero

graph: tree
edge list, with adjacency list that indexes the edge list

java

List<List<Integer>> idx;
List<Boolean> visited;
int[][] conn;

int countReverse(int u) {
	int out = 0;
	for (int i : idx.get(u)) {
		if (visited.get(i))
			continue; // if already visited this edge, skip
		visited.set(i, true); // mark edge as visited

		int[] edge = conn[i];
		if (edge[0] == u)
			out += countReverse(edge[1]) + 1; // u -> v, we must reverse this
		else
			out += countReverse(edge[0]); // v -> u, dont need to reverse
	}
	return out;
}

public int minReorder(int n, int[][] connections) {
	conn = connections; // el
	visited = new ArrayList<>(Collections.nCopies(connections.length, false)); // keep track of visited edges
	idx = new ArrayList<>(); // al that maps to an element in the el
	for (int i = 0; i < n; i++)
		idx.add(new ArrayList<>()); // cannot use nCopies for Objects

	for (int i = 0; i < connections.length; i++) {
		idx.get(connections[i][0]).add(i);
		idx.get(connections[i][1]).add(i);
	}
	// System.out.println(idx);

	return countReverse(0);
}

Leetcode: Course Schedule

cycle detection

java

List<List<Integer>> al;
List<Integer> visited;

boolean dfs_cycle(int u) {
	visited.set(u, 1); // 1 (partially) visited

	boolean hasCycle = false;
	for (int v: al.get(u)) 
		if (visited.get(v) == 0)
			hasCycle |= dfs_cycle(v);
		else if (visited.get(v) == 1) {
			hasCycle = true;
			break;
		}
	visited.set(u, 2); // 2 (fully) visited
	return hasCycle;
}

public boolean canFinish(int numCourses, int[][] prerequisites) {
	// [a, b] represents b -> a

	// set up al
	al = new ArrayList<>();
	for (int i = 0; i < numCourses; i++) 
		al.add(new ArrayList<>());
	
	// set up visited
	visited = new ArrayList<>(Collections.nCopies(numCourses, 0)); // 0 not visited

	// convert edge list to adjacency list
	for (int[] prereq : prerequisites) 
		al.get(prereq[1]).add(prereq[0]);
	
	// in case graph is disconnected
	for (int i = 0; i < numCourses; i++) 
		if (visited.get(i) == 0)
			if (dfs_cycle(i))
				return false;
	
	return true;
}

Extra

Tikz template for drawing undirected edges as two parallel directed edges

latex

\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\tikzstyle{vertex}=[draw,circle,minimum size=18pt,inner sep=0pt]
\newcommand\sedge[4]{
  \draw[->,#1,transform canvas={shift={($(#3)!4pt!90:(#2)-(#3)$)}}] (#2) to node[auto,swap] {#4} (#3);
}
\begin{document}
\begin{tikzpicture}[thick]
\node[vertex] (A) at (0,0) {A};
\node[vertex] (B) at (3,0) {B};

\sedge{red}{A}{B}{test};
\sedge{blue}{B}{A}{test2};
\end{tikzpicture}
\end{document}