Patterns Graphs
Here is a collection of different graph algorithms.
Floyd-Warshall
It will find the shortest paths between all pairs of nodes in $O(n^3)$ time, where $n$ is number of nodes. Sanity check here means that we have cycles with negative weigth.
def floyd_warshall(n, edges):
dist = [[0 if i == j else float("inf") for i in range(n)] for j in range(n)]
pred = [[None] * n for _ in range(n)]
for u, v, d in edges:
dist[u][v] = d
pred[u][v] = u
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
pred[i][j] = pred[k][j]
"""Sanity Check
for u, v, d in edges:
if dist[u] + d < dist[v]:
return None
"""
return dist, pred
Bellman-Ford algorithm
It will find shortest paths from given node to all others, if we can have negative weights, but not negative cycles. Time complexity is $O(mn)$, where $m$ is number of edges and $n$ is number of nodes. Sanity check again is used to find existance of negative loops.
def bellman_ford(n, edges, start):
dist = [float("inf")] * n
pred = [None] * n
dist[start] = 0
for _ in range(n):
for u, v, d in edges:
if dist[u] + d < dist[v]:
dist[v] = dist[u] + d
pred[v] = u
"""Sanity Check
for u, v, d in edges:
if dist[u] + d < dist[v]:
return None
"""
return dist, pred
Strongly Connected Components, Tarjan
Here is Tarjan algorithm to detect strongly connected components in directed graph. Time and space complexity is $O(E+V)$ (however with quite big constant, like 5-7). Input is directed unweighted graph and output will be list of length $n$, where for each node we have index of SCC.
from collections import defaultdict
class Solution:
def SCCU_helper(self, u):
self.disc[u] = self.Time
self.low[u] = self.Time
self.Time += 1
self.stackMember[u] = True
self.st.append(u)
for v in self.graph[u]:
if self.disc[v] == -1 :
self.SCCU_helper(v)
self.low[u] = min(self.low[u], self.low[v])
elif self.stackMember[v] == True:
self.low[u] = min(self.low[u], self.disc[v])
w = -1
if self.low[u] == self.disc[u]:
while w != u:
w = self.st.pop()
self.comp[w] = u
self.stackMember[w] = False
def SCC(self, n, connections):
self.Time = 0
self.disc = [-1] * n #discovery time
self.low = [-1] * n #low link
self.stackMember = [False] * n
self.st = []
self.comp = [-1]*n #component number for each node
self.graph = defaultdict(list)
for u, v in connections:
self.graph[u].append(v)
for i in range(n):
if self.disc[i] == -1:
self.SCCU_helper(i)
return self.comp
Strongly Connected Components, Kosaraju
Here is Kosaraju algorithm to evaluate strongly connected components in graph, complexity is also $O(V + E)$. It will return two pieces of information:
SCC
is list of lists, where in each list we have stronlgy connected component and these components follow the topological sort of graph with components merged to point.out
is list of lengthn
, where for each node we have index of connected component.
def kosaraju(G, n):
SCC, S, P, out, D = [], [], [], [0]*n, [0]*n
st = list(range(n))
while st:
x = st.pop()
if x < 0:
d = D[~x] - 1
if P[-1] > d:
SCC += [S[d:]]
del S[d:], P[-1]
for x in SCC[-1]: D[x] = -1
elif D[x] > 0:
while P[-1] > D[x]: P.pop()
elif D[x] == 0:
S += [x]
P += [len(S)]
D[x] = len(S)
st += [~x]
st += G[x]
for x, comp in enumerate(SCC):
for i in comp: out[i] = x
return SCC[::-1], out
Dijkstra Algorithm
Let $n$ be number of nodes with numbers $0,1,\dots, n-1$ and edges
be edges in form: from, to, weight
. Let start
and end
be nodes between which we want to find minimal distance. Time complexity is $O((E+V)\log V)$, space complexity is $O(E+V)$.
class Solution:
def Dijkstra(self, n, edges, start, end):
dist = [float('inf')] * n
dist[start] = 0
G = defaultdict(list)
for a, b, w in edges:
G[a].append((b, w))
G[b].append((a, w))
heap = [(0, start)]
while heap:
(min_dist, id) = heappop(heap)
if id == end: return min_dist
for neibh, weight in G[id]:
cand = min_dist + weight
if cand < dist[neibh]:
dist[neibh] = cand
heappush(heap, (cand, neibh))
return -1
Code 2
Here is a bit faster implementation of code.
def Dijkstra(graph, K):
q, t = [(0, K)], {}
while q:
time, node = heappop(q)
if node not in t:
t[node] = time
for v, w in graph[node]:
heappush(q, (time + w, v))
return [t.get(i, float("inf")) for i in range(n)]
Bridges
Bridges partition graph into biconnected edge components, goal is to find all bridges in graph in $O(V + E)$ time.
class Solution:
def criticalConnections(self, n, connections):
used, tin, fup = [0]*n, [-1]*n, [-1]*n
self.timer, ans = 0, []
graph = defaultdict(list)
def dfs(node, par = -1):
used[node] = 1
tin[node] = fup[node] = self.timer + 1
self.timer += 1
for child in graph[node]:
if child == par: continue
if used[child] == 1:
fup[node] = min(fup[node], tin[child])
else:
dfs(child, node)
fup[node] = min(fup[node], fup[child])
if fup[child] > tin[node]: ans.append([node, child])
for i, j in connections:
graph[i].append(j)
graph[j].append(i)
for i in range(n):
if not used[i]: dfs(i)
return ans
See also leetcode 1192.
Articulation points
Articulation points in graphs: such points which being removed break graph into parts. Articulation points partition graph into biconnected vertex components. Here is implementation of classical algorithm. Note that it is very similar to bridges with small differences:
- It is
fup[child] >= tin[node]
instead offup[child] > fup[node]
. - We also keep
children
: number of connections and make one more check ifpar = -1
and number of children more than one (it means, they can not have common descendents), then this is also articulation point. - Finally, we keep set of articulation points, not list, because one node can be visited several times during traversal.
class Solution:
def ArticulationPoints(self, n, connections):
used, tin, fup = [0]*n, [-1]*n, [-1]*n
self.timer, ans = 0, set()
graph = defaultdict(list)
def dfs(node, par = -1):
used[node] = 1
tin[node] = fup[node] = self.timer + 1
self.timer += 1
children = 0
for child in graph[node]:
if child == par: continue
if used[child] == 1:
fup[node] = min(fup[node], tin[child])
else:
dfs(child, node)
fup[node] = min(fup[node], fup[child])
if fup[child] >= tin[node] and par != -1: ans.add(node)
children += 1
if par == -1 and children > 1: ans.add(node)
for i, j in connections:
graph[i].append(j)
graph[j].append(i)
for i in range(n):
if not used[i]: dfs(i)
return ans
See also problem 0928, where one of the solutions can use this idea.
Topological sort
Given graph, check if it is DAG, and if it is, give the correct order of nodes, if not, return $[]$. Here is code which use BFS, time and space complexity is $O(V + E)$. verts
is list of vertices and E
is list of edges.
def Topological(verts, edges):
pre, suc = defaultdict(int), defaultdict(list)
for a, b in edges:
pre[a] += 1
suc[b].append(a)
free, out = set(verts) - set(pre), []
while free:
a = free.pop()
out.append(a)
for b in suc[a]:
pre[b] -= 1
if not pre[b]: free.add(b)
return out * (len(out) == len(verts))
Euler path
Given edges of graph, return euler path. Time complexity is O(E + V)
.
Notice that graph is oriented, so it is general case.
def Euler(pairs):
G = defaultdict(list)
D = Counter() # net out degree
for x, y in pairs:
G[x].append(y)
D[x], D[y] = D[x] + 1, D[y] - 1
for k in D:
if D[k] == 1:
x = k
break
ans, stack = [], [x]
while stack:
while G[stack[-1]]:
stack.append(G[stack[-1]].pop())
ans.append(stack.pop())
return ans[::-1]
Bipartite graphs
We can check if graph is bipartite, using usual dfs: either recursive or with stack. With stack it is faster. Time complexity is O(E + V)
.
The result is color
, where color[i]
is 0 or 1 depending on part of graph.
def is_bipartite(graph):
n = len(graph)
color = [-1] * n
for start in range(n):
if color[start] == -1:
color[start] = 0
stack = [start]
while stack:
parent = stack.pop()
for child in graph[parent]:
if color[child] == -1:
color[child] = 1 - color[parent]
stack.append(child)
elif color[parent] == color[child]:
return False, color
return True, color
BFS
Classical bfs implementation: given graph and starting node, we traverse it with bfs.
Function layers
will return layers, where in first layer distance is 0
, then distance is 1
and so on.
def bfs(graph, start=0):
used = [False] * len(graph)
used[start] = True
q = [start]
for v in q:
for w in graph[v]:
if not used[w]:
used[w] = True
q.append(w)
def layers(graph, start=0):
used = [False] * len(graph)
used[start] = True
q, ret = [start], []
while q:
nq = []
ret.append(q)
for v in q:
for w in graph[v]:
if not used[w]:
used[w] = True
nq.append(w)
q = nq
return ret
Bidirectional BFS
We can use bidirectional bfs in the cases, where we need to find the shortest path between nodes beg
and end
.
The idea is to start from both ends and each time choose the end with smaller size of queue. Here we need to be careful: Our invariant, that at each moment of time in our queues we have number of steps (first elements):
[i,i,..., i, i+1, i+1, ..., i+1]
and [j,j,..., j, j+1, j+1, ..., j+1]
We extract left element from first queue and we need to check if it is in second. At this moment we for sure know that distance is not more than i + j. However, it can be either i+j or i+j+1, and we need to check all elements with length i to make sure there is no element from second queue with steps j
. So, first time we see that sum of first elements from our queue is more than limit, it means that we finished to process all candidates, so we can return answer.
Also I add empty the part where we look for all neibhours of node cand
. Usually for bidirectional bfs it makes sense not to construct the whole graph (if we have it, why not just use usual bfs), but we construct connections only if needed: on the fly. So, instead of line neibs = ???
you need to create list of all possible neibhours.
Complexity is potentially as in bfs, but for some graphs it works much better, especially if distance is not very big.
Use with care, code is not full and not fully tested
def bfs_bidir(beg, end):
queue1 = deque([(0, beg)])
queue2 = deque([(0, end)])
visited1 = {beg: 0}
visited2 = {end: 0}
limit, ans = float("inf"), float("inf")
while queue1:
if len(queue1) > len(queue2):
queue1, queue2 = queue2, queue1
visited1, visited2 = visited2, visited1
steps, elem, = queue1.popleft()
if steps + queue2[0][0] > limit: return ans
if elem in visited2:
limit = steps + queue2[0][0]
ans = min(visited1[code] + visited2[code], ans)
neibs = ??? #list of all neibs of elem
for cand in neibs:
if cand not in visited1:
visited1[cand] = step + 1
queue1.append((steps + 1, cand))
return -1
LCA
Given tree, the goal is to answer queries: find LCA of two given nodes. There are at least two different approaches to solve this problem:
1.1 First way is to use Eulerian traversal of graph and then use segment tree/sparse table to answer queries.
Also we need indxs
array\dict where for each value we keep the last occurence of this node (in fact we can keep any occurence, but it is easy to code for the last one).
full code not tested here
self.arr, self.dep = [], [] #euler path
def dfs(node, depth):
self.arr += [node]
self.dep += [depth]
for child in filter(None, [node.left, node.right]):
dfs(child, depth + 1)
self.arr += [node]
self.dep += [depth]
dfs(root, 0)
indxs = {x:i for i, x in enumerate(self.arr)}
1.2 Another way is to use dfs, where for each node we keep the time when we extracted this node from dfs stack. I think it is more or less equivalent to the previous approach.
class RangeQuery:
def __init__(self, data, func=min):
self.func = func
self._data = _data = [list(data)]
i, n = 1, len(_data[0])
while 2 * i <= n:
prev = _data[-1]
_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
i <<= 1
def query(self, begin, end):
depth = (end - begin).bit_length() - 1
return self.func(self._data[depth][begin], self._data[depth][end - (1 << depth)])
class LCA:
def __init__(self, root, graph):
self.time = [-1] * len(graph)
self.path = [-1] * len(graph)
P = [-1] * len(graph)
t = -1
dfs = [root]
while dfs:
node = dfs.pop()
self.path[t] = P[node]
self.time[node] = t = t + 1
for nei in graph[node]:
if self.time[nei] == -1:
P[nei] = node
dfs.append(nei)
self.rmq = RangeQuery(self.time[node] for node in self.path)
def __call__(self, a, b):
if a == b:
return a
a = self.time[a]
b = self.time[b]
if a > b:
a, b = b, a
return self.path[self.rmq.query(a, b)]
2.0 Use binary lyfting, see Leetcode 1724 solution for more details.
Hungarian algorithm
Given n x n
matrix the goal is to choose such n
cells, no two of them lies in the same line or row such that sum of given cells is maximized
Here is so-called hungarian algorighm with time complexity O(n^3)
. The result will be total sum and coordinates of cells.
def hungarian(G, T=1e-6):
n = len(G)
U, V = range(n), range(n)
mu, mv = [None] * n, [None] * n
lu = [max(row) for row in G]
lv = [0] * n
for root in U:
au = [False] * n
au[root] = True
Av = [None] * n
slack = [(lu[root] + lv[v] - G[root][v], root) for v in V]
while True:
(delta, u), v = min((slack[v], v) for v in V if Av[v] == None)
if delta > T:
for u0 in U:
if au[u0]: lu[u0] -= delta
for v0 in V:
if Av[v0] != None: lv[v0] += delta
else:
(val, arg) = slack[v0]
slack[v0] = (val - delta, arg)
Av[v] = u
if mv[v] == None: break
u1 = mv[v]
au[u1] = True
for v1 in V:
if Av[v1] == None:
slack[v1] = min((lu[u1] + lv[v1] - G[u1][v1], u1), slack[v1])
while v != None:
u = Av[v]
prec = mu[u]
mv[v] = u
mu[u] = v
v = prec
return (mu, sum(lu) + sum(lv))
Maximum bipartite matching
Given bipartite graph G
, the goal is to find the maximum bipartite matching. We can do it in O(E * n)
time. Output will be list, where for each node we have None
if it is not in partitioning and node if it is. For example for graph with parts {0, 1, 2, 3}
and {4, 5, 6}
, where we have edges (0, 5), (1, 5), (2, 4), (2, 6), (3, 6)
one of the possible answers is [5, None, 4, 6, 2, 0, 3]
, meaning that we found edges (0, 5), (2, 4), (3, 6)
.
def dfs(u, G, V, match):
for v in G[u]:
if not V[v]:
V[v] = True
if match[v] is None or dfs(match[v], G, V, match):
match[v] = u
return True
return False
def max_bipartite_matching(G):
n = len(G)
match = [None] * n
for u in range(n):
dfs(u, G, [False] * n, match)
return match