[Leetcode] Graph

Posted on | In , |

Intro to Graph

Video: https://www.youtube.com/watch?v=zaBhtODEL0w&t=261s

Definetion A directed graph is a set V of vertices and a set E of edges. Given an edge e = (u,v), the vertex u is its source, and v is its sink

A path in a directed graph from u to vertex v is a sequence of vertices , where each (vi, vi+1) is an edge. The length of the path is n - 1

A directed acyclic graph (DAG) is a directed graph in which there are no cycles (paths which contains one or more edges and which begin and end at the same vertex).

[Related Problems]

  • Matrix problems
  • Geometric problems
  • Consider using a graph when you need to analyze any binary relationship
  • BFS can be used to compute distances from the start vertex and DFS can be used to check for the presence of cycles

Connected Graph

  • If G is an undirected graph, vertices u and v are said to be connected if G contains a path from u to v.
  • A graph is said to be connected if every pair of vertices in the graph is connected
  • A connected component is a maximal set of vertices C such that each pair of vertices in C is connected in G
  • A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces an undirected graph that is connected.

Representation

Adjacency lists and Adjacency matrix

Spanning tree

Given a graph G = (V,E), if the graph G’ = (V, E’) where E’ belongs to E is a tree, then G’ is referred to as a spanning tree of G.

DFS

Goes Deep to children before going broad to neighbors. Mark visited node to avoid cycles.

[Key Concept] Use Stack, Use a Mark to mark if a node is visited.

  • Visit node A, mark A as visited add A to the top of stack
  • Find A’s unvisited B, visit B, repeat first step
  • If all of the chilren are visited, pop node off the stack

[Related Problems]

  • Anaylizing structure. i.e. Looking for cycles or connected components
  • Some graph problems are

133. Clone Graph

Leetcode: https://leetcode.com/problems/clone-graph/description/
Solution

  1. Use a Map to track visited nodes. If visited, return the node.
  2. Clone node, and put node into visited map.
  3. Clone all the neighbors of the node and link them to the cloned node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    Map<Integer, UndirectedGraphNode> visited = new HashMap<Integer, UndirectedGraphNode>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        // Use a Map to track visited node
        // DFS
        return clone(node);
    }

    private UndirectedGraphNode clone(UndirectedGraphNode node) {
        if (node == null) return node;
        if (visited.get(node.label) != null) {
            // Node has been visited
            return visited.get(node.label);
        }
        UndirectedGraphNode n = new UndirectedGraphNode(node.label);
        visited.put(node.label, n);
        for (UndirectedGraphNode neighbor: node.neighbors) {
            n.neighbors.add(clone(neighbor)); // link all neighbors to the cloned node
        }
        return n;
    }
}

138. Copy List with Random Pointer

Leetcode: https://leetcode.com/problems/copy-list-with-random-pointer/description/

Solution same as the above problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    Map<Integer, RandomListNode> visited = new HashMap<>();
    public RandomListNode copyRandomList(RandomListNode head) {
        return clone(head);
    }

    private RandomListNode clone(RandomListNode head) {
        if (head == null) return head;
        if (visited.get(head.label) != null) return visited.get(head.label);

        RandomListNode n = new RandomListNode(head.label);// new node
        visited.put(head.label, n);
        // copy all the neighbors (next, random)
        n.next = clone(head.next);
        n.random = clone(head.random);
        return n;
    }
}

Team Match problem

Goal: Given team A and B, is there a sequence of teams starting with A and ending with B such that each team in the sequence has beaten the next team in the sequence?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
MatchResult = collections.namedtupple('MatchResult', ('winning_team', 'losing_team'))

def can_team_a_beat_team_b(matches, team_a, team_b):
    def build_graph():
        graph = collections.defaultdict(set)
        for match in matches:
            graph[match.winning_team].add(match.losing_team)
        return graph

    def is_reachable_dfs(graph, cur, dest, visited=set()):
        if cur == dest:
            return True
        if cur in visited or cur not in graph:
            return False
        visited.add(cur)
        return any(is_reachable_dfs(graph, team, dest) for team in graph[cur]) # For each cur's child, repeat dfs

    return is_reachable_dfs(build_graph(), team_a, team_b)

Tarjan’s Algorithm

Intro video

Tarjan’s Algorithm is used in finding strongly connected components.

Strongly Connected Components (SCC) can be thought of as self-contained cycles within a directed graph where every vertex in a given cycle can reach every other vertex in the same cycle.

Low-link value of a node is the smallest[lowest] node id reachable from that node when doing a DFS (including itself)

Flaw: the low-link value might be dependant on the start point of dfs traversal.

To fix the flaw: use a stack(set) of valid nodes:

  • Nodes are added to the stack of valid nodes as they’re explored for the first time
  • Nodes are removed from the stack each time a complete SCC is found

New low-link update condition:

  • If u and v are nodes in a graph and we’re currently on u:
  • To update u‘s low-link value to node v‘s low-link value there has to be a valid path from u to v and
  • v must be on the stack

Time complexity: linear O(V+E)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
UNVISITED = -1
n = number of nodes in graph
g = adjacency list with directed edges

id = 0 # Used to give each node an id
sccCount = 0 # Used to count number of SCCs found

# Index i in these arrays represents node i
ids = [0, 0, ... 0, 0] # len = n
low = [0, 0, ... 0, 0] # len = n
onStack = [false, false, ..., false] # len = n
stack = [] # an empty stack

def findSCCs():
    for i in range(n): # Initialization
        ids[i] = UNVISITED
    for i in range(n):
        if ids[i] == UNVISITED:
            dfs(i)
    return low

def dfs(v):
    stack.append(v)
    onStack[v] = true
    ids[v], low[v] = id, id
    id += 1

    # Visit all neightbors & min low-link on callback
    for neib in g[v]:
        if(ids[neib] == UNVISITED):
            dfs(neib)
        if (onStack[neib]):
            low[v] = min(low[v], low[neib])
        
        # After having visited all neighbors of `v`
        # if we're at the start of a SCC empty the stack untill we're back to the start of SCC
        if ids[v] == low[v]:
            for node = stack.pop():
                onStack[node] = false
                low[node] = ids[v] # backtrack
                if node == v:
                    break
            sccCount += 1

BFS

[Key Concept] Use Queue, Use a Mark to mark if a node is visited.

Goes Broad to neighbors before goes deep. Use a Queue to add all the children of the nodes into the queue maintain the right order.

  • Visit node A, mark A as visited, add A to queue
  • Visit A’s unvisited child B, repeat step A
  • If all the chilren are visited, pop node from queue, and make that node the current node, repeat step 1

Shortest path problems:

  1. Binary Tree Level Order Traversal
  2. Word Ladder
  3. Word Ladder II
  4. Remove Invalid Parentheses
  5. Shortest Distance from All Buildings
  6. Minesweeper
  7. Sliding Puzzle
  8. Bus Routes
  9. K-Similar Strings
  10. Shortest Path to Get All Keys
  11. Shortest Path in Binary Matrix
  12. Minimum Moves to Reach Target with Rotations
  13. Minimum Moves to Move a Box to Their Target Location
  14. Shortest Path in a Grid with Obstacles Elimination

Topological Sort

Topological Sort is used to solve problems like prerequisite, dependency problems.

Video: https://www.youtube.com/watch?v=Q9PIxaNGnig

Some events must occur before others.

Topological sort is ordering of the nodes in a directed graph where for each directed edge from node A to node B, node A appears before node B in the ordering.

The topological algorithm can find a topological ordering in O(V+E) time. The sort ordering are NOT unique.

Set: keep track of visited nodes. If visited, put node in set, explore its children. If all children are in the visited set, put node into stack.
Stack: sorted. Only when vertices are fully explored(all children visited), put such vertices into stack.

Can also be used to detect cycle in graph.

Only Directed Acyclic Graphs have topological sort. By definition, all trees have topological orders.

[Related Problems]

  • School class prerequesites
  • Program dependencies
  • Event scheduling
  • Assembly instructions

Kahn’s Algorithm
https://www.youtube.com/watch?v=cIBFEhD77b4

Repeatedly remove nodes without any dependencies from the graph and add them to the topological ordering. As nodes without dependencies (and their outgoing edges) are removed from the graph, new nodes without dependencies should become free. We repeat removing nodes without dependencies from the graph until all nodes are processed, or a cycle is discovered.

  • Begin by counting the incoming degree of each node, store them in an array
  • Use a queue to track which node to be processed next
  • Return invalid if indegree list has non-zero in the end

207. Course Schedule

Video: Topological solution: https://www.youtube.com/watch?v=M6SBePBMznU
Video: BFS solution: https://www.youtube.com/watch?v=zkTOIVUdW-I

Has two status: visited and visiting, if cur == visiting, means we start from cur and go back to cur again, means has cycle in the graph

[Solution]

  1. Construct a HashMap key: each class, value: the direct children of the class
  2. Construct a indegree list to keep track of all the node’s indegree
  3. Run BFS: Construct a queue, put all node in the indegree list whose value is 0
  4. while queue.size() != 0 pop nodes i from queue, reduce the indegree of the child of i in indegree list by 1, check the map of their children. If the children’s indegree == 0, put the child into the queue
  5. Loop through the indegree list, if any node has value != 0, return false

Recursive Solution: 148s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    # Prepare graph
    g = {}
    for edge in prerequisites:
        if edge[0] not in g:
            g[edge[0]] = []
        if edge[1] not in g:
            g[edge[1]] = [edge[0]]
        else:
            g[edge[1]].append(edge[0])
    visited = []
    visiting = []
    
    # print(g)
    def dfs(node):
        if node in visited:
            return True
        if node in visiting:
            return False
        visiting.append(node)
        for neighbor in g[node]:
            if not dfs(neighbor):
                return False
        
        visited.append(node)
        visiting.pop()
        return True
    
    for node in g:
        if not dfs(node): # If any node have cycle
            return False
    return True

If the question has something like 0 -> n, we can consider using it as index in the array.

Iterative Solution

1
2
3
4
5
6
7
8
Construct two lists with out and in information of the graph
Start from node whose out degree == 0, bottom up, visit the node and remove it from the graph
[[1,0],[2,0],[1,2],[1,3],[3,0]] [1 <- 0]
out | | prereq
 3  |0| 
 0  |1| 0,2,3
 1  |2| 0
 1  |3| 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    # Buttom-up solution
    # i <- j
    n = numCourses
    out = [0 for i in range(n)]
    preqs = [[] for i in range(n)]
    for i, j in prerequisites:
        out[j] += 1
        preqs[i].append(j)
    visited = []
    q = collections.deque([x for x in range(n) if out[x] == 0])
    while q:
        cur = q.popleft() # Remove cur from graph
        for n in preqs[cur]:
            out[n] -= 1
            if out[n] == 0:
                q.append(n)
        visited.append(cur)
    return len(visited) == numCourses

210. Course Schedule II

Leetcode: https://leetcode.com/problems/course-schedule-ii/

Note:

  1. Use a stack to store the sequence
  2. Use two sets, one for visited, one for visiting nodes to detect if there’s loop in the graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class Graph {
    private HashMap<Integer, Node> nodeLookup = new HashMap<Integer, Node>();

    public static class Node {
        private int id;
        LinkedList<Node> adjacent = new LinkedList<Node>();
        private Node(int id) {
            this.id = id;
        }
    }

    private Node getNode(int id) {
        return nodeLookup.get(id);
    }
    public void addEdge(int source, int destination) {
        Node s = getNode(source);
        Node d = getNode(destination);
        if (s == null) {
            s = new Node(source);
        }
        if (d == null) {
            d = new Node(destination);
        }
        s.adjacent.add(d);
        d.adjacent.add(s);
        this.nodeLookup.put(source, s);
        this.nodeLookup.put(destination, d);
    }

    public boolean hasPathDFS(int source, int destination) {
        Node s = getNode(source);
        Node d = getNode(destination);
        HashSet<Integer> visited = new HashSet<Integer>();
        return hasPathDFS(s, d, visited);
    }

    private boolean hasPathDFS(Node source, Node destination, HashSet<Integer> visited) { // Finding a path from source to destination
        if (visited.contains(source.id)) return false;
        visited.add(source.id);
        if (source == destination) return true;
        for (Node child: source.adjacent) {
            if (hasPathDFS(child, destination, visited)) return true;
        }
        return false;
    }

    public boolean hasPathBFS(int source, int destination) {
        return hasPathDFS(new Node(source) , new Node(destination));
    }

    private boolean hasPathBFS(Node source, Node destination) {
        LinkedList<Node> nextToVisit = new LinkedList<Node>();
        HashSet<Integer> visited = new HashSet<Integer>();
        nextToVisit.add(source);
        while (!nextToVisit.isEmpty()) {
            Node node = nextToVisit.remove();
            if (node == destination) return true;
            if (visited.contains(node.id)) continue;
            visited.add(node.id);

            for (Node child: node.adjacent) {
                nextToVisit.add(child);
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = collections.defaultdict(list)
    queue = []
    lst = [0 for i in range(numCourses)]
    for relation in prerequisites:
        lst[relation[0]] += 1
        graph[relation[1]].append(relation[0])
    
    for index, indegree in enumerate(lst):
        if indegree == 0:
            queue.append(index)
    visited = set()
    res = []
    while queue:
        node = queue.pop(0)
        res.append(node)
        for neib in graph[node]:
            lst[neib] -= 1
            if lst[neib] == 0:
                queue.append(neib)
    if sum(lst) != 0:
        return []
    return res

269. Alien Dictionary

Leetcode: https://leetcode.com/problems/alien-dictionary/

  • Construct the map first
  • Topo sort later
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def alienOrder(self, words: List[str]) -> str:
    ordering = ""
    # construct graph
    unique = set()
    inDeg = collections.defaultdict(int)
    graph = collections.defaultdict(list)
    
    for word in words:
        for ch in word:
            unique.add(ch)
            inDeg[ch] = 0
            
    for i in range(len(words) - 1):
        hasDiff = False
        for j in range(len(words[i])):
            if j < len(words[i + 1]) and words[i][j] != words[i + 1][j]:
                hasDiff = True
                graph[words[i][j]].append(words[i + 1][j])
                inDeg[words[i + 1][j]] += 1
                break
        if len(words[i]) > len(words[i + 1]) and not hasDiff:
            # invalid
            return ""
                
    if sum(inDeg.values()) == 0 and len(unique) == 1:
        for ch in unique:
            return ch
    queue = collections.deque([])
    for key in inDeg.keys():
        if inDeg[key] == 0:
            queue.append(key)
    while queue:
        cur = queue.popleft()
        ordering += cur
        for neib in graph[cur]:
            inDeg[neib] -= 1
            if inDeg[neib] == 0:
                queue.append(neib)
    
    if len(ordering) != len(unique):
        return ""
    
    return ordering

310. Minimum Height Trees

Leetcode: https://leetcode.com/problems/minimum-height-trees/

  • There would be at most 2 trees that satisfy the condition
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # furtherst distance to other node is minimum
        # memo + dfs
        # build graph
        if n <= 2:
            return [i for i in range(n)]
        
        graph = collections.defaultdict(set)
        neibCount = [0 for _ in range(n)]
        nodes = set([i for i in range(n)])
        
        for u, v in edges:
            neibCount[u] += 1
            neibCount[v] += 1
            graph[u].add(v)
            graph[v].add(u)

        remainingNodes = n
        removed = set()
        leaves = []
        for i in range(n):
            if neibCount[i] == 1:
                leaves.append(i)
        
        remain = n
        while remain > 2:
            newLeaves = []
            remain -= len(leaves)
            while leaves:
                leaf = leaves.pop()
                for neib in graph[leaf]:
                    graph[neib].remove(leaf)
                    neibCount[neib] -= 1
                    if neibCount[neib] == 1:
                        newLeaves.append(neib)
            leaves = newLeaves
        return leaves

490. The Maze

Leetcode: https://leetcode.com/problems/the-maze/

[Solution]

  • Model the maze into a graph, white cells as nodes, and adjacent white cells as edges

1091. Shortest Path in Binary Matrix

Leetcode: https://leetcode.com/problems/shortest-path-in-binary-matrix/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    if not grid or not grid[0]:
        return 0
    if grid[0][0] == 1:
        return -1
    
    dirs = [(-1, 0), (-1, 1), (-1, -1), (0, 1), (0, -1), (1, -1), (1, 0), (1, 1)]
    visited = set()
    
    queue = deque([(0, 0, 1)])
    visited.add((0, 0))
    while queue:
        curI, curJ, curDist = queue.popleft()
        if curI == len(grid) - 1 and curJ == len(grid[0]) - 1:
            return curDist
        
        
        for deltaI, deltaJ in dirs:
            newI, newJ = curI + deltaI, curJ + deltaJ
            if (newI, newJ) in visited or newI < 0 or newJ < 0 or newI >= len(grid) or newJ >= len(grid[0]) or grid[newI][newJ] == 1:
                continue
            visited.add((newI, newJ))
            queue.append((newI, newJ, curDist + 1))

    return -1

DFS

1042. Flower Planting With No Adjacent

(four color problem)

Leetcode: https://leetcode.com/contest/weekly-contest-136/problems/flower-planting-with-no-adjacent/

Video: https://www.youtube.com/watch?v=052VkKhIaQ4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
    # Construct graph
    graph = {}
    
    for i in range(1, N + 1):
        graph[i] = set()
            
    for path in paths:
        graph[path[0]].add(path[1])
        graph[path[1]].add(path[0])
    # graph: {1: {2,3}, 2: {1,3}...} key: node, value: [neighbors]

    res = [0] * (N + 1)

    def paint(cur):
        # check all used colors by current node's neighbors
        used = set([res[neib] for neib in graph[cur]])
        for i in range(1, 5):
            if i not in used: # find an unused color
                # paint current
                res[cur] = i
                break
    for i in range(1, N + 1):
        paint(i)
    
    return res[1:]

323. Number of Connected Components in an Undirected Graph

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def countComponents(self, n: int, edges: List[List[int]]) -> int:
    cnt = 0
    graph = {}
    visited = set()
    for i in range(n):
        graph[i] = set()
        
    for edge in edges:
        graph[edge[0]].add(edge[1])
        graph[edge[1]].add(edge[0])
    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neib in graph[node]:
            dfs(neib)
        
        
    for i in range(n):
        if i not in visited:
            dfs(i)
            cnt += 1
        
    return cnt

200. Number of Islands

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def numIslands(self, grid: List[List[str]]) -> int:
    cnt = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                self.dfs(grid, i, j)
                cnt += 1
    return cnt
    
def dfs(self, grid, i, j):
    if  i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':
        return False
    # Flip i, j
    grid[i][j] = '0'
    self.dfs(grid, i-1, j)
    self.dfs(grid, i+1, j)
    self.dfs(grid, i, j-1)
    self.dfs(grid, i, j+1)
    return True

547. Friend Circles

Leetcode: https://leetcode.com/problems/friend-circles/

Find the lower land problem

277. Find the Celebrity

Leetcode: https://leetcode.com/problems/find-the-celebrity/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findCelebrity(self, n):
    """
    :type n: int
    :rtype: int
    """
    x = 0
    for i in range(n): # Find the suspicious celebrity
        if knows(x, i):
            x = i
    for i in range(n): # If someone doesnt know him
        if not knows(i, x):
            return -1
    for i in range(n):
        if i != x and knows(x, i): # If he doesnt know anyone
            return -1
    return x

997. Find the Town Judge

Leetcode: https://leetcode.com/problems/find-the-town-judge/

Same as above.

1
2
3
4
5
6
7
8
9
10
11
12
13
def findJudge(self, N, trust):
    graph = [[0 for j in range(N)] for i in range(N)]
    for t in trust:
        graph[t[0] - 1][t[1] - 1] = 1
    x = 0
    for i in range(N):
        if graph[x][i]:
            x = i
    if any(i != x and not graph[i][x] for i in range(N)):
        return -1
    if any(i != x and graph[x][i] for i in range(N)):
        return -1
    return x + 1

Solution 2:
The point with in-degree - out-degree = N - 1 become the judge.

1
2
3
4
5
6
7
8
9
10
11
def findJudge(self, N, trust):
    d = collections.defaultdict(list) # {1, [0, 2]}
    for i in range(1, N + 1):
        d[i] = [0, 0]
    for t in trust:
        d[t[0]][0] += 1
        d[t[1]][1] += 1
    for k in d:
        if d[k][1] - d[k][0] == N - 1:
            return k
    return -1

1197. Minimum Knight Moves

Leetcode: https://leetcode.com/problems/minimum-knight-moves/