Depth First Search Code Example

Let’s suppose we have a graph that has 8 nodes, A through H. The edges between the nodes are described below.

A has an edge to node B.
B has an edge to node G.
B has edges to nodes C and D.
C has an edge to node D.
D has an edge to node E.
E has edges to nodes F and G.
G has an edge to node H.

Graph for our example

The edges of our graph are directed that is, an edge from B to C means we can go from B to C but not the other way around e.g. C to B.

If you we the algorithm in the code panel on the right, it will print:

A B G H C D E F

Here, the the DFS algorithm starts at node A and visits its neighbors B, G, H, C, D, E, F in that order

Our DFS algorithm starts at node A and visits its only neighbor: node B.
Then the algorithm visits node G, which is a neighbor of B, and then node H, which is a neighbor of G.
After visiting all the nodes reachable from node A, the algorithm backtracks to node B and visits its other neighbor: node C.
Node C has a neighbor, node D, which the algorithm then visits.
Finally, the algorithm backtracks to node E and visits its neighbors, nodes F and G, in that order (G is already visited so it’s not printed.)

The visited property of Node is used to keep a track of which nodes have been visited by the DFS algorithm already. It is important to mark a node as visited when it is first encountered, as this helps the algorithm avoid visiting the same node multiple times and getting stuck in an infinite loop. For example if we have the following graph:

A -- B
|    |
C -- D

If we start the DFS algorithm at node A and do not mark nodes as visited, the algorithm will visit node B and then follow the the graph through nodes D and C back to A. It will then repeat indefinitely and will get stuck in an infinite loop. This is why we must mark nodes as visited.

import java.util.LinkedList;

// Class to represent a node in the graph
class Node {
    String name;
    LinkedList neighbors;
    boolean visited;

    public Node(String name) {
        this.name = name;
        this.neighbors = new LinkedList<>();
        this.visited = false;
    }
}

public class DepthFirstSearch {
    public static void main(String[] args) {
        // Create eight nodes
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        Node G = new Node("G");
        Node H = new Node("H");

        // Add edges: A -> B
        A.neighbors.add(B);
        // B -> G, B -> C, B -> D
        B.neighbors.add(G);
        B.neighbors.add(C);
        B.neighbors.add(D);
        // C -> D
        C.neighbors.add(D);
        // D -> E
        D.neighbors.add(E);
        // E -> F, E -> G
        E.neighbors.add(F);
        E.neighbors.add(G);
        // G -> H
        G.neighbors.add(H);

        // Put all nodes in a linked list
        Node[] nodes = {A, B, C, D, E, F, G, H};

        // Perform DFS starting from node A
        dfs(A);
    }

    public static void dfs(Node node) {
        // Mark the current node as visited
        node.visited = true;
        System.out.print(node.name + " ");

        // Follow all edges from current Node to all of its neighbors
        for (Node neighbor : node.neighbors) {
            if (!neighbor.visited) {
                dfs(neighbor);
            }
        }
    }
}visited = set() # set to store visited vertices or nodes

# The algorithm starts at the root node (specified by the node parameter) and adds 
# it to the visited set. It then follows the edges of the graph, visiting each neighbor
# of the current node and calling the dfs function recursively on each neighbor. It 
# continues this process until it has visited all the nodes in the graph.
def dfs(graph, node): 
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor)
    
        
# This dictionary to represent the graph, where the keys are 
# the nodes and the values are sets of nodes that are connected 
# to the key node by an edge. 
graph = {'A': ['B'],
         'B': ['G', 'C', 'D'],
         'C': ['D'],
         'D': ['E'],
         'E': ['F', 'G'],
         'F': set(),
         'G': ['H'],
         'H': set()}

# Call the graph starting at Node A
dfs(graph, 'A')

# Output
# A
# B
# G
# H
# C
# D
# E
# F
package main

import "fmt"

// A map to represent the graph, where the keys are the nodes
// and the values are slices of nodes that are connected to the key node by an edge
var graph = map[string][]string{
	"A": {"B"},
	"B": {"G", "C", "D"},
	"C": {"D"},
	"D": {"E"},
	"E": {"F", "G"},
	"F": {},
	"G": {"H"},
	"H": {},
}

// DFS performs a depth-first search on the graph, starting at the specified node
func DFS(graph map[string][]string, node string) {
	// Print the current node
	fmt.Print(node + " ")

	// Mark the current node as visited
	visited[node] = true

	// Visit each neighbor of the current node
	for _, neighbor := range graph[node] {
		if !visited[neighbor] {
			DFS(graph, neighbor)
		}
	}
}

var visited = make(map[string]bool) // set to store visited nodes

func main() {
	// Call DFS starting at node A
	DFS(graph, "A")
}

// Output
// A B G H C D E F 
const graph = {
	A: ['B'],
	B: ['G', 'C', 'D'],
	C: ['D'],
	D: ['E'],
	E: ['F', 'G'],
	F: [],
	G: ['H'],
	H: [],
};

const visited = new Set(); // set to store visited nodes

// DFS performs a depth-first search on the graph, starting at the specified node
function DFS(graph, node) {
	// Print the current node
	console.log(node);

	// Mark the current node as visited
	visited.add(node);

	// Visit each neighbor of the current node
	for (const neighbor of graph[node]) {
		if (!visited.has(neighbor)) {
		DFS(graph, neighbor);
		}
	}
}

// Call DFS starting at node A
DFS(graph, 'A');

// Output
// A
// B
// G
// H
// C
// D
// E
// F

# A hash to represent the graph, where the keys are the nodes 
# and the values are arrays of nodes that are connected to the key node by an edge
GRAPH = {
  'A' => ['B'],
  'B' => ['G', 'C', 'D'],
  'C' => ['D'],
  'D' => ['E'],
  'E' => ['F', 'G'],
  'F' => [],
  'G' => ['H'],
  'H' => [],
}

# DFS performs a depth-first search on the graph, starting at the specified node
def dfs(graph, node)
  # Print the current node
  puts node

  # Mark the current node as visited
  visited.add(node)

  # Visit each neighbor of the current node
  graph[node].each do |neighbor|
    dfs(graph, neighbor) unless visited.include?(neighbor)
  end
end

visited = Set.new # set to store visited nodes

# Call DFS starting at node A
dfs(GRAPH, 'A')

Depth First Search Code Example

Related Tutorials

DFS Applications

Depth-First Search

Breadth-First Search

Graphs

Related Videos