Depth First Search on Disconnected Components

Problem Statement

You are given a set of edges, n, where edges represents the connection between two nodes, n represents the number of nodes, and src represents the source node. Traverse each component in the graph in a depth-first fashion.

Example 1

Input:
edges = [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 5], [3, 4], [3, 5], [6, 7], [7, 8]]
n = 9
Output: 
0 1 2 5 3 4 6 7 8

Video Solution

Java Code

import java.util.ArrayList;
import java.util.List;

class DFSDisconnectedGraph {

    public List<List<Integer>> buildGraph(int[][] edges, int n) {
        List<List<Integer>> graph = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        return graph;

    }

    private void solve(int node, List<Integer> dfsAnswer, List<List<Integer>> graph, boolean[] visited) {
        dfsAnswer.add(node);
        visited[node] = true;
        for(int nbr : graph.get(node)) {
            if(!visited[nbr]) {
                solve(nbr, dfsAnswer, graph, visited);
            }
        }
    }

    private List<Integer> depthFirstSearch(int[][] edges, int n) {
        List<List<Integer>> graph = buildGraph(edges, n);
        List<Integer> dfsAnswer = new ArrayList<>();
        boolean[] visited = new boolean[n];
        for(int src = 0; src < n; src++) {
            if(!visited[src]) {
                solve(src, dfsAnswer, graph, visited);
            }
        }
        return dfsAnswer;
        
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 4}, {3, 5}, {6, 7}, {7, 8}};
        int n = 9;
        
        DFSDisconnectedGraph dfs = new DFSDisconnectedGraph();
        
        List<Integer> dfsAnswer = dfs.depthFirstSearch(edges, n);
        for(int node : dfsAnswer) {
            System.out.print(node + " ");
        }
    }
}

C++ Code

#include<bits/stdc++.h>
using namespace std;

class DFSDisconnectedGraph {
public:
    vector<vector<int>> buildGraph(vector<vector<int>>& edges, int n) {
        vector<vector<int>> graph(n);
        
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        return graph;
    }

    void solve(int node, vector<int>& dfsAnswer, vector<vector<int>>& graph, vector<bool>& visited) {
        dfsAnswer.push_back(node);
        visited[node] = true;
        for (int nbr : graph[node]) {
            if (!visited[nbr]) {
                solve(nbr, dfsAnswer, graph, visited);
            }
        }
    }

    vector<int> depthFirstSearch(vector<vector<int>>& edges, int n) {
        vector<vector<int>> graph = buildGraph(edges, n);
        vector<int> dfsAnswer;
        vector<bool> visited(n, false);
        for(int src = 0; src < n; src++) {
            if(!visited[src]) {
                solve(src, dfsAnswer, graph, visited);
            }
        }
        return dfsAnswer;
    }
};

int main() {
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 4}, {3, 5}, {6, 7}, {7, 8}};
    int n = 9;
    
    DFSDisconnectedGraph dfs;
    
    vector<int> dfsAnswer = dfs.depthFirstSearch(edges, n);
    for (int node : dfsAnswer) {
        cout << node << " ";
    }

    return 0;
}

Python Code

from typing import List

class DFSDisconnectedGraph:

    def __init__(self):
        pass

    def build_graph(self, edges, n):
        graph = []

        for i in range(n):
            graph.append(list())

        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])

        return graph

    def solve(self, node, dfs_answer, graph, visited):
        dfs_answer.append(node)
        visited[node] = True
        for nbr in graph[node]:
            if not visited[nbr]:
                self.solve(nbr, dfs_answer, graph, visited)

    def depthFirstSearch(self, edges, n):
        graph = self.build_graph(edges, n)
        dfs_answer = []
        visited = [False] * n
        for src in range(n):
            if visited[src] is not True:
                self.solve(src, dfs_answer, graph, visited)
        return dfs_answer

if __name__ == "__main__":
    edges = [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 5], [3, 4], [3, 5], [6, 7], [7, 8]]
    n = 9
    
    dfs = DFSDisconnectedGraph()
    
    dfs_answer = dfs.depthFirstSearch(edges, n)
    for node in dfs_answer:
        print(node, end=" ")

Javascript Code

class DFSDisconnectedGraph {

    buildGraph(edges, n) {
        const graph = new Array(n).fill(null).map(() => []);
        
        for (const edge of edges) {
            graph[edge[0]].push(edge[1]);
            graph[edge[1]].push(edge[0]);
        }

        return graph;
    }

    solve(node, dfsAnswer, graph, visited) {
        dfsAnswer.push(node);
        visited[node] = true;
        for (const nbr of graph[node]) {
            if (!visited[nbr]) {
                this.solve(nbr, dfsAnswer, graph, visited);
            }
        }
    }

    depthFirstSearch(edges, n) {
        const graph = this.buildGraph(edges, n);
        const dfsAnswer = [];
        const visited = new Array(n).fill(false);
        for (let src = 0; src < n; src++) {
            if (!visited[src]) {
                this.solve(src, dfsAnswer, graph, visited);
            }
        }
        return dfsAnswer;
    }
}

const edges = [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 5], [3, 4], [3, 5], [6, 7], [7, 8]];
const n = 9;

const dfs = new DFSDisconnectedGraph();
const dfsAnswer = dfs.depthFirstSearch(edges, n);
console.log(dfsAnswer.join(' '));

Go Code

package main

import "fmt"

type DFSDisconnectedGraph struct{}

func (dfs *DFSDisconnectedGraph) buildGraph(edges [][]int, n int) [][]int {
	graph := make([][]int, n)

	for i := 0; i < n; i++ {
		graph[i] = make([]int, 0)
	}

	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		graph[edge[1]] = append(graph[edge[1]], edge[0])
	}

	return graph
}

func (dfs *DFSDisconnectedGraph) solve(node int, dfsAnswer *[]int, graph [][]int, visited []bool) {
	*dfsAnswer = append(*dfsAnswer, node)
	visited[node] = true
	for _, nbr := range graph[node] {
		if !visited[nbr] {
			dfs.solve(nbr, dfsAnswer, graph, visited)
		}
	}
}

func (dfs *DFSDisconnectedGraph) depthFirstSearch(edges [][]int, n int) []int {
	graph := dfs.buildGraph(edges, n)
	dfsAnswer := make([]int, 0)
	visited := make([]bool, n)
	for src := 0; src < n; src++ {
	    if !visited[src] {
	        dfs.solve(src, &dfsAnswer, graph, visited)
	    }
	}
	return dfsAnswer
}

func main() {
	edges := [][]int{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 4}, {3, 5}}
	n := 9

	var dfs DFSDisconnectedGraph
	dfsAnswer := dfs.depthFirstSearch(edges, n)
	for _, node := range dfsAnswer {
		fmt.Printf("%d ", node)
	}
}

Complexity Analysis

Time Complexity: O(V + E), where V is the total number of vertices and E is the number of edges.
Space Complexity: O(V + E), where V is the total number of vertices and E is the number of edges.