Graph-Algorithms

Posted on | In , |

Topological ordering

Definition

A topological ordering of a directed graph G is a a labelling f of G’s nodes such that:

  • the f(v)’s are the set {1, 2, …, n}
  • $(u, v) \in G => f(u) < f(v) $

Motivation:
sequence tasks while respecting all precedence constraints
Note: G has directed cycle => no topological ordering
Theorem: no directed cycle => can compute topological ordering in O(m+n) time (DFS + book kepping)
Time: O(V+E)
Reason: O(1) per node, O(1) per edge
Correctness: need to show that if (u,v) is an edge, then f(u) < f(v)

  • case1 u visited by DFS before v => recursive call corresponding to v finishes before that of u (since DFS) => f(v) > f(u)
  • case2: v visited before u => v’s recursive call finishes before u’s even starts => f(v) > f(u)

Examples

Course Schedule
https://www.hrwhisper.me/leetcode-graph/
https://leetcode.com/problems/course-schedule-ii/description/

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
# 1. 每次找入度为0的点，输出该入度为0的点，并删除与之相连接的边
# 2. 重复1直到没有入度为0的点。之前输出入度为0的点若小于原图的结点数，那么说明图有环，即拓扑排序不存在，否则即为拓扑排序。
# Time O(V+E)  Space O(E)
def findOrder(numCourses, prerequisites):
    degrees = [0] * numCourses
    childs = [[] for _ in range(numCourses)]
    for t,s in prerequisites:
        degrees[t] += 1
        childs[s].append(t)
    
    res = []
    courses = set(range(numCourses))
    flag = True
    
    while flag and courses:
        flag = False
        removeList = []
        for c in courses:
            if degrees[c] == 0:
                res.append(c)
                for child in childs[c]:
                    degrees[child] -= 1
                removeList.append(c)
                flag = True
        for c in removeList:
            courses.remove(c)
    
    return res if len(courses) == 0 else []

Union Find

  1. simple version for undirected graph

    1
    2
    3
    4
    5
    6
    7
    parent = {}
    def init(node):
        if node not in parent:
            parent[node] = node
    def find(node):
        # no path compression
        return node if parent[node] == node else find(parent[node])

  2. for directed graph

  3. with path compression

e.g.
https://leetcode.com/problems/redundant-connection/description/
https://leetcode.com/problems/number-of-islands-ii/description/

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
def numIslands2(self, m, n, positions):
    parent = {}
    rank = {}
    self.cnt = 0
    
    def find(x):
        if parent[x] != x:
            # path compression
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        x, y = find(x), find(y)
        if x != y:
            if rank[x] < rank[y]:
                x, y = y, x
            parent[y] = x
            rank[x] += rank[y]
            self.cnt -= 1
    
    def add((i, j)):
        x = parent[x] = i, j
        rank[x] = 0
        self.cnt += 1
        for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
            if y in parent:
                union(x,y)
    
    map(add, positions)
    return self.cnt

Floyd Algorithm

正如我们所知道的，Floyd算法用于求最短路径。Floyd算法可以说是Warshall算法的扩展，三个for循环就可以解决问题，所以它的时间复杂度为O(n^3)。

Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#http://bookshadow.com/weblog/2016/09/11/leetcode-evaluate-division/
# Floyd算法求解传递闭包
# 输入等式可以看做一个有向图
# 例如等式a / b = 2.0，可以转化为两条边：<a, b>，<b, a>，其长度分别为2.0，0.5
# 遍历equations与values，利用字典g保存有向图中各边的长度，g的keys即为顶点集
# 最后调用Floyd算法即可
# Time O(N^3) Space O(N^2)
def calcEquation(self, equations, values, queries):
    g = defaultdict(lambda: defaultdict(int))
    for (s,t), v in zip(equations, values):
        g[s][t] = v
        g[t][s] = 1.0/v
    
    for k in g:
        g[k][k] = 1.0
        for s in g:
            for t in g:
                if g[s][k] and g[k][t]:
                    g[s][t] = g[s][k] * g[k][t]
    
    return [ g[s][t] if g[s][t] else -1.0 for s,t in queries]

Bellman Ford Algorithm