Graph

2023-04-19
#python
Data Structure & Algorithm

Some Graph Algorithms and Theories

  • Graph cheatsheet for coding interviews

  • How to determine a undirected graph is a valid tree

    • It must be connected and have exactly (n-1) edges.
      • Any less than (n-1) edges, it can’t possibly be fully connected.
      • Any more than (n-1) edges, it has to contain cycles.

  • If a graph has far less edges, such that |E|<<|V|2, the graph is said to be “sparse”.

  • Corner cases for your graph algorithm to handle

    • Empty graph
    • Graph with one or two nodes
    • Disconnected graphs
    • Graph with cycles

LeetCode examples

  • BFS and DFS

    • LeetCode 133. Clone Graph
    • DFS 
      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
      # Definition for a Node.
       class Node:
           def __init__(self, val = 0, neighbors = None):
               self.val = val
               self.neighbors = neighbors if neighbors is not None else []
       class Solution:
       # Need to use a Hashmap to track the visited node.
           def cloneGraph(self, node: 'Node') -> 'Node':
               # memo is the HashMap that tracks the existing nodes
               def dfs(node, memo):
                   newNode = Node(node.val)
                   memo[node.val] = newNode
                   for neigh in node.neighbors:
                       if neigh.val in memo:
                           newNeigh = memo[neigh.val]
                       else:
                           newNeigh = dfs(neigh, memo)
                       newNode.neighbors.append(newNeigh)
                   return newNode
               if node is None:
                   return None
               memo = {}
               dfs(node, memo)
               #print(memo)
           return memo[1]
    • BFS 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      # Definition for a Node.
       class Node:
           def __init__(self, val = 0, neighbors = None):
               self.val = val
               self.neighbors = neighbors if neighbors is not None else []
       class Solution:
           def cloneGraph(self, node: 'Node') -> 'Node':
               if node is None:
                   return None
               # memo is the HashMap that tracks the existing nodes
               queue, memo = deque([node]), {node.val: Node(node.val)}
               while(queue):
                   oldNode = queue.popleft()
                   newNode = memo[oldNode.val]
                   for neigh in oldNode.neighbors:
                       if(neigh.val not in memo):
                           # Create new node before adding oldNode into the queue, there're also several other use cases of this pattern. 
                           newNeigh = Node(neigh.val)
                           memo[neigh.val] = newNeigh
                           queue.append(neigh)
                       newNode.neighbors.append(memo[neigh.val])
               #print(memo)
               return memo[1]

  • Topological Sort

    • LeetCode 269. Alien Dictionary
      • You are given a list of strings words from the alien language’s dictionary, where the strings in words are sorted lexicographically by the rules of this new language. 
        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 alienOrder(self, words: List[str]) -> str:
            """
            Input: words = ["wrt","wrf","er","ett","rftt"]
            Output: "wertf"
            It forms a directed graph
            """
            # degree indicates the number of letter that are ahead for each one
            adj, degree = collections.defaultdict(set), {}
            degree = {ch:0 for w in words for ch in w}
            for i in range(1, len(words)):
                minLen = min(len(words[i-1]), len(words[i]))
                flag = len(words[i-1]) > len(words[i])
                for j in range(minLen):
                    preCh = words[i-1][j]
                    curCh = words[i][j]
                    if(preCh != curCh):
                        if(curCh not in adj[preCh]):
                            adj[preCh].add(curCh)
                            degree[curCh] += 1
                        break
                    # for a corner case
                    elif(j == (minLen - 1) and flag):
                        return ""
            #print(degree)
            # put all letters who have 0 degree into the queue, and then run topological sort
            queue = collections.deque([x for (x,v) in degree.items() if v == 0])
            res = []
            while(queue):
                ch = queue.popleft()
                res.append(ch)
                neighbors = adj[ch]
                for nodeCh in neighbors:
                    degree[nodeCh] -= 1
                    if(degree[nodeCh] == 0):
                        queue.append(nodeCh)
            print(res)
            return "".join(res) if len(res)==len(degree) else ""

  • Union Find

    • Disjoint Set Union (Union Find)
    • LeetCode 323. Number of Connected Components in an Undirected Graph
      • You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph. 
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        def countComponents(self, n: int, edges: List[List[int]]) -> int:
            parents = [i for i in range(n)]
            def findParents(parents, node):
                while(node != parents[node]):
                    node = parents[node]
                return node
            nComponents = n
            for edge in edges:
                pA = findParents(parents, edge[0])
                pB = findParents(parents, edge[1])
                if(pA != pB):
                    # Note that it's the roots of 2 nodes are connected, not the nodes themselves.
                    parents[pB] = pA
                    nComponents -= 1
            #print(parents)
            return nComponents

  • Dijkstra Algorithm

    • LeetCode 787. Cheapest Flights Within K Stops
      • There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1. 
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
             """
             Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
             Output: 700
             """
             minCost, adj = {i:float('inf') for i in range(n)}, collections.defaultdict(list)
             for flight in flights:
                 adj[flight[0]].append((flight[1], flight[2]))
             queue, stop = collections.deque([(src,0)]), 0
             while(queue and stop<=k):
                 size = len(queue)
                 for _ in range(size):
                     (city,curCost) = queue.popleft()
                     neighbors = adj[city]
                     for (neigh, price) in neighbors:
                         if(curCost+price<=minCost[neigh]):
                             minCost[neigh] = curCost+price
                             queue.append((neigh, minCost[neigh]))
                 stop += 1
                 print(minCost)
             return minCost[dst] if minCost[dst] != float('inf') else -1

  • Hierholzer’s algorithm to find the Eulerian cycle

    • Medium reference Finding the Eulerian Cycle with Hierholzer’s Algorithm. The algorithm is explained briefly as,
      1. It starts with a random node and then follows an arbitrary unvisited edge to a neighbor. This step is repeated until one returns to the starting node. This yields a first circle in the graph.
      2. If this circle covers all nodes it is an Eulerian cycle and the algorithm is finished. Otherwise, one chooses another node among the cycles’ nodes with unvisited edges and constructs another circle, called subtour.
        Eulerian Cycle
    • LeetCode 332. Reconstruct Itinerary
      • You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
        For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.         
        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 findItinerary(self, tickets: List[List[str]]) -> List[str]:
            """
            Check the LeetCode webpage for input example 
            """
            adj = collections.defaultdict(list)
            for ticket in tickets:
                adj[ticket[0]].append(ticket[1])
            for (key,value) in adj.items():
                value.sort(reverse=True)
                #print(key, value)

            def dfs(adj, origin, res):
                destList = adj[origin]
                while destList:
                    # while we visit the edge, we trim it off from graph.
                    nextDest = destList.pop()
                    dfs(adj,nextDest, res)
                # post-order DFS
                res.append(origin)
                
            res = []
            dfs(adj, 'JFK', res)

            # reconstruct the route backwards
            return res[::-1]