Coding Questions - Graph


Graph Representation: Here’s a good `tutorial`__.

  1. How long it takes to determine whether a given edge is in the graph
    • Adjacency lists
    • Edge lists
  2. How long it takes to find the neighbors of a given vertex
    • Adjacency matrices

The most used or nataural way is to use Adjacency lists:


Or we can use OOD concept to store vertex information.

Topological Sort: Topological Sorting for a graph is not possible if the graph is not a DAG.

An ordering of its vertices along a horizontal line so that all directed edges go from left to right.

  1. Doing with DFS:
  2. Doing with BFS:

LeetCode 207. Course Schedule

My thought is clear and i construct a graph using dictionary, then i can do a BFS on this graph until number of courses has met. However, i failed to detect the circle and handle that case. This is really a good chance for me to learn this kind of graph related questions.

Or saying from `website`__ this prerequisite relationship reminds one of directed graphs. Then, the problem reduces to find a topological sort order of the courses, which would be a DAG if it has a valid order.

This problem can be solved in 3 different ways: #. Detecting a cycle DFS.(Don’t use BFS) #. Using topological sort. (BFS/DFS) #. Union-Find?

If you treat it as a cycle detection problem, you can use a graph traversal method and detect a cycle along the traverse. Thus there’re 2 versions of cycle detection.


# Adjacency List solution to detect cycle
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        from collections import defaultdict
        graph = defaultdict(list)
        # initilize the graph
        # since the question is assuming we will have n courses in total which makes
        # initializing the graph much easier.
        def buildGraph(graph, numCourses, edgelists):
            for i in range(numCourses):
            for edge in edgelists:
            return graph

        graph = buildGraph(graph, numCourses, prerequisites)
        WHITE = 1
        BLACK = 2
        GREY = 3
        self.visited = [WHITE for _ in range(numCourses)] = 0

        def DFS_Visit(graph, vertex):
            self.visited[vertex] = GREY
            for adj_vertex in graph[vertex]:
                if self.visited[adj_vertex] == WHITE:
                    DFS_Visit(graph, adj_vertex)
                elif self.visited[adj_vertex] == GREY:
           += 1
            self.visited[vertex] = BLACK

        for vertex in range(numCourses):
            if self.visited[vertex] == WHITE:
                DFS_Visit(graph, vertex)

        return == 0

In fact, BFS cannot be simply used as an edge detection paradigm, here’re some reasons:

  1. Edge types are defined by DFS according to the text book

  2. If u is BLACK and v is next to u, then (u, v) can either be BLACK or GREY

  3. You can’t use distance as a flag because one might have different paths to same node


Topological Sort(BFS):

From `solution`__, BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we have found one. We set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of all its neighbors by 1. This process will be repeated for n (number of nodes) times. If we have not returned false, we will return true:

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        def buildGraph(graph, numCourses, edgelists):
            for i in range(numCourses):
            for edge in edgelists:
            return graph

        def computeDegrees(graph, numCourses):
            indegrees = [0]*numCourses
            for values in graph.values():
                for vertex in values:
            return indegrees
        from collections import defaultdict
        graph = defaultdict(list)
        graph = buildGraph(graph, numCourses, prerequisites)
        indegrees = computeDegrees(graph, numCourses)

        queue = []
        for i in range(numCourses):
            if indegrees[i]==0:
        # there's no vertex with 0 indegree which is a circle
        if not queue:
            return False
        # you can check the degrees by calling each method, however, queue is most easy to understand following BFS pattern.
        while queue:
            vertex = queue.pop(0)
            for adj_vertex in graph[vertex]:
                indegrees[adj_vertex] -= 1
                if indegrees[adj_vertex] == 0:

        return sum(indegrees) == 0

Topological Sort(DFS):

It’s safer to add one more step to calculate the indegrees, then we don’t need to worry about the order of input:

from collections import defaultdict
graph = defaultdict(list)
graph = buildGraph(graph, 5, [[0,5],[0,4],[2,5],[1,4],[3,2],[1,3]]) #[[1,0], [2,0], [3,1], [4,1], [2, 5]]
indegrees = indegrees(graph)
visited = [False] * len(graph.keys())

def dfs(graph, adj_vertex, visited, res):
    visited[adj_vertex] = True
    for vertex in graph[adj_vertex]:
        if not visited[vertex]:
            dfs(graph, vertex, visited, res)
res = []
for vertex in graph.keys():
    if not visited[vertex]:
        dfs(graph, vertex, visited, res)
print res[::-1]

LeetCode 547. Friend Circles

From some source, we can visit every connected node to it with a simple DFS. As is the case with DFS’s, seen will keep track of nodes that have been visited.

For every node, we can visit every node connected to it with this DFS, and increment our answer as that represents one friend circle (connected component.)


class Solution(object):
    def findCircleNum(self, M):
        :type M: List[List[int]]
        :rtype: int
        visited = [False]*len(M)
        count = 0

        def dfs(M, visited, i):
            for j in range(len(M)):
                if M[i][j] == 1 and not visited[j]:
                    visited[j] = True
                    dfs(M, visited, j)

        for i in range(len(M)):
            if not visited[i]:
                dfs(M, visited, i)
        return count

LeetCode 675. Cut Off Trees for Golf Event

The question is turned into finding distance between 2 trees. My original approach was to find the paths from (0, 0) to all trees which will be more complex because you don’t know how to handle the intermediate step.

In order to implement the distance method, there’re 3 algorithms:
  1. BFS
  2. A* (Dijkstra’s special case)
  3. Hadlock
  4. Another trick is 2-direction BFS

Explaination is in sorce code:

class Solution(object):
def cutOffTree(self, forest):
    :type forest: List[List[int]]
    :rtype: int
    # since the tree heights are ordered, we already have an order to cut these trees(have to cut the global min each time)
    # then we can sort the tree node at the begining.
    trees = []
    for i in range(len(forest)):
        for j in range(len(forest[0])):
            if forest[i][j] > 1:
                trees.append((forest[i][j], i, j))
    trees = sorted(trees, key=lambda x: x[0])

    def dist(forest, sr, sc, tr, tc):
        # this array is to help go discover the grid
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        # we can't maintain a global visited helper map because previous search will
        # change the trace
        queue = [(sr, sc, 0)]
        visited =[[False for _ in range(len(forest[0]))] for __ in range(len(forest))]
        visited[sr][sc] = True
        while queue:
            r, c, d = queue.pop(0)
            if r == tr and c == tc:
                return d

            for dx, dy in directions:
                x = r + dx
                y = c + dy
                if 0 <= x < len(forest) and 0 <= y < len(forest[0]) and forest[x][y] and not visited[x][y]:
                    queue.append((x, y, d+1))
                    visited[x][y] = True
        return -1
    sr = sc = ans = 0
    for _, tr, tc in trees:
        d = dist(forest, sr, sc, tr, tc)
        if d < 0:
            return -1
        ans += d
        sr, sc = tr, tc
    return ans

LeetCode 269. Alien Dictionary

When you are asked to get some kind of orders, think about Topological sort, but you first need to convert the question to a graph problem.