Skip to main content

DFS on Undirected Graph

This technique traverses an undirected graph in a depth-first search manner.

How to Identify​

  • Data Structure Involves: Graph, Array, HashTable
  • Question Type: When the input data has dependencies (undirected edges) between items.

Example​

Number of Connected Components in an Undirected Graph​

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example
Example 1:
     0          3
     |          |
     1 --- 2    4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:
     0           4
     |           |
     1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
Typescript
function countComponents(edges: number[][], n: number): number {
    const visited: boolean[] = new Array(n).fill(false)
    let count = 0
    const neighbors = buildGraph(edges, n)

    for(let i=0; i<n; i++){
        if(visited[i] === false) {
            count++
            dfs(neighbors, visited, i)
        }
    }

    return count
}

function buildGraph(edges: number[][], n: number) {
    const neighbors: {[key: number]: number[]} = {}
    
    for(let i=0; i<n; i++){
        neighbors[i] = []
    }

    for(let i=0; i<edges.length; i++){
        const [x, y] = edges[i]
        neighbors[x].push(y)
        neighbors[y].push(x)
    }

    return neighbors
}

function dfs(neighbors: {[key: number]: number[]}, visited: boolean[], node: number){
    visited[node] = true

    for(const neighbor of neighbors[node]){
        if(visited[neighbor] === false)
        dfs(neighbors, visited, neighbor)
    }
}
ProblemsDifficulty
1Clone GraphMedium
2Graph Valid Tree (Leetcode Premium)Medium
3Number of Connected Components in an Undirected Graph (Leetcode Premium)Medium