Graphs

My second nemesis 🥵!

Topological Sort (Detecting cycle in directed graph)

TIP

If you have not tried these questions, please give it a go first! 👾

• https://leetcode.com/problems/course-schedule/
• https://leetcode.com/problems/course-schedule-ii/
• Minimum Height Trees
• Accounts Merge
• Reconstruct Itinerary

Source

One of the best explanation by hxuanhung

Method 1: DFS with stack

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        visited = set()
        graph = self.buildAdj(numCourses, prerequisites)

        def hasCycle(v, stack):
            if v in visited: # why check this?
                if v in stack:
                    # Cycle exists
                    return True
                # Visited but not in stack -> already checked before
                return False

            # Not visited
            visited.add(v)
            stack.append(v)

            for d in graph[v]: # Check all descendants
                if hasCycle(d, stack):
                    return True

            # Remove v from stack
            stack.pop()
            return False

        for i in range(numCourses):
            if hasCycle(i, []):
                return False

        return True

    # Build adjacency matrix: prereq: [modules]
    def buildAdj(self, n, p):
        graph = [[] for i in range(n)]
        for a, b in p: # b -> a : take course b first
            graph[b].append(a)
        return graph

Method 2: BFS (Kanh's Algorithm)

• Repeatedly remove nodes without any incoming edges and add them to the topological ordering.
• As nodes without incoming edges (and their outgoing edges) are removed, new nodes without incoming edges should become free.
• Repeat until all nodes covered or cycle detected.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        return self.BFS(numCourses, prerequisites)


    def BFS(self, n, p):
        graph = self.buildAdj(n,p)
        queue = []
        topoOrder = []

        # Store number of income edges for each vertex
        inOrder = [0] * n
        for a, b in p:
            inOrder[a] += 1

        # Add vertex with no incoming edges to queue
        for v in range(n):
            if inOrder[v] == 0:
                queue.append(v)

        count = 0
        topoOrder = []
        while queue:
            v = queue.pop(0)
            topoOrder.append(v)
            count += 1

            for d in graph[v]:
                inOrder[d] -= 1
                if inOrder[d] == 0:
                    queue.append(d)

        if count == n:
            return True
        else:
            return False

    # Build adjacency matrix: prereq: [modules]
    def buildAdj(self, n, p):
        graph = [[] for i in range(n)]
        for a, b in p: # b -> a : take course b first
            graph[b].append(a)
        return graph

Minimum Height Trees

tip

Amazing answer on LeetCode submissions.

Solution 1: BFS

• Maintain a list of leaf nodes where there is only one edge each
• Remove layer of leaf nodes until 2 or less nodes remaining

def findMinHeightTrees(self, n, edges):
    if n == 1:
        return [0]
    # Build adjacency list
    graph = [[] for i in range(n)]
    for a, b in edges: # Undirected edges
        graph[a].append(b)
        graph[b].append(a)
    # Add leaves
    leaves = []
    for i in range(n):
        if len(graph[i]) == 1:
            leaves.append(i)
    while n > 2:
        newLeaves = []
        n -= len(leaves)
        for leaf in leaves:
            node = graph[leaf].pop()
            graph[node].remove(leaf)
            if len(graph[node]) == 1:
                newLeaves.append(node)
        leaves = newLeaves
    return leaves

Time Complexity: O(n) for running BFS and building adjacency list.

Space Complexity: O(n) for adjacency list and leaves list.

Accounts Merge

tip

Amazing answer by none other than Yang Shun.

Solution 1: DFS

• Create a graph emails_map: email -> [account index]
• Perform DFS on each account and accounts that are linked to it using the emails_map, adding emails along the way and performing DFS on its neighbours.

def lowestCommonAncestor(self, accounts):
    from collections import defaultdict
    res = []
    emails_map = defaultdict(list)
    visited = [False] * len(accounts)

    # Build emails_map
    for i, account in enumerate(accounts):
        for email in account[1:]:
            emails_map[email].append(i)
    
    # DFS function
    def dfs(i, emails):
        if visited[i]:
            return
        visited[i] = True
        for email in accounts[i][1:]:
            emails.add(email)
            for neighbor in emails_map[email]:
                dfs(neighbor, emails)

    # Run DFS
    for i, account in enumerate(accounts):
        if visited[i]:
            continue
        name, emails = account[0], set()
        dfs(i, emails)
        res.append([name] + sorted(emails))
    return res
  

Time Complexity: O(nlogn) for sorting the emails.

Space Complexity: O(n) for the dictionary used.

Reconstruct Itinerary

tip

Amazing answer on LeetCode.

Solution 1: DFS

• Create a graph src -> [dst]
• Sort [dst] in reverse order to pop last element in O(1) time
• Perform DFS and add to res when location has no more destinations to go
• Return reverse res

def findItinerary(self, tickets):
    graph = collections.defaultdict(list)
    for src, dst in tickets: # src -> [dst]
        graph[src].append(dst)
    
    for src in graph:
        graph[src].sort(reverse=True)

    res = []
    stack = "JFK"
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        res.append(stack.pop())
    return res[::-1]

Time Complexity: O(n)

Space Complexity: O(n) for the dictionary used.