0%

Essential Graph Algorithms

What is a Graph

Non-directed

Directed

Cycle Detection

Non-directed Graph

Union-Find

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
class UF:
def __init__(self):
self.uf = {}

def find(self, x: int) -> int:
uf = self.uf
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = self.find(uf[x])
return uf[x]

def union(self, x: int, y: int) -> None:
# x -> y
uf = self.uf
uf[self.find(x)] = self.find(y)

def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:
uf = UF()

for u, v in edges:
if uf.find(u) == uf.find(v):
return True
uf.union(u, v)

return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 1), (2, 1), (1, 3)])

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
def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:

def dfs(u: int, p: int) -> bool:
visited.add(u)

for v in graph[u]:
if v == p: continue
if v in visited or dfs(v, u):
return True

return False

graph, visited = defaultdict(set), set()

for u, v in edges:
graph[u].add(v)
graph[v].add(u)

for u in range(n):
if u not in visited and dfs(u, None):
return True
return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 1), (2, 1), (1, 3)])

Directed 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
def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:

def dfs(u: int) -> bool:
visited.add(u), stack.add(u)

for v in graph[u]:
if v in stack or v not in visited and dfs(v):
return True

stack.remove(u)
return False

graph, visited, stack = defaultdict(set), set(), set()

for u, v in edges:
graph[u].add(v)

for u in range(n):
if u not in visited and dfs(u):
return True
return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 2), (0, 1), (2, 1), (1, 3)])

Euler Path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_euler_path(start: int, edges: List[Tuple[int, int]]) -> List[int]:
# Assume euler path does exist
def dfs(u):
while graph[u]:
v = graph[u].pop()
dfs(v)
ret.append(u)

graph, ret = defaultdict(set), []
for u, v in edges:
graph[u].add(v)

dfs(start)
return ret[::-1]

print(find_euler_path(0, [(0, 1), (1, 0), (1, 2), (2, 3), (3, 1), (1, 4)] ))

Shortest Path

Dijkstra

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
from sortedcontainers import SortedList
def dijkstra(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> List[int]:
graph, dist, prev = defaultdict(dict), defaultdict(lambda: math.inf), {}

for u, v, w in edges:
graph[u][v] = w

q = SortedList([(0, begin)])
dist[0] = 0
while q:
_, u = q.pop(0)
for v, w in graph[u].items():
if dist[v] > dist[u] + w:
q.discard((dist[v], v)) # this will reduce the time complexity from O(E*log(V)) to O(V*log(V))
prev[v] = u
dist[v] = dist[u] + w
q.add((dist[v], v))

if dist[end] == math.inf:
return []

def bt(cur):
if cur == begin:
return [begin]
return bt(prev[cur]) + [cur]
return bt(end)

print(dijkstra(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Bellman Ford

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 bellman_ford(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> List[int]:
dist = defaultdict(lambda: math.inf)
dist[begin], prev = 0, {}

for _ in range(n):
upd = 0
for u, v, w in edges:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
prev[v] = u
upd += 1
if not upd:
break

for u, v, w in edges:
if dist[u] + w < dist[v]:
raise Exception('Negative cycle')

def bt(u):
if u == begin:
return [begin]
return bt(prev[u]) + [u]
return bt(end)

print(bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Floyd Warshall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def floyd_warshall(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> int:
dist = defaultdict(lambda: math.inf)

for u, v, w in edges:
dist[(u, v)] = w

for k in range(n):
for u in range(n):
for v in range(n):
if dist[(u, k)] + dist[(k, v)] < dist[(u, v)]:
dist[(u, v)] = dist[(u, k)] + dist[(k, v)]

return dist[(begin, end)]

print(floyd_warshall(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Minimal Spanning Tree

Kruskal’s method

1
2
3
4
5
6
7
8
9
10
11
def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> int:
uf, ret = UF(), []

for u, v, w in sorted(edges, key=lambda x: x[2]):
if uf.find(u) != uf.find(v):
ret.append((u, v, w))
uf.union(u, v)

return ret if len(set(map(uf.find, range(n)))) == 1 else []

print(kruskal(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Prim’s method

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
from sortedcontainers import SortedList
def prim(n: int, edges: List[Tuple[int, int, int]]) -> int:
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = w

start = 0
pq, ret, visited, prev = SortedList([(0, start, None)]), [], set(), {}

while pq:
if len(visited) == n:
break
w, u, p = pq.pop(0)
if u in visited: continue

visited.add(u), ret.append((p, u, w))

for v, w in graph[u].items():
if v in visited: continue
if v in prev and prev[v][1] >= w:
pq.remove((prev[v][1], v, prev[v][0]))
prev[v] = (u, w)
pq.add((w, v, u))

return ret[1:] if len(visited) == n else []

print(prim(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Tarjan’s algorithm

Strong Connected Component

Cutting Edge

Cutting Vertex