Graph Depth-First Search
Overview
Now that we know what BFS (Breadth First Search) is, we can proceed with its 'brother' - DFS (Depth First Search).
It's another way of traversal but is kind of opposite to what BFS is.
Remember BFS traverses horizontally, level by level? DFS goes downward, in depth first. And when it reaches an end (node that's not connected to an unvisited node), it goes back to where it started and continues the traversal in the next depth path.
A real world example of a Depth First Search is like exploring a forest (without GPS obviously). You start from one place and leave markers along the way. When you go back to a marker, you go another direction. Until all directions have been explored.
That being said - the implementation of DFS can be done either via stack data structure (iterative approach) or recursively. Let's take a look at the iterative approach now.
Choose a starting node. In our animation - it's the 'A' node.
Push it onto a stack data structure.
Then we pop it from the stack and mark it as visited (so we don't explore it again) and start exploring it - which means finding its neighbors and pushing them onto the stack.
Then we simply repeat these steps. At some point we will encounter a dead end from the first path but we will have the first node (first neighbour of the starting node) remaining in the stack and by popping it, we will continue on the exploration of the second path until we have traversed the full graph and the stack is empty.
That results in the following worst-case performances and memory:
Worst-case time complexity: O(V + E)
Worst-case space complexity: O(V)
Now that we know how DFS works, lets see its pros and cons.
Some of its pros are:
-
It generally uses less memory. BFS needs to keep track of all nodes in the current level before it could proceed with next level. In the animation we have small graphs as example but in real world scenarios, the increased memory usage could be an issue.
-
Situationally better - for the purpose of our application we may need quicker depth traversal like exploration of branches in Trees, solving a maze, or finding cycles in graphs (because the only way to get to a node that's marked as visited is through a cycle in the graph).
And the cons:
-
DFS would not find the shortest nor the most optimal path.
-
As with anything that has the word 'recursion' or 'backtracking' in its description - DFS needs extra caution during implementation because it could lead to infinite loops.
In conclusion, something to remember as a key and easy difference between BFS and DFS - BFS is generally used to find the shortest path in graphs while DFS is used to find the longest path.
Code
class Node:
def __init__(self, value):
self.value = value
self.neighbors = []
rootNode = Node('A')
nodeB = Node('B')
nodeC = Node('C')
nodeD = Node('D')
nodeE = Node('E')
nodeF = Node('F')
rootNode.neighbors.extend([nodeB, nodeC])
nodeB.neighbors.append(nodeD)
nodeC.neighbors.append(nodeE)
nodeD.neighbors.append(nodeF)
def depth_first_search(root):
stack = [root]
visited = set()
while stack:
node = stack.pop()
if node not in visited:
print(node.value)
visited.add(node)
for neighbor in reversed(node.neighbors):
if neighbor not in visited:
stack.append(neighbor)
depth_first_search(rootNode)
class Node {
constructor(value) {
this.value = value;
this.neighbors = [];
}
}
const rootNode = new Node('A');
const nodeB = new Node('B');
const nodeC = new Node('C');
const nodeD = new Node('D');
const nodeE = new Node('E');
const nodeF = new Node('F');
rootNode.neighbors.push(nodeB, nodeC);
nodeB.neighbors.push(nodeD);
nodeC.neighbors.push(nodeE);
nodeD.neighbors.push(nodeF);
function depthFirstSearch(root) {
const stack = [root];
const visited = new Set();
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
console.log(node.value);
visited.add(node);
for (let i = node.neighbors.length - 1; i >= 0; i--) {
if (!visited.has(node.neighbors[i])) {
stack.push(node.neighbors[i]);
}
}
}
}
}
depthFirstSearch(rootNode);
import java.util.*;
class Node {
String value;
List<Node> neighbors;
Node(String value) {
this.value = value;
neighbors = new ArrayList<>();
}
}
public class Main {
public static void main(String[] args) {
Node rootNode = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
rootNode.neighbors.addAll(Arrays.asList(nodeB, nodeC));
nodeB.neighbors.add(nodeD);
nodeC.neighbors.add(nodeE);
nodeD.neighbors.add(nodeF);
depthFirstSearch(rootNode);
}
static void depthFirstSearch(Node root) {
Stack<Node> stack = new Stack<>();
Set<Node> visited = new HashSet<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
if (!visited.contains(node)) {
System.out.println(node.value);
visited.add(node);
Collections.reverse(node.neighbors);
for (Node neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
}
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 6
struct Node {
char label;
struct Node* neighbors[MAX_NODES];
int numNeighbors;
int visited;
};
struct Node* createNode(char label) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->label = label;
node->numNeighbors = 0;
node->visited = 0;
return node;
}
void addEdge(struct Node* node1, struct Node* node2) {
if (node1->numNeighbors < MAX_NODES) {
node1->neighbors[node1->numNeighbors++] = node2;
}
}
struct Node* stack[MAX_NODES];
int top = -1;
void push(struct Node* node) {
stack[++top] = node;
}
struct Node* pop() {
return stack[top--];
}
void dfs(struct Node* startNode) {
push(startNode);
while (top != -1) {
struct Node* currentNode = pop();
if (!currentNode->visited) {
printf("%c ", currentNode->label);
currentNode->visited = 1;
}
for (int i = currentNode->numNeighbors - 1; i >= 0; i--) {
struct Node* neighbor = currentNode->neighbors[i];
if (!neighbor->visited) {
push(neighbor);
}
}
}
}
int main() {
struct Node* nodes[MAX_NODES];
for (int i = 0; i < MAX_NODES; i++) {
nodes[i] = createNode('A' + i);
}
addEdge(nodes[0], nodes[1]);
addEdge(nodes[0], nodes[2]);
addEdge(nodes[1], nodes[3]);
addEdge(nodes[2], nodes[4]);
addEdge(nodes[3], nodes[5]);
dfs(nodes[0]);
return 0;
}
<?php
class Node {
public $value;
public $neighbors;
public function __construct($value) {
$this->value = $value;
$this->neighbors = array();
}
}
function depthFirstSearch($root) {
$stack = array();
$visited = array();
array_push($stack, $root);
while (!empty($stack)) {
$node = array_pop($stack);
if (!in_array($node, $visited)) {
echo $node->value . " ";
array_push($visited, $node);
// Push unvisited neighbors onto the stack in reverse order
$neighbors = array_reverse($node->neighbors);
foreach ($neighbors as $neighbor) {
if (!in_array($neighbor, $visited)) {
array_push($stack, $neighbor);
}
}
}
}
}
$rootNode = new Node('A');
$nodeB = new Node('B');
$nodeC = new Node('C');
$nodeD = new Node('D');
$nodeE = new Node('E');
$nodeF = new Node('F');
$rootNode->neighbors[] = $nodeB;
$rootNode->neighbors[] = $nodeC;
$nodeB->neighbors[] = $nodeD;
$nodeC->neighbors[] = $nodeE;
$nodeD->neighbors[] = $nodeF;
depthFirstSearch($rootNode);
?>