Detect the Cycle

Find if a cycle exits in a directed graph

Undirected Graph

261. Graph Valid Tree

• Undirected Graph: Union Find, DFS, BFS

• 解法1. Union Find

  • 图是以edge的形式表示的，方便union find

class Solution(object):
    def validTree(self, n, edges):
        root = range(n)
        self.cnt = n
        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                root[rootx] = rooty
                self.cnt -= 1
                return True
            return False

        for i, j in edges:
            if not union(i, j):
                return False
        return self.cnt == 1

• 解法2. DFS
  • undirected graph 边都是对称的，防止dfs访问过的边原路返回构成了环，需要加上prev节点
  • 三个visited的状态0-未访问，1-正在访问，2-已经访问
  • 有且只有一个联通图

class Solution(object):
    def validTree(self, n, edges):
        graph = collections.defaultdict(set)
        for i, j in edges:
            graph[i].add(j)
            graph[j].add(i)

        visited = [0] * n
        if not self.dfs(-1, 0, visited, graph):
                return False
        return (0 not in visited)

    def dfs(self, prev, i, visited, graph):
        if visited[i] == 2:
            return True

        if visited[i] == 1:
            return False

        visited[i] = 1

        for nei in graph[i]:
            if nei == prev:
                continue
            if not self.dfs(i, nei, visited, graph):
                return False

        visited[i] = 2
        return True

• 解法3. BFS
  • 和DFS思路一样，要避免边的对称性导致的往回检测

class Solution(object):
    def validTree(self, n, edges):
        graph = collections.defaultdict(set)
        for i, j in edges:
            graph[i].add(j)
            graph[j].add(i)

        visited = [0] * n
        queue = collections.deque([(0, -1)])
        while queue:
            node, prev = queue.popleft()
            visited[node] = 1
            for nei in graph[node]:
                if nei == prev:
                    continue
                if visited[nei]:
                    return False
                queue.append((nei, node))
        return sum(visited) == n

Directed graph

207. Course Schedule

• Directed graph: DFS, BFS

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

有向图，This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

• 解法1. DFS

visited三种状态，-1正在visit, 0未visit, 1已经visit

• Why 三种状态？or 两种状态？
  • 两种状态，做DFS时间复杂度是O(n^2)
  • 引入第三种状态，可以避免访问已经访问过不构成环的点，O(n)

# Time : O(n)
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(set)
        for c, p in prerequisites:
            graph[c].add(p)

        visited = [0] * numCourses

        for i in xrange(numCourses):
            if not self.dfs(i, visited, graph):
                return False
        return True

    def dfs(self, i, visited, graph):
        if visited[i] == 1:
            return True

        if visited[i] == -1:
            return False

        visited[i] = -1

        for edge in graph[i]:
            if not self.dfs(edge, visited, graph):
                return False

        visited[i] = 1
        return True

• 解法2. BFS

有向图的BFS算法还是比较有意思的，基于indegree的！ Indegree, 每次访问入度为0的节点，并删掉所在边，最后sum(indegree) == 0!

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in xrange(numCourses)]
        indegree = [0] * numCourses
        for i, j in prerequisites:
            graph[j].append(i)
            indegree[i] += 1

        queue = [i for i in xrange(numCourses) if indegree[i] == 0]
        while queue:
            course = queue.pop(0)
            for n in graph[course]:
                indegree[n] -= 1
                if indegree[n] == 0:
                    queue.append(n)
        return sum(indegree) == 0