Graphs

Graph representation

A directed graph consists of a finite set V of vertices (or nodes) and a set E of directed edges. A directed edge is an ordered pair of vertices (u, v).
In mathematical terms, a directed graph G=(V,E) is just a binary relation E ⊆ V × V on a finite set V.
An undirected graph is the special case of a directed graph where (u,v) ⊆ E if and only if (v,u) ∈ E.
Notational conventions: |V | = n, |E| = m
Representing graphs: (1) Adjacency matrix (2) Adjacency list

	Matrix	List
pros	1. check whether edge exists in a constant time. 2. easy to adapt if the graph is weighted. * suitable for dense graphs.	1. Allocates O(n + m) space. No unnecessary space. 2. Suitable for linear algorithms.
Cons	1. Requires Ω(n^2) space even if the graph is sparse. 2. Does not allow for linear time algorithm in sparse graphs.	1. Searching for an edge can take O(n) time.

BFS and DFS Summary

---	BFS	DFS
Shortest Path	Yes	No
Connected components	Yes	Yes
Bipartiteness	Yes	Yes
Cycle detection in undirected graph	No	Yes
Cycle detection in directed graph	No	Yes

BFS

BFS is used for the shortest path in the unweighted graph
The output of BFS is a tree.

BFS Pseudocode The code below is the answer for https://leetcode.com/problems/01-matrix/description/

private static int[][] dirs = new int[][] {
      {1, 0}, // up
      {-1, 0}, // down
      {0, 1}, // right
      {0, -1}, // left
    };
    public int[][] updateMatrix(int[][] mat) {
      Queue<int[]> bfsQ = new LinkedList<>();
      int[][] distance = new int[mat.length][mat[0].length];
      boolean[][] visited = new boolean[mat.length][mat[0].length];

      for (int i = 0; i < mat.length; i++) {
        for (int j = 0; j < mat[0].length; j++) {
          int cur = mat[i][j];
          if (cur == 0) {
            visited[i][j] = true;
            distance[i][j] = 0;
            bfsQ.add(new int[] {i, j});
          }
        }
      }
        
      while (!bfsQ.isEmpty()) {
        int[] curNode = bfsQ.poll();
        int curRow = curNode[0]; int curCol = curNode[1];
        for (int[] dir : dirs) {
          int newRow = curRow + dir[0]; int newCol = curCol + dir[1];
          if (isValid(newRow, newCol, visited)) {
            visited[newRow][newCol] = true;
            distance[newRow][newCol] = distance[curRow][curCol] + 1;
            bfsQ.add(new int[] {newRow, newCol});
          }
        } 
      }
      return distance;
    }

    private boolean isValid(int row, int col, boolean[][] visited) {
      if (row < 0 || row == visited.length || col < 0 || col == visited[0].length || visited[row][col] == true) return false;
      return true;
    }

DFS

Depth-first search (DFS): starting from a vertex s, explore the graph as deeply as possible, then backtrack.
DFS is naturally recursive and implemented using a stack.
In BFS, you have to check if the node is visited or not and set the node visted before the next layer of BFS tree is examined. However, in DFS, you can do such checks or any other valid or invalid checks lazily as a base case in the dfs function, instead of checking before calling the functions. The code becomes more readable and simpler.

private void dfs(int row, int col, char[][] grid) {
    if (row < 0 || col < 0 || row == grid.length || col == grid[0].length || grid[row][col] == '0') return;

    grid[row][col] = '0'; // mark visited

    for (int[] dir : dirs) {
        dfs(row + dir[0], col + dir[1], grid);
    }
}

Bipartiteness/2-colorability

Testing bipartiteness is same as seeing if we can color all the vertices in G using at most 2 colors so that no edge has two endpoints with the same color. A graph is bipartite if and only if it contains no odd length cycle. The reason that BFS can be used for bipartiteness is because the output of BFS is a tree. The BFS output tree has a concept of layers and for bipartiteness you don't want an edge between nodes in the same layer of the BFS output tree. DFS can be used for bipartiteness too.

Cycle detection in Directed Graphs using Topological Sorting

It has to be a DAG (Directed Acyclic Graph)
A source is a node with no incoming edges. A sink is a node with no outgoing edges.
Every DAG has at least one source and at least one sink.
Let G′ be the graph after a source node and its adjacent edges have been removed. Then G′ is a DAG.

Map<Character, Integer> indegreeMap = new HashMap<>();
Map<Character, Set<Character>> adjacencySetMap = new HashMap<>();
Queue<Character> queue = new LinkedList<>();
Set<Character> uniqueSet = new HashSet<>();

/**
 Add indegree 0 nodes to the queue
 while queue is not empty:
 1. poll from the queue
 2. remove the polled node from the unique node set

 For neighbor u of polled:
 1. Decrement the indegree value by 1
 2. if indegree is 0, add it to the queue
 */
// Step 1. put all the indegree of 0 into the inMap
for (Map.Entry<Character, Integer> entry : indegreeMap.entrySet()) {
    char curChar = entry.getKey(); int count = entry.getValue();
    if (count == 0) {
        queue.add(curChar);
    }
}

while (!queue.isEmpty()) {
    char polled = queue.poll();
    uniqueSet.remove(polled);

    Set<Character> neighbors = adjacencySetMap.get(polled);
    for (char neighbor : neighbors) {
        indegreeMap.put(neighbor, indegreeMap.get(neighbor) - 1);
        if (indegreeMap.get(neighbor) == 0) queue.add(neighbor);
    }
}
// there is a cycle if uniqueSet is not emptied out.

Minimum Spaning Tree

Prim's Algorithm

Start with a root node s.
Greedily grow a tree outward from s by adding the node that can be attached as cheaply as possible at every step.

Kruskal's algorithm

Kruskal Pseudocode

DFS - articulation points
DFS - bridges
Cycle detection

Undirected graphs
Topological ordering
Union Find
Minimum Spanning Tree(Kruskal's and Prim's)

Union and Find

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf

Plain Union and Find

Time complexity: O(N) for union and find where N is the number of nodes
Space complexity: O(N) for roots

int numberOfNodes = 5; // number of nodes
int[] roots = makeSets(numberOfNodes);

public int[] makeSets(int numberOfNodes) {
    // setting the root for every node its own node.
    int[] roots = new int[numberOfNodes];
    for (int i = 0; i < roots.length; i++) {
        roots[i] = i;
    }
    return roots;
}

public int findIterative(int node) {
    while (roots[node] != node) {
        node = roots[node];
    }
    return node;
}

public int findRecursive(int node) {
    if (roots[node] == node) return node;
    return findRecursive(roots[node]);
}

public void union(int a, int b) {
    int a_root = findIterative(a);
    int b_root = findRecursive(b);
    if (a_root == b_root) return;
    roots[a] = b_root; // arbitrarily changing root of a with root of b.
}

Union by size with plain find

Time complexity: O(log N) for both find and union.
Space complexity: O(N)

  int numberOfNodes = 5; // number of nodes
  int[] roots = makeSets(numberOfNodes);
  int[] size = new int[numberOfNodes];
  public int[] makeSets(int numberOfNodes) {
    // setting the root for every node its own node.
    int[] roots = new int[numberOfNodes];
    for (int i = 0; i < roots.length; i++) {
      roots[i] = i;
      // setting the size here too. (not clean code)
      size[i] = 1;
    }
    return roots;
  }

  public int findIterative(int node) {
    while (roots[node] != node) {
      node = roots[node];
    }
    return node;
  }

  public void unionBySize(int a, int b) {
    int a_root = findIterative(a);
    int b_root = findIterative(b);
    if (a_root == b_root) return;
    // attaching the smaller set to the larger set
    if (size[a_root] < size[b_root]) {
      roots[a_root] = b_root;
      size[b_root] += size[a_root];
    } else {
      roots[b_root] = a_root;
      size[a_root] += size[b_root];
    }
  }

Union by size with path compression find

Time complexity: Here, it's hard to get time complexity with the number of vertices. Therefore, we will compare time complexity with the number of FIND's and UNION's. With any intermixed sequence of m ≥ n FIND and n – 1 UNION operations, O(m logn) time. ** log ** is the base-2 iterated log and it grows much more slowly than the base-2 logarithm.

  public int findWithPathCompression(int node) {
    int root = node;
    while (roots[root] != root) {
      root = roots[root];
    }
    while (roots[node] != root) {
      int nextNode = roots[node]; 
      roots[node] = root;
      node = nextNode;
    }
    return root;
  }

  public void unionBySize(int a, int b) {
    int a_root = findWithPathCompression(a);
    int b_root = findWithPathCompression(b);
    if (a_root == b_root) return;
    // attaching the smaller set to the larger set
    if (size[a_root] < size[b_root]) {
      roots[a_root] = b_root;
      size[b_root] += size[a_root];
    } else {
      roots[b_root] = a_root;
      size[a_root] += size[b_root];
    }
  }

Graph construction/Clone graphs

https://leetcode.com/problems/clone-graph/

Preorder DFS

Let me start with wrong code.

public Node cloneGraph(Node node) {
    if (node == null) return node;
    Set<Integer> set = new HashSet();
    Node copyNode = new Node(node.val);
    cloneGraph(node, copyNode, set);
    return copyNode;   
}

private void cloneGraph(Node node, Node copy, Set<Integer> set) {
    set.add(node.val);
    // copying
    List<Node> copyNeighbors = new ArrayList<>();
    copy.neighbors = copyNeighbors;

    for (Node neighbor : node.neighbors) {// 2,4
        Node newNode = new Node(neighbor.val);
        copyNeighbors.add(newNode);
        if (!set.contains(neighbor.val)) {
            cloneGraph(neighbor, newNode, set);
        }
    }
} 

The reason that it's wrong is because every node is pointing to a new node and it's not a connecting graph anymore.

private void cloneGraph(Node node, Node copy, Map<Integer, Node> map) {
    map.put(node.val, copy);

    for (Node neighbor : node.neighbors) {// 2,4
        if (!map.containsKey(neighbor.val)) {
            Node newNode = new Node(neighbor.val);
            copy.neighbors.add(newNode);
            cloneGraph(neighbor, newNode, map);
        } else {
            copy.neighbors.add(map.get(neighbor.val));
        }
    }
}

The code above is correct. The infinite loop is prevented by going through the recursion only if it's an unseen node.

Postorder DFS

I wasn't sure if I could do it in a postorder way because I thought I had to return List<Node>. Thinking back to the trees, you don't have to return both left and right together from a function.

// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

The following code stops because if it's a seen node, the function returns the existing copy and not go through the recursive function.

private Node cloneGraph(Node node, Map<Integer, Node> map) {
    if (node == null) return null;
    Node curCopy = null;
    if (map.containsKey(node.val)) {
        curCopy = map.get(node.val);
        return curCopy;
    } else {
        Node copy = new Node(node.val);
        map.put(node.val, copy);
        curCopy = copy;
    }

    for (Node neighbor : node.neighbors) {
        curCopy.neighbors.add(cloneGraph(neighbor, map));
    }
    return curCopy;   
}

BFS Problems

Leetcode - 286. Walls and Gates
The distance to its nearest gate means the problem wants you to calculate the shortest distance. Therefore, BFS is the best use.
Bruteforce way is starting from every empty room, find a nearest gate with BFS and it will be n^2m^2 algorithm, because for each empty room cell, you're searching every other room.
Instead of the bruteforce way, you can start from the destination which is the gate and then do the BFS by setting the gate's distance to 0. Every adjacent cell will get the distance + 1 from the gates.

public void wallsAndGates(int[][] rooms) {
    int[][] dist = new int[rooms.length][rooms[0].length];
    Queue<int[]> queue = new LinkedList<>();
    
    for (int i = 0; i < rooms.length; i++) {
      for (int j = 0; j < rooms[0].length; j++) {
        int curDepth = rooms[i][j];
        if (curDepth == 0) {
          queue.add(new int[] {i, j, 0});
        }
      }
    }
    
    while (!queue.isEmpty()) {
      int[] polled = queue.poll();
      int polledRow = polled[0], polledCol = polled[1], polledDepth = polled[2];
      for (int[] dir : dirs) {
        int nextRow = polledRow + dir[0], nextCol = polledCol + dir[1], nextDepth = polledDepth + 1;
    
        if (0 <= nextRow && nextRow < rooms.length && 0 <= nextCol && nextCol < rooms[0].length && nextDepth < rooms[nextRow][nextCol]) {
          rooms[nextRow][nextCol] = nextDepth;
          queue.add(new int[] {nextRow, nextCol, nextDepth});
        }
      }
    }  
}

    private final int[][] dirs = { // ?
        {+1, 0},// down
        {-1, 0},// up
        {0, +1}, // right
        {0, -1}, // left
        {+1, +1}, // right bottom
        {-1, +1}, // right up
        {+1, -1}, // left bottom
        {-1, -1} // left up
    };
    public int shortestPathBinaryMatrix(int[][] grid) {
        int[] startPoint = new int[] {0, 0};
        int[] endPoint = new int[] {grid.length - 1, grid[0].length - 1};   
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int[][] distance = new int[grid.length][grid[0].length];
        Queue<int[]> bfsq = new LinkedList<>();

        if (grid[0][0] == 0) {// path
            bfsq.add(startPoint);
            visited[0][0] = true;
            distance[0][0] = 1;
            distance[grid.length - 1][grid[0].length - 1] = grid.length == 1 && grid[0].length == 1 ? 1 :  -1;
        } else {
            distance[0][0] = -1;
            distance[grid.length - 1][grid[0].length - 1] = -1;
        } // ?
        while(!bfsq.isEmpty()) {
            int[] curPoint = bfsq.poll(); // [0, 0]
            int curRow = curPoint[0], curCol = curPoint[1]; // 0, 0

            for (int[] dir : dirs) {
                int newRow = curRow + dir[0], newCol = curCol + dir[1];
                // within the bounds, visited, if it's 0
                if (newRow < 0 || newRow == grid.length || newCol < 0 || newCol == grid[0].length || visited[newRow][newCol] == true || grid[newRow][newCol] == 1) continue;

                bfsq.add(new int[] {newRow, newCol}); // [1, 1] ?
                visited[newRow][newCol] = true;
                distance[newRow][newCol] = distance[curRow][curCol] + 1;
            }
        }
        return distance[grid.length - 1][grid[0].length - 1]; // ?
    } 

Bipartiteness problems

Leetcode - 785. Is Graph Bipartite?

My mistake #1: Figuring out how to detect odd length cycle when coloring nodes. From the node that's coloring its neighbors, the color is always different from its own color. If there's no odd length cycle, its parent node will always have a different color than the current node. In other words, its parent node will have the same color as the current color to paint. Therefore, if a neighbor node already has a color and that's different from the current color to paint, then there's an odd length cycle.
My mistake #2: How to take care of nodes if there's no path from the root to other nodes. This can be resolved by having a for loop on the outside of the while loop.
My mistake #3: Related to mistake #2, I didn't know what to do with disjoint nodes' starting color. The root node of a new set of disjoint nodes can start with any color, because what matters is the distance from the root node to the rest of the connected nodes, not the actual colors.

public static boolean isBipartite(int[][] graph) {
    if (graph == null || graph.length == 0) return true;
    
    // map<node value, 0 or 1 color>
    Map<Integer, Integer> map = new HashMap<>(); //
    Queue<Integer> queue = new LinkedList<>(); //
    
    for (int root = 0; root < graph.length; root++) {
      int colorToPaint = 0;
      int curNode = root;
      if (map.containsKey(root)) continue;
      map.put(curNode, colorToPaint); // 
      queue.add(root);
      while (!queue.isEmpty()) {
        curNode = queue.poll(); // 4
        colorToPaint = map.getOrDefault(curNode, colorToPaint) + 1; // 2
    
        for (int neighbor : graph[curNode]) {// [0,2,3]
          if (map.containsKey(neighbor)) { //3
            int neighborColor = map.get(neighbor); //0
            if (neighborColor != colorToPaint % 2) {
              return false;
            }
          } else {
            map.put(neighbor, colorToPaint % 2); // 
            queue.add(neighbor); // 
          }
        }
      }
    }
    return true;
}

DFS problems

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

public int numIslands(char[][] grid) {
    int counter = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                counter++;
                dfs(i, j, grid);   
            }
        }
    }
    return counter;
}
private static int[][] dirs = {
    {1, 0}, // up
    {-1, 0}, // down
    {0, 1}, // right
    {0, -1}, // left
};

private void dfs(int row, int col, char[][] grid) {
    if (row < 0 || col < 0 || row == grid.length || col == grid[0].length || grid[row][col] == '0') return;

    grid[row][col] = '0'; // mark visited

    for (int[] dir : dirs) {
        dfs(row + dir[0], col + dir[1], grid);
    }
} 

Graphs

Graph representation

BFS and DFS Summary

BFS

DFS

Bipartiteness/2-colorability

Cycle detection in Directed Graphs using Topological Sorting

Minimum Spaning Tree

Prim's Algorithm

Kruskal's algorithm

Union and Find

Plain Union and Find

Union by size with plain find

Union by size with path compression find

Graph construction/Clone graphs

Preorder DFS

Postorder DFS

BFS Problems

Bipartiteness problems

DFS problems

Cycle detection problems

Union Find problems

Minimum spanning trees problems

Graphs

Graph representation​

BFS and DFS Summary​

BFS​

DFS​

Bipartiteness/2-colorability​

Cycle detection in Directed Graphs using Topological Sorting​

Minimum Spaning Tree​

Prim's Algorithm​

Kruskal's algorithm​

Union and Find​

Plain Union and Find​

Union by size with plain find​

Union by size with path compression find​

Graph construction/Clone graphs​

Preorder DFS​

Postorder DFS​

BFS Problems​

Bipartiteness problems​

DFS problems​

Cycle detection problems​

Union Find problems​

Minimum spanning trees problems​

Graph representation

BFS and DFS Summary

BFS

DFS

Bipartiteness/2-colorability

Cycle detection in Directed Graphs using Topological Sorting

Minimum Spaning Tree

Prim's Algorithm

Kruskal's algorithm

Union and Find

Plain Union and Find

Union by size with plain find

Union by size with path compression find

Graph construction/Clone graphs

Preorder DFS

Postorder DFS

BFS Problems

Bipartiteness problems

DFS problems

Cycle detection problems

Union Find problems

Minimum spanning trees problems