Graph Traversal🔗

Connected Components🔗

Can be done using Union-Find and BFS also.

// inside int main()---this is the DFS solution
numCC = 0;
  dfs_num.assign(V, UNVISITED); // sets all vertices’ state to UNVISITED
  for (int i = 0; i < V; i++) // for each vertex i in [0..V-1]
    if (dfs_num[i] == UNVISITED) // if vertex i is not visited yet
    printf("CC %d:", ++numCC), dfs(i), printf("\n"); // 3 lines here!

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/

Flood Fill - Labeling/Coloring the Connected Components🔗

This version actually counts the size of each component and colors it.

int dr[] = {1,1,0,-1,-1,-1, 0, 1}; // trick to explore an implicit 2D grid
int dc[] = {0,1,1, 1, 0,-1,-1,-1}; // S,SE,E,NE,N,NW,W,SW neighbors
int floodfill(int r, int c, char c1, char c2) { // returns the size of CC
  if (r < 0 || r >= R || c < 0 || c >= C) return 0; // outside grid
  if (grid[r][c] != c1) return 0; // does not have color c1
  int ans = 1; // adds 1 to ans because vertex (r, c) has c1 as its color
  grid[r][c] = c2; // now recolors vertex (r, c) to c2 to avoid cycling!
  for (int d = 0; d < 8; d++)
    ans += floodfill(r + dr[d], c + dc[d], c1, c2);
  return ans; // the code is neat due to dr[] and dc[]
}

NOTE: this direction traversal can be simple using vector<vector<int>> dirs to represent directions to traverse in.

Cycle Detection🔗

Directed Graph (DFS)

Undirected Graph (DFS or BFS(Kahn’s Algorithm))

DFS on Directed Graph🔗

we need to keep track of path we used to come to a node. Without recStack, the algorithm cannot identify back edges properly, which are a key indicator of cycles in a directed graph.

In a directed graph, a back edge points from a node to one of its ancestors in the current DFS path.

Here visited only keeps track of nodes that have been explored, for example if you again run dfs on different node but come across a node that is visited doesn’t mean it is forming a cycle but rec Stack keeps track of that.

1 → 2 → 3 → 4
    ↘   ↗
      5

// above graph lets say traverses straight from 1->2->3->4->5, marks everything visited.
// when branching again happens at 2, we see wait 3 is marked visited, this should not happen there fore its important to keep track of current path.

bool dfsDirected(int v, vector<vector<int>> &adj, vector<bool> &visited, vector<bool> &recStack) {
    visited[v] = true;
    recStack[v] = true;

    for (int neighbor : adj[v]) {
        if (!visited[neighbor]) {
            if (dfsDirected(neighbor, adj, visited, recStack))
                return true;
        } else if (recStack[neighbor]) {
            return true; // Cycle detected
        }
    }

    recStack[v] = false;
    return false;
}

bool hasCycleDirected(vector<vector<int>> &adj, int n) {
    vector<bool> visited(n, false);
    vector<bool> recStack(n, false);
    for (int i = 0; i < n; ++i)         // check all nodes
        if (!visited[i])
            if (dfsDirected(i, adj, visited, recStack))
                return true;
    return false;
}

Kahn’s Algorithm🔗

bool hasCycleKahn(vector<vector<int>> &adj, int n) {
    vector<int> inDegree(n, 0);

    // Calculate in-degree
    for (int i = 0; i < n; ++i)
        for (int neighbor : adj[i])
            inDegree[neighbor]++;

    // put zero-indegree nodes in on queue
    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (inDegree[i] == 0)
            q.push(i);

    int count = 0; // Number of processed nodes
    while (!q.empty()) {
        int v = q.front(); q.pop();
        count++;

        for (int neighbor : adj[v]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0)
                q.push(neighbor);
        }
    }
    return count != n; // Cycle exists if not all vertices are processed
}

DFS on Undirected Graph🔗

Key Idea: During DFS, if you encounter a visited vertex that is not the parent of the current vertex, a cycle exists.

bool dfs(int v, int parent, vector<vector<int>> &adj, vector<bool> &visited) {
    visited[v] = true;
    for (int neighbor : adj[v]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, v, adj, visited))
                return true;
        } else if (neighbor != parent)
            return true; // Cycle detected
    }
    return false;
}

bool hasCycleUndirected(vector<vector<int>> &adj, int n) {
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i)
        if (!visited[i])
            if (dfs(i, -1, adj, visited))
                return true;
    return false;
}

Bipartite(or 2/bi-colorable) Graph Check🔗

// inside int main()
  queue<int> q; q.push(s);
  vi color(V, INF); color[s] = 0;
  bool isBipartite = true; // addition of one boolean flag, initially true
  while (!q.empty() & isBipartite) { // similar to the original BFS routine
    int u = q.front(); q.pop();
    for (int j = 0; j < (int)AdjList[u].size(); j++) {
      ii v = AdjList[u][j];
      if (color[v.first] == INF) { // but, instead of recording distance,
        color[v.first] = 1 - color[u]; // we just record two colors {0, 1}
        q.push(v.first); }
      else if (color[v.first] == color[u]) { // u & v.first has same color
        isBipartite = false; break; } } } // we have a coloring conflict

Problems on DFS/BFS🔗

Problem	Concept	Approach
Number of Provinces	DFS on adjacency matrix	Calculate connected components using a custom DFS implementation. Iterate through unvisited nodes, recursively traverse neighbors via adjacency matrix.
Rotting Oranges	BFS for shortest path	Use BFS starting from all rotten oranges simultaneously. Simulate the rotting process and track total and rotten orange counts to determine if any fresh oranges remain disconnected.
Flood Fill	BFS / Flood Fill	Perform BFS to change connected cells to the new color. Use the original color to track visited cells instead of a separate array.
Course Schedule	Topological Sort (Kahn’s Algo)	Use Kahn's Algorithm for topological sorting. Challenge: Solve using a DFS approach by detecting cycles in the graph.
01 Matrix	Modified BFS	Initialize BFS from all 0-value cells with a queue storing `{i, j, distance}`. Increment distances during BFS traversal.
Surrounded Regions	Boundary DFS/BFS	Traverse the board boundary and mark connected `O` regions. Any unmarked `O` regions are captured. Ensure comparisons are done on the board's characters.
Number of Enclaves	Boundary BFS/DFS	Start BFS from boundary `1`s, marking reachable land cells. Count unmarked `1`s for enclosed regions.
Word Ladder	BFS with transformation	Generate all possible transformations of each word in BFS. Use unordered maps to check validity and track visited words.
Word Ladder II	BFS with path reconstruction	Solve using BFS for shortest path. Use parent tracking for reconstructing paths. Avoid DFS as it explores all paths and may result in TLE.
Is Graph Bipartite	BFS/DFS with color assignment	Check bipartiteness using BFS/DFS. Assign colors alternately and ensure there are no conflicts. Handle disconnected components by applying the algorithm to all nodes.

Number of Distinct Islands🔗

This problem requires identifying the shapes of the encountered island. The way to approach this problem is creating a canonical hash for the dfs we perform on each island.

Problem: https://leetcode.com/problems/number-of-distinct-islands/

Given a 2D array grid 0’s and 1’s island as a group of 1’s representing land connected by 4-neighbors.

Count number of distinct islands. An island is considered to be same as another if and only if one island can be translated (and not rotated/reflected) to equal the other.

Hmm make a island into a string xD and then store it in the map (kind of like serialization) , now for each island check before whether its stored in map then its not distinct and don’t count it in result.

Now how to serialize : Create a traversal strings representing traversal DRLU representing the down,right,left,up!

  vector<vector<int>> dirs = {{0, 1, 'R'}, {1, 0, 'U'}, {-1, 0, 'L'}, {0, -1, 'D'}};
  void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited,string& island){
      visited[i][j] = true;

      for(auto dir: dirs){
          // neighbors
          int x = i + dir[0];
          int y = j + dir[1];

          if(x < 0 || y < 0 || x >= grid.size()||
          y >= grid[0].size()||visited[x][y] || grid[x][y] == 0)
              continue;

          island += dir[2];
          dfs(grid, x, y, visited, island);      
      }
      island+="#";
  }
  int numDistinctIslands(vector<vector<int>>& grid){
      int m = grid.size(), n = grid[0].size(), i, j;
      unordered_set<string> islands;
      vector<vector<bool>> visited(m,vector<bool>(n,false));

      for(i = 0; i< m; i++){
          for(j = 0; j < n; j++)
              if(grid[i][j] == 1 && !visited[i][j]){
                  string island_pattern = "";
                  dfs(grid, i, j, visited, island_pattern);
                  islands.insert(island_pattern);
              }
      }
      return (int) islands.size();
  }