01/03/2020
Graph - 14. Bipartite Problem

#14 Bipartite Problem

#14.1 Decide whether a given undirected graph is a bipartite graph

Algorithm

BFS

Java IsBipartite

TODO

1
2

Python IsBipartite

1
2

#14.2 Maximum Cardinality Bipartite Matching (MCBM)

Some examples of unweighted bipartite matching problem that could use maximum flow algorithm, like Ford-Fulkerson to solve:

  • Mice and Owls problem
  • Book selection problem
  • Elementary Math problem

01/03/2020
Graph - 13. Network Flow

#13. Network Flow

#13.1 Concept

#What is a Flow Graph?

A flow graph is a directed, where each edge (also called an arc) has a certain capacity

#What is an Augmenting Path?

Augmenting path is a path of edges in the residual graph with remaining capacity greater than 0 from the source s to the destination t.

  • How to find the augmenting path is flexible in Ford-Fulkerson algorithm, there are multiple ways.
  • Every augmenting path has a bottle-neck, which is the smallest (capacity - flow) on the path.
    • In the above example, the bottle-neck is edge (3, 0)
  • Augmenting the flow means updating the flow values along the augmenting path.
    • For forward edge, increasing the flow by the bottle-neck value.
    • For backward edge, also called residual edge, decreasing the flow by the bottle-neck value
  • Residual edge exist to undo bad augmenting paths that do not lead to a maximum flow

#What is Residual Graph?

  • Think every edge in the original graph as also having a residual edge with a flow/capacity of 0/0
  • The resulting graph is a residual graph
    • Example of residual graph

#13.2 Ford-Fulkerson Algorithm

Algorithm

  • Keep finding augmenting path, then augments the flow until no more augmenting path from s to t
  • The sum of the bottle-necks found in each augmenting path is equal to the max flow.
  • The flow into the destination is also the max flow

Assuming the method of finding augmenting paths is by using DFS, then the Ford-Fulkerson algorithm runs in O(fE), where f is the maximum flow and E is the number of Edges.

1
Time Complexity: O(fE), where f is the maximum flow and E is the number of Edges.

There are other ways to find the augmenting path, Edmonds-Karp is the famous one.

Python Ford-Fulkerson Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import math
import flowgraph
# Problem: Ford-Fulkerson is used to find the maximum flow on a flow graph
# Performance: O(fE) time, where f is the maximum flow and E is the number of edges in the graph
# Notes:
# A flow graph is a `directed graph` with each edge has a flow and capacity.
def fordfulkerson(g):
"""
:type g: a FlowGraph
:rtype: int
"""
res = 0
flow = augmenting_path(g)
while flow != 0:
res += flow
flow = augmenting_path(g)
return res
def augmenting_path(g):
"""
:type g: a FlowGraph
:rtype: int
"""
visited = set()
return dfs(g, g.s, visited, math.inf)
def dfs(g, v, visited, flow):
"""
:type g: a FlowGraph
:type v: int
:type visited: set
:type flow: int
:rtype: int
"""
if v == g.t:
return flow
graph = g.graph
visited.add(v)
for adj in graph[v]:
if adj not in visited:
edge = graph[v][adj]
if edge.remaining_capacity() > 0:
bottleneck = dfs(g, adj, visited, min(flow, edge.remaining_capacity()))
if bottleneck > 0:
edge.augment(bottleneck)
return bottleneck
visited.remove(v)
return 0
def main():
n = 12
s, t = n - 2, n - 1
graph = flowgraph.FlowGraph(n, s, t)
print(graph.t)
# Set up edges from source
graph.add_edge(graph.s, 0, 10)
graph.add_edge(graph.s, 1, 5)
graph.add_edge(graph.s, 2, 10)
# Set up middle edges
graph.add_edge(0, 3, 10)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 5, 15)
graph.add_edge(3, 1, 20)
graph.add_edge(3, 6, 15)
graph.add_edge(4, 1, 15)
graph.add_edge(4, 3, 3)
graph.add_edge(5, 4, 4)
graph.add_edge(5, 8, 10)
graph.add_edge(6, 7, 10)
graph.add_edge(7, 5, 7)
# Set up edges to destination
graph.add_edge(6, graph.t, 15)
graph.add_edge(8, graph.t, 10)
# Expected result of the above graph
expected_flow = 23
maxflow = fordfulkerson(graph)
print('expected result is %d, actual result is %d' % (expected_flow, maxflow))
main()

#13.3 Edmonds Karp Algorithm

  • Using BFS instead of DFS to find the augmenting path.
  • Takes O(VE^2 ) time, the difference is this time complexity no longer depends on the capacity value of any edge.
1
Time Complexity: O(VE^2 ), where V is the number of vertices and E is the number of Edges.

Python Ford-Fulkerson with Edmonds Karp

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import collections
import math
import flowgraph
# Problem: Ford-Fulkerson is used to find the maximum flow on a flow graph
# Performance: O(VE^2) time
def edmondskarp(g):
"""
:type g: a flow graph
:rtype: int
"""
res = 0
flow = augmenting_path(g)
while flow != 0:
res += flow
flow = augmenting_path(g)
return res
def augmenting_path(g):
"""
:type g: a flow graph
:rtype: int
"""
visited = set()
queue = collections.deque()
prev = {} # node -> edge poiting to it
queue.append(g.s)
visited.add(g.s)
while queue:
curr = queue.popleft()
if curr == g.t:
break
for adj in g.graph[curr]:
if adj not in visited:
edge = g.graph[curr][adj]
if edge.remaining_capacity() > 0:
queue.append(adj)
visited.add(adj)
prev[adj] = edge
if g.t not in prev:
return 0
bottleneck = math.inf
node = g.t
while node != g.s:
bottleneck = min(bottleneck, prev[node].remaining_capacity())
node = prev[node].s
node = g.t
while node != g.s:
prev[node].augment(bottleneck)
node = prev[node].s
return bottleneck
def main():
n = 12
s, t = n - 2, n - 1
graph = flowgraph.FlowGraph(n, s, t)
# Set up edges from source
graph.add_edge(graph.s, 0, 10)
graph.add_edge(graph.s, 1, 5)
graph.add_edge(graph.s, 2, 10)
# Set up middle edges
graph.add_edge(0, 3, 10)
graph.add_edge(1, 2, 10)
graph.add_edge(2, 5, 15)
graph.add_edge(3, 1, 20)
graph.add_edge(3, 6, 15)
graph.add_edge(4, 1, 15)
graph.add_edge(4, 3, 3)
graph.add_edge(5, 4, 4)
graph.add_edge(5, 8, 10)
graph.add_edge(6, 7, 10)
graph.add_edge(7, 5, 7)
# Set up edges to destination
graph.add_edge(6, graph.t, 15)
graph.add_edge(8, graph.t, 10)
# Expected result of the above graph
expected_flow = 23
maxflow = edmondskarp(graph)
print('expected result is %d, actual result is %d' % (expected_flow, maxflow))
main()

#13.4 Capacity Scaling

capacity scaling is another technique to use heuristic to efficiently find augmenting path.

  1. Find the largest capacity in the flow graph, call it U
  2. Find the delta, which is the largest 2^x that’s less or equal to U
  3. Find augmenting path with capacity > than delta
  4. If no more augmenting path has capacity greater than delta, then delta /= 2
  5. Repeat until delta <= 0
1
Time Complexity: O(log(U) * E^2), where U is the largest capacity in the flow graph.

#13.5 Dinic Algorithm

Another heuristic to efficiently find augmenting path. 太难了.

01/03/2020
Graph - 12. Traveling Salesman Problem

#12. Traveling Salesman Problem

  • Dynamic Programming problem
1
2
Time O(N^2 * 2^N)
Space O(N * 2^N)

Python Traveling Salesman Problem

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# Problem: Travelling salesman problem
# Given a complete weighted graph, find a hamiltonian cycle of the minimum cost
#
# Algorithm:
# Dynamic programming, O(N^2 * 2^N) time, O(N * 2^N) space
import math
def tsp(matrix, start):
"""
:type matrix: List[List[int]], adjacency matrix
:type start: int, staring node
:rtype: int
"""
if not matrix:
return 0
n = len(matrix)
# dp[n][2^n], represents the minimum cost from s to i with x ndoes visited, where x is the bit set in the state.
dp = [[math.inf for j in range(1 << n)] for i in range(n)]
for i in range(n):
if i != start:
dp[i][(1 << start | 1 << i)] = matrix[start][i]
for r in range(3, n + 1):
# r means how many nodes have been visited
for state in combinations(r, n):
if is_set(start, state):
for adj in range(n):
if adj != start and is_set(adj, state):
prev_state = state ^ (1 << adj)
min_dist = math.inf
for prev in range(n):
if prev != start and prev != adj and is_set(prev, state):
dist = dp[prev][prev_state] + matrix[prev][adj]
min_dist = min(min_dist, dist)
dp[adj][state] = min_dist
# Find min cost from the last state to back to start
res = math.inf
end_state = (1 << n) - 1
for i in range(n):
if i != start:
dist = dp[i][end_state] + matrix[i][start]
res = min(res, dist)
get_path(matrix, dp, start)
return res
def get_path(matrix, dp, start):
"""
:type matrix: List[List[int]], adjacency matrix
:type dp: List[List[int]]
:type start: int
:rtype: tuple(int)
"""
n = len(matrix)
last_index = start
state = (1 << n) - 1
path = [0 for i in range(n + 1)]
for i in range(n - 1, 0, -1):
candidate = -1
min_dist = math.inf
for j in range(n):
if j != start and is_set(j, state):
dist = dp[j][state] + matrix[j][last_index]
if dist < min_dist:
min_dist = dist
candidate = j
path.append(j)
state = state ^ (1 << candidate)
last_index = candidate
path[0] = path[n] = start
return path[::-1]
# Find all combinations of n bits with r set to 1s
# example: combinations(3, 4) => [0111, 1011, 1101, 1110]
def combinations(r, n):
"""
:type r: int
:type n: int
:rtype: List[int]
"""
res = set()
backtrack(0, 0, r, n, res)
return res
def backtrack(curr, pos, r, n, res):
"""
:type curr: int, curr value
:type pos: int, current index
:type r: int
:type n: int
:type res: List[int]
"""
if r == 0:
res.add(curr)
return
for i in range(pos, n):
curr |= (1 << i)
backtrack(curr, i + 1, r - 1, n, res)
curr &= ~(1 << i)
def is_set(i, bits):
return bits & (1 << i) == 1

01/03/2020
Graph - 11. Shortest Path

#11. Shortest Path

  • Topo sort + relax: O(E + V) time. Only work for DAG
  • Dijkstra, work for graph without negative weight. 可以有环.
  • Bellman-Ford, work for graph without negative cycle, 可以有negative weight, 也可以有环
  • Floyd-Warshall, all sources shortest path algorithm
Algorithm Condition Time Space
Topological Sort + Relaxing DAG O(V) O(V)
Dijkstra Without Negative Edge O((E + V)log(V))
Bellman-Ford Without Negative Cycle O(EV)
Floyd-Warshall All pairs shortest path O(V^3 )

#11.1 Topological Sort to Find Shortest Path for Directed Acyclic Graph (DAG)

Only work for weighed DAG, either positive or negative weight

#Algorithm of Acyclic Shortest Path

  1. Topological Sort
  2. Relaxing based on topological order

#Performance

1
Time: O(E + V)

#Proof

因为是Acyclic, 而且是topological order, 所以each edge is relaxed exactly once.

  1. distTo[w]不可能increase, 因为我们只有当distTo[v] + weight(v, w) < dist[w]的时候才更新dist[w]
  2. distTo[v]不可能再有所改变. 因为是topological order, 当处理到w的时候可以保证已经没有任何未处理的edge再指向v.

Java Acyclic Shortest Path Problem

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
public class AcyclicShortestPath {
public static Map<Integer, Integer> acyclicShortestPath(final Map<Integer, Map<Integer, Integer>> graph, final int source) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Map<Integer, Integer> dist = new HashMap<>();
for (final int v : graph.keySet()) {
dist.put(v, Integer.MAX_VALUE);
}
dist.put(v, 0);
final List<Integer> topologicalOrder = TopologicalSort.topologicalSortDFS(graph);
for (final int v : topologicalOrder) {
for (final int adj : graph.get(v)) {
relax(adj, v, graph.get(v).get(adj), dist);
}
}
return dist;
}
private static void relax(final int v, final int parent, final int weight, Map<Integer, Integer> dist) {
final int updatedWeight = dist.get(parent) + weight;
if (updatedWeight < dist.get(v)) {
dist.put(v, updatedWeight);
}
}
}

Python Acyclic Shortest Path Problem

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#!/usr/bin/python
import collections
import toposort
# Problem: SSSP on a Weighted DAG
# Solution: toplogical sort + relax
# This algorithm assumes:
# 1. the input graph is a DAG
# 2. the input graph has the start and end node.
# 3. every node in the graph is reachable from node
# 4. there is only one node with 0 indegree, which is the starting node
INT_MAX = 2147483647
def shortest_path(graph, start, end):
"""
:type graph: Dict[int, Dict[int, int]]
:type start: int
:type end: int
:rtype: void
"""
if not graph:
raise Exception("invalid graph")
if start not in graph or end not in graph:
raise Exception("invalid input")
ordered = toposort.topo_sort_dfs(graph)
dist, path = collections.defaultdict(lambda: INT_MAX), collections.defaultdict(lambda: INT_MAX)
dist[start] = 0
dfs(graph, start, end, dist, path)
print("shortest length is: %d" % dist[end])
print("shortest path is: %s" % get_path(path, start, end))
def dfs(graph, v, end, dist, path):
if v == end:
return
for adj in graph[v].keys():
if dist[v] + graph[v][adj] < dist[adj]:
dist[adj] = dist[v] + graph[v][adj]
path[adj] = v
dfs(graph, adj, end, dist, path)
def get_path(path, start, end):
res = ''
v = end
while v != start:
res = v + ", " + res
v = path[v]
return res

#11.2 Longest Path Problem

  • For general longest path problem, it’s an NP-Hard problem
  • For DAG, use topological sort to find the longest path

#Algorithm

  1. Negate all weights. (This solution allows negative weights)
  2. Run AcyclicShortestPath Algorithm.
  3. Negate back the results.

#11.2.1 Parallel Job Scheduling Problem

Given a set of jobs with durations and precedence constraints, schedule the jobs by finding the start time for each job, so as to achieve the minimum completion time, while respecting the constraints.

This is a longest path problem

Solution:

  1. Create an edge-weighted DAG.
  2. Two virtual vertices representing:
    • Source: “Before everything start”
    • Destination: “After everything is done”
  3. Each job will create 2 vertices
    • Job start
    • Job end
    • The weight is the duration
    • There will be at least 3 edges for each job (not vertex)
      • Job start –> Job end
      • Source –> Job start
      • Job end –> Destination
  4. Each constraint is an edge.

The longest path of this problem is also called a “critical path”

证明:

  1. Job和Job之间的先后顺序只会产生一条edge, 但不会有weight. 也就是weight是0.
  2. 有weight的都是每一个Job的Duration.

所以比如下图这种情况:

  • 要保证每个Job都完成的话,只能取longest path而不是shortest path.

#11.3 Dijkstra Algorithm

Only work for non-negative weighed directed graph (可以有环).

Dijkstra有两种implementation:

  1. Lazy Implementation
    • not good for dense graph
    • lots of duplicated tuples
  2. Eager Implementation with Indexed Heap

[Notes]

Dijkstra中如果一个node被visit过了, 表示这个node到source的最短距离已经被找到了, 不能improve了, 这也是为什么Dijkstra不能有negative weight的原因.

#Dijkstra vs Eager Prim

They are essentially the same algorithm.

  • Prim’s algorithm picks the closest vertex to the Tree.
  • Dijkstra algorithm picks the closest vertex to the Source.

Both of them are trying to find the spanning tree. (Dijkstra is to find the shortest path from a source to every other vertices.)

  • Prim’s algorithm is for the undirected graph.
  • Dijkstra algorithm is for the directed graph (with no negative weights).

#Performance

1
Time: O(E * log(V)) for IndexedHeap

Java Dijkstra Eager Implementation

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
31
32
33
34
35
36
37
38
39
40
41
public class Dijkastra {
public static Map<Integer, Integer> shortestPath(final Map<Integer, Map<Integer, Integer>> graph, final int source) {
if (graph == null || !graph.containsKey(source)) {
throw new IllegalArgumentException();
}
/* Better to verify if the graph only contains non-negative weight */
final IndexHeap<Integer> minIndexHeap = new IndexHeap<>((x, y) -> x.weight - y.weight);
final Map<Integer, Integer> dist = new HashMap<>();
final Map<Integer, Integer> parent = new HashMap<>();
for (final int v : graph.keySet()) {
dist.put(v, Integer.MAX_VALUE);
}
minIndexHeap.add(source, 0);
while (!minIndexHeap.isEmpty()) {
final int v = minIndexHeap.poll();
for (final int adj : graph.get(v)) {
relax(adj, v, graph.get(v).get(adj), minHeap, dist, parent);
}
}
return dist;
}
private void relax(final int v, final int parent, final int weight,
final IndexHeap<Integer> minIndexHeap, final Map<Integer, Integer> dist, Map<Integer, Integer> parent) {
final int updatedWeight = dist.get(parent) + weight;
if (updatedWeight < dist.get(v)) {
dist.put(v, updatedWeight);
parent.put(v, parent);
if (minIndexHeap.containsKey(v)) {
minIndexHeap.decreaseKey(v, updatedWeight);
} else {
minIndexHeap.add(v, updatedWeight);
}
}
}
}

Python Dijkstra Lazy Implementation

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import heapq
# Problem: SSSP on a weighted directed graph without negative edge
# The algorithm assumes:
# 1. the graph does not have negative edge
# 2. the graph has start and end node
# This is a lazy implementation without updating priority in the heap. The down side of this lazy implementation is
# lots of duplicated tuples in the heap for dense graph.
# There is another eager implementation of dijkstra, which uses an IndexHeap to update the priorities inside the heap.
INT_MAX = 2147483647
def dijkstra(graph, start, end):
"""
:type graph: Dict[int, Dict[int, int]]
:type start: int
:type end: int
:rtype: int, shortest path from start to end
"""
if not graph:
raise Exception("invalid graph")
visited = set()
dist, path = {}
hp = []
# Initialize dist and path
for v in graph.keys():
for w in graph[v].keys():
if v not in dist:
dist[v] = INT_MAX
path[v] = v
if w not in dist:
dist[w] = INT_MAX
path[w] = w
heapq.heappush(hp, (0, start))
dist[start] = 0
while heapq:
curr = heapq.heappop(hp)
distance, v = curr[0], curr[1]
visited.add(v)
if v == end:
return distance
if dist[v] < distance:
continue
for adj in graph[v].keys():
if adj not in visited:
new_dist = distance + graph[v][adj]
if new_dist < dist[adj]:
dist[adj] = new_dist
path[adj] = v
heapq.heappush(hp, (new_dist, adj))
raise Exception("invalid graph")

#11.4 Bellman-Ford Algorithm

Work for Negative Weights on directed graph without negative cycle

#11.4.1 Why Dijkstra doesn’t work for negative edge?

  • 这个slides里的内容很有意思. 先是举例子说明了为什么Dijkstra Algorithm不能在Negative weighted graph上work.
  • 然后可能有人会想出上面Re-weighting的trick. 但是这样的想法是错误的,因为即使这样得到了一个positive weighted graph, 但是shortest path就不是原来那条了!

  • Reference from Princeton’s Algorithm course.

#11.4.2 Algorithm

Relax all edges (in any order) V - 1 times

Bellman-Ford is a Dynamic Programming Algorithm

#11.4.3 Proof: Why V - 1 ?

Check here to see why Bellman-ford algorithm works.

Another proof from Tushar Roy

Relaxing edges的order很大程度上决定了Bellman-Ford algorithm找到shortest path的快慢.

比如Tushar的视频里举了一个例子:

假设有这么一个简单的graph, source是0. 如果按照左边的edge顺序来进行relax, 很显然第一遍iteration只能更新V2的distance. 第二遍iteration只能更新V3的distance. 最后一遍iteration才能找到V4的shortest path.

但是如果edges的relax顺序换成右边的, 那么在第一轮iteration的时候就能找出所有vertices的shortest distance.

所以在worst case的情况下, 需要进行V - 1次relaxing.

#11.4.4 Performance

1
2
3
4
5
6
1. Single Source Shortest Path:
* O(V * E) time
* O(V) space
2. All Sources Shortest Path:
* Apply Bellman-Ford V times. So O(V^2 * E) times.

#11.4.5 Bellman-Ford For All Sources Shortest Path Problem

We can apply Bellman-Ford V times to get all sources shortest distances. (Make every vertex as the single source)

So the time complexity is O(V^2 * E). But What’s the maximum number of edges with V vertices ?

  • 对于每个vertex, 它最多能有V - 1条边, 那么对于整个graph, 最多能有V * (V - 1)条边.
  • 因此Bellman-Ford algorithm在All sources shortest path problem中worst case的时间复杂度是O( V^4 ).
  • Floyd-Warshall algorithm在这个All sources shortest path problem中只需要O(V^3 )

#11.4.6 How to find Negative Cycle

A Shortest path exists iff no negative cycle

  • 因为如果有negative cycle的话, shortest path可以沿着这个cycle无限循环下去, 因为是negative的关系,每绕一圈total weight就更小一点.

Algorithm

上面已经证明了worst case情况下需要进行 V - 1 次relaxing能找到SSSP. 那么我们只需要再多进行一次relax, 如果有vertex的shortest distance有变化(变得更小, 因为relax只有更小才更新), 那么就说明有negative cycle.

Java 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class BellmanFord {
public void Map<Integer, Integer> shortestPath(Map<Integer, Map<Integer, Integer>> graph, final int source) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Map<Integer, Integer> dist = new HashMap<>();
final Map<Integer, Integer> parent = new HashMap<>();
for (final int v : graph.keySet()) {
dist.put(v, Integer.MAX_VALUE);
}
dist.put(source, 0);
for (int i = 0; i < graph.size(); i++) {
relax(graph, dist, parent);
}
// One more relax to detect negative cycle
if (hasNegativeCycle(graph, dist)) {
throw new IllegalArgumentException();
}
return dist;
}
private void relax(final Map<Integer, Map<Integer, Integer>> graph, final Map<Integer, Integer> dist, final Map<Integer, Integer> parent) {
for (final int v : graph.keySet()) {
for (final int adj : graph.get(v)) {
final int updatedWeight = dist.get(v) + graph.get(v).get(adj);
if (updatedWeight < dist[adj]) {
dist.put(adj, updatedWeight);
parent.put(adj, v);
}
}
}
}
private boolean hasNegativeCycle(final Map<Integer, Map<Integer, Integer>> graph, final Map<Integer, Integer> dist) {
for (final int v : graph.keySet()) {
for (final int adj : graph.get(v)) {
final int updatedWeight = dist.get(v) + graph.get(v).get(adj);
if (updatedWeight < dist[adj]) {
return true;
}
}
}
return false;
}
}

Python 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# Problem: SSSP on a weighted directed graph,
# raise exception if negative edge exists
# This algorithm assumes:
# 1. the graph could be any directed graph, with or without negative edges or cycles.
# 2. the graph has start and end node
#
# Why this algorithm works?
# https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
INT_MAX = 2147483647
def bellmanford(graph, start, end):
"""
:type graph: Dict[int, Dict[int, int]]
:type start: int
:type end: int
:rtype: int
"""
if not graph:
raise Exception("invalid graph")
dist = {}
vertices = set()
for v in graph.keys():
for w in graph[v].keys():
vertices.add(v)
vertices.add(w)
dist[v] = INT_MAX
dist[w] = INT_MAX
dist[start] = 0
n = len(vertices)
for _ in range(n - 1):
for v in graph.keys():
for w in graph.keys():
dist[w] = min(dist[w], dist[v] + graph[v][w])
for v in graph.keys():
for w in graph[v].keys():
if dist[v] + graph[v][w] < dist[w]:
raise Exception("negative cycle")
return dist[end]

#11.5 Floyd-Warshall Algorithm

Python Floyd-Warshall Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# Problem: All pairs shortest path problem
# Solution:
# O(V^3) time Dynamic Programming problem
#
# dp[k][i][j] represents the shortest distance from i to j routing through nodes 0 to k
# dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
#
# space is O(V^3) but can be optimized to O(V^2)
# dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
import math
def floyd_warshall(matrix):
"""
:type matrix: List[List[int]], adjacency matrix
If there is no edge between two nodes, the corresponding entry in the matrix is math.inf
:rtype: List[List[int]], all pairs shortest path
"""
if not matrix:
raise Exception("invalid graph")
n = len(matrix)
dp = [[math.inf for j in range(n)] for i in range(n)]
# next[i][j] represents the next node from i if we want to go to j with shortest path
next = [[None for j in range(n)] for i in range(n)]
# Initialization
for i in range(n):
for j in range(n):
dp[i][j] = matrix[i][j]
if matrix[i][j] != math.inf:
next[i][j] = j
# Floyd-Warshall DP
for k in range(n):
for i in range(n):
for j in range(n):
if dp[i][k] + dp[k][j] < dp[i][j]:
dp[i][j] = dp[i][k] + dp[k][j]
next[i][j] = next[i][k]
# Detect Negative Cycle, do DP one more time
for k in range(n):
for i in range(n):
for j in range(n):
if dp[i][k] + dp[k][j] < dp[i][j]:
dp[i][j] = -math.inf
next[i][j] = -1
return dp[n - 1]
def get_path(dp, next, start, end):
"""
:type dp: List[List[int]]
:type next: List[List[int]]
:type start: int
:type end: int
:rtype: List[int]
"""
if dp[start][end] == math.inf:
raise Exception("no path between %s and %s" % (start, end))
elif dp[start][end] == -math.inf:
raise Exception("negative cycle between %s and %s" % (start, end))
path = []
curr = start
while curr != end:
if curr == -1:
raise Exception("negative cycle between %s and %s" % (start, end))
path.append(curr)
curr = next[curr][end]
return path

01/03/2020
Graph - 10. Minimum Spanning Tree

#10. Minimum Spanning Tree

Given: Undirected Graph G with positive edge weights (connected)

Definition: A spanning tree of G is a subgraph that is both a tree (connected and acyclic) and spanning (includes all the vertices)

Goal: Find a spanning tree with minimum weight

下面两种Algorithm都属于Greedy algorithm

#10.1 Kruskal’s Algorithm

利用Union Find.

  1. Sort all edges by weight
  2. Add next edge to Tree unless its creating a cycle (Union-Find)

#Performance

Time: O(E * log(E))

构建minHeap的过程其实是O(E). 但是之后按次序遍历每条edge并把它加入tree, 是O(E * log(E))的操作. 因为union-find可以保证union和find都是O(log(E)

Java Kruskal’s Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class KruskalMST {
private class Edge {
int v;
int w;
int weight;
public Edge(final int v, final int w, final int weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
}
public static Queue<Edge> mstByKruskal(final Map<Integer, Map<Integer, Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Queue<Edge> mst = new LinkedList<>();
final PriorityQueue<Edge> minHeap = new PriorityQueue<>((x, y) -> x.weight - y.weight);
// 因为MST只作用于Undirected Graph. 所以在处理Edge的时候需要去重.
for (final int v : graph.keySet()) {
if (!visited.contains(v)) {
addEdgeToMinHeap(v, graph, visited, minHeap);
}
}
while (!minHeap.isEmpty()) {
final Edge edge = minHeap.poll();
if (!uf.find(edge.v, edge.w)) {
uf.union(edge.v, edge.w);
mst.offer(edge);
}
}
return mst;
}
private void addEdgeToMinHeap(final int v, final Map<Integer, Map<Integer, Integer>> graph, final Set<Integer> visited, final PriorityQueue<Edge> minHeap) {
visited.add(v);
for (final int adj : graph.get(v).keySet()) {
if (!visited.contains(adj)) {
minHeap.offer(new Edge(v, adj, graph.get(v).get(adj)));
addEdgeToMinHeap(adj, graph, visited, minHeap);
}
}
}
}

Python Kruskal’s Algorithm

TODO

1
2

#10.2 Prim’s Algorithm

  • Prims’s Algorithm Works best for dense graph
  • lazy version has runtime O(E * log(E))
  • eager version has runtime O(E * log(V))

#Algorithm

  1. Start with vertex 0 and greedily grow tree.
  2. Add to tree the minimum weight edge with exactly one endpoint in tree.
  3. Repeat until V - 1 edges.

#10.2.1 Lazy Implementation

1
2
Time: O(E * log(E))
Space: O(E)
  • Maintain priority queue by Edges, 和Kruskal’s Algorithm一样, 需要维护一个MinHeap,
  • 但是和Kruskal Algorithm不一样的是, 不需要把所有Edge都一股脑的先加到PriorityQueue里面.
  • 因为我们每次要找的Edge得保证至少一个endpoint在tree里, 所以在minHeap里的东西只需要是所有跟当前mst connect的edges即可.
  • 最终的结果mst可以有多种返回方式, 比如:
    1. 可以返回一个Queue
    2. 也可以返回一个Set
  • 如果是返回一个Set的话, 因为mst的定义就是要包含图中所有vertices, 所以如果mst就可以把它当做visited来用. 而如果mst是一个Queue, 那么需要另外一个visited的数据结构来记录访问情况.

Java Prim’s Lazy Implementation

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
31
32
33
34
35
36
37
38
public class LazyPrimMST {
public static Queue<Edge> mstByLazyPrims(final Map<Integer, Map<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final PriorityQueue<Edge> minHeap = new PriorityQueue<>((x, y) -> x.weight - y.weight);
final Queue<Edge> mst = new LinkedList<>();
final Set<Integer> visited = new HashSet<>();
// Start with any ONE of the vertices
for (final int v : graph.keySet()) {
visit(v, graph, minHeap, mst, visited);
break;
}
while (!minHeap.isEmpty()) {
final Edge edge = minHeap.poll();
if (visited.contains(edge.v) && visited.contains(edge.w)) {
continue;
} else {
mst.offer(edge);
if (!visited.contains(edge.v)) visit(edge.v);
if (!visited.contains(edge.w)) visit(edge.w);
}
}
return mst;
}
private static void visit(final int v, final Map<Integer, Map<Integer, Integer>> graph, final PriorityQueue<Edge> minHeap, final Set<Integer> visited) {
visited.add(v);
for (final int adj : graph.get(v)) {
if (!visited .contains(adj)) {
minHeap.offer(new Edge(v, adj, graph.get(v).get(adj)));
}
}
}
}

Python Prims’s Lazy Implementation

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
31
32
33
34
35
36
37
38
39
40
41
def lazy_prim(graph):
"""
:type grpah: Dict[int, Dict[int, int]] adjacency list representing a weighted undirected graph
:rtype: int, the cost of mst
"""
if not graph:
raise Exception("invalid graph")
hp, mst = [], []
visited, nodes = set(), set()
for v in graph:
for w in graph[v]:
nodes.add(v)
nodes.add(w)
start = next(iter(nodes))
visited.add(start)
mst.append(start)
for adj in graph[start].keys():
if adj not in visited:
heapq.heappush(hp, (graph[start][adj], adj))
cost = 0
while hp:
curr = heapq.heappop(hp)
weight, node = curr[0], curr[1]
if node not in visited:
cost += weight
visited.add(node)
mst.append(node)
if len(mst) == len(nodes):
break
for adj in graph[node].keys():
if adj not in visited:
heapq.heappush(hp, (graph[node][adj], adj))
return cost

#10.2.2 Eager Implementation

1
2
Time: O(E * log(V))
Space: O(V)
  • Maintain priority queue of Vertices.
  • Eager Implementation 需要利用IndexHeapupdate priority. 因为这个方法是将vertex存在priority queue中, 排序方式是vertex与mst之间的weight.

举个栗子:
比如 v - w 的weight是5, v在mst中, w不在. 因为w connected to mst, 所以w结点现在应该在MinHeap中. 假设MinHeap中的top结点是x, x和w之间也有一条边, weight是1。那么当把x加入mst之后, 我们要更新w和tree之间的weight, 从原来的5变为更小的1.

Java Prim’s Eager Implementation

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class EagerPrimMST {
public static Queue<Edge> mstByEagerPrims(final Map<Integer, Map<Integer, Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final IndexHeap<Integer> minIndexHeap = new IndexHeap<>((x, y) -> x.weight - y.weight);
final Queue<Edge> mst = new LinkedList<>();
final Set<Integer> visited = new HashSet<>();
// Store the minimum weight edge from a vertex to current MST
// Not every edge to a vertex!
final Map<Integer, Edge> vertexToMinWeightEdge = new HashMap<>();
// Start with any one of the vertices
for (final int v : graph.keySet()) {
minIndexHeap.decreaseKey(v, 0);
break;
}
while (!minIndexHeap.isEmpty()) {
final int v = minIndexHeap.poll();
visited.add(v);
// vertexToMinWeightEdge存放的是结点v到当前mst中weight最小的edge.
if (vertexToMinWeightEdge.containsKey(v)) {
mst.offer(vertexToMinWeightEdge.get(v));
}
for (final int adj : graph.get(v)) {
// 之所以没有直接negate condition而是要continue,
// 是因为想要强调obsolete edges的概念.
if (visited.contains(adj)) continue; // Obsolete edge
if (graph.get(v).get(adj) < minIndexHeap.getWeight()) {
if (minIndexHeap.contains(adj)) {
minIndexHeap.decreaseKey(adj, graph.get(v).get(adj));
} else {
minIndexHeap.add(adj, graph.get(v).get(adj));
}
vertexToMinWeightEdge(adj, new Edge(v, adj, graph.get(v).get(adj)));
}
}
}
return mst;
}
}

01/03/2020
Graph - 9. Hamilton Cycle / Path

#9. Hamilton Cycle / Path

Hamilton Cycle: A cycle with each vertex exactly once.

Hamilton Cycle是一个Backtracking问题!

#9.1 Hamiltonian Cycle for Directed Graph

Java Hamiltonian Cycle

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static boolean hasHamiltonCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
visited.add(v);
res.add(v);
if (backtracking(v, graph, visited, res)) {
return true;
}
res.remove(0);
visited.remove(v);
}
return false;
}
private static boolean backtracking(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final List<Integer> res) {
if (res.size() == graph.size()) {
// If the last node in res list is connected to the first node in the res list
final int lastNode = res.get(res.size() - 1);
final int firstNode = res.get(0);
if (graph.get(lastNode).contains(firstNode)) {
return true;
} else {
return false;
}
}
for (final int adj : graph.get(v)) {
if (!visited.contains(adj)) {
visited.add(adj);
res.add(adj);
if (backtracking(adj, graph, visited, res)) {
return true;
}
res.remove(res.size() - 1);
visited.remove(adj);
}
}
return false;
}

#9.2 Hamiltonian Cycle for Undirected Graph

Hamilton Cycle对于Undirected Graph依旧是一个Backtracking的problem

和Directed Graph唯一的区别就是要pass一个parent避免无限循环.

Java Hamiltonian Cycle

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
31
32
33
34
35
36
37
38
39
40
41
42
43
public static boolean hasHamiltonCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
return new IllegalArgumentException();
}
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
visited.add(v);
res.add(v);
if (backtracking(v, graph, visited, res, v)) {
return true;
}
res.remove(0);
visited.remove(v);
}
return false;
}
private static void backtracking(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final List<Integer> res, final int parent) {
if (res.size() == graph.size()) {
final lastNode = res.get(res.size() - 1);
final firstNode = res.get(0);
if (graph.get(lastNode).contains(firstNode)) {
return true;
} else {
return false;
}
}
for (final int adj : graph.get(v)) {
if (adj != parent && !visited.contains(adj)) {
visited.add(adj);
res.add(adj);
if (backtracking(adj, graph, visited, res, v)) {
return true;
}
res.remove(res.size() - 1);
res.remove(adj);
}
}
return false;
}

01/03/2020
Graph - 8. Eulerian Cycle / Eulerian Path

#8. Eulerian Cycle / Eulerian Path

欧拉回路: A Cycle with each edge exactly once.

Eulerian Cycle Eulerian Path
Undirected Graph Every vertex has an even degree Every vertex has an even degree or only 2 vertices can have odd degree
Directed Graph Every vertex has the same indegree and outdegree At most 1 vertex has (outdegree) - (indegree) = 1, and at most 1 vertex has (indegree)- (outdegree) = 1, and all other vertices has the same indegree and outdegree
  • If a graph has an Eulerian Cycle, it must have an Eulerian Path

#8.1 Eulerian Cycle for Directed Graph

A directed graph has an Euler Cycle iff:

  1. Every vertex with non-zero degree belong to a single strongly connected component
  2. Every vertex must have the same indegree and outdegree

[Notes]

  • A singleton is a valid node in the eulerian graph. Because eulerian cycle or eulerian path visit each edge once, there is no need to visit that singleton node.
  • In a directed graph, an eulerian path has only one starting node and only one end node. Starting node has (outdegree) - (indegree) = 1, while end node has (indegree) - (outdegree) = 1

Java: Check if the graph has Eulerian Cycle

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
31
public static boolean hasEulerCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
return isStronglyConnected(graph) && hasSameDegree(graph);
}
private static boolean isStronglyConnected(final Map<Integer, Set<Integer>> graph) {
final List<Set<Integer>> scc = StronglyConnectedComponent.scc(graph);
return scc.size() == 1;
}
private static boolean hasSameDegree(final Map<Integer, Set<Integer>> graph) {
final Map<Integer, Integer> degrees = new HashMap<>();
for (final int v : graph.keySet()) {
degrees.putIfAbsent(v, 0);
for (final int adj : graph.get(v)) {
degrees.putIfAbsent(adj, 0);
degrees.put(v, degrees.get(v) - 1);
degrees.put(adj, degrees.get(v) + 1);
}
}
for (final int v : graph.keySet()) {
if (degrees.get(v) != 0) {
return false;
}
}
return true;
}

#8.2 Hierholzer’s Algorithm

Find Euler path/cycle in Directed graph

特别注意这个implementation. 当处理Euler Path/Cycle的问题时,如果需要自己构建graph, 不需要用Inner class来构建Edge, 然后再用类似于Set的数据结构来记录edge的访问情况.

Java Hierholzer’s Algorithm

仔细理解一下下面的code, 用一个Queue来构建adjacency list会省了很多事.

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
31
public static List<Integer> findEulerPath(final Map<Integer, Queue<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final List<Integer> res = new LinkedList<>();
// if there is no cycle, src must have 0 indegree.
final int src = computeIndegreeAndGetSource(graph);
if (src == -1) {
// Euler Cycle, any vertex can be a source, since it's a cycle.
for (final int v : graph.keySet()) {
dfs(v, graph, res);
break;
}
} else {
// Euler Path
dfs(src, graph, res);
}
return res;
}
private void dfs(final int v, final Map<Integer, Queue<Integer>> graph, final List<Integer> res) {
while (!graph.get(v).isEmpty()) {
final int adj = graph.get(v).poll();
dfs(adj, graph, res);
}
res.add(0, v);
}

Python Hierholzer’s Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# Problem: Given a graph, find the eulerian path or eulerian cycle if exists
# Directed graph
# A directed graph has eulerian cycle iff all vertices have the same indegree and outdegree
# A directed graph has eulerian path iff only one vertex has (outdegree) - (indegree) = 1,
# and only one vertex has (indegree) - (outdegree) = 1, and all other vertices have the same indegree
# and outdegree.
# All vertices with `non-zero` degree must be in the same connected component. Otherwise, the graph is disconnected,
# it's impossible to have eulerian path or cycle in a disconnected graph. However, a singleton is a valid node
# in an eulerian graph.
import collections
def euler_directed_graph(graph):
"""
:type graph: Dict[int, List[int]], a directed graph, which can have multiple edges from same src and dst
:rtype: List[int], eulerian path
"""
if not graph:
raise Exception("invalid graph")
# get indegree and outdegree for each node
indegree, outdegree = collections.defaultdict(lambda: 0), collections.defaultdict(lambda: 0)
# nodes have every vertex in the graph, including singleton and those without out-going edges
nodes = set()
# number of edges in the graph
edge_cnt = 0
for v in graph:
edge_cnt += len(graph[v])
for w in graph[v]:
indegree[w] += 1
outdegree[v] += 1
nodes.add(v)
nodes.add(w)
# find the starting node if there is a euler path
start = next(iter(nodes))
start_nodes, end_nodes = 0, 0
for v in nodes:
if indegree[v] - outdegree[v] > 1 or outdegree[v] - indegree[v] > 1:
raise Exception("no eulerian path or cycle")
if outdegree[v] - indegree[v] == 1:
start_nodes += 1
start = v
if indegree[v] - outdegree[v] == 1:
end_nodes += 1
# find eulerian path or cycle
path = []
dfs(start, graph, path)
# check if the graph is disconnected
if len(path) != edge_cnt + 1:
raise Exception("no eulerian path because the graph is disconnected")
return path[::-1]
def dfs(v, graph, path):
"""
:type v: int
:type graph: Dict[int, List[int]], a directed graph, which can have multiple edges from the same src and dst
:type path: List[int]
"""
while len(graph[v]) > 0:
# Must be pop to dedup, because in eulerian path, a vertex can be visited multiple times,
# we can not use a set to keep track visited node.
adj = graph[v].pop()
dfs(adj, graph, path)
path.append(v)
def main():
graph = {}
for v in range(7):
graph[v] = []
graph[1].append(2)
graph[1].append(3)
graph[2].append(2)
graph[2].append(4)
graph[2].append(4)
graph[3].append(1)
graph[3].append(2)
graph[3].append(5)
graph[4].append(3)
graph[4].append(6)
graph[5].append(6)
graph[6].append(3)
expected_path = [1, 3, 5, 6, 3, 2, 4, 3, 1, 2, 2, 4, 6]
actual_path = euler_directed_graph(graph)
if expected_path.sort() != actual_path.sort():
raise Exception("wrong answer")
main()

#8.2 Eulerian Cycle/Path for Undirected Graph

An undirected graph has an Euler Cycle iff:

  1. Every vertex with non-zero degree belong to a single connected component
  2. Every vertex must have even number as its degree

Implementation中注意区分Directed Graph里的isStronglyConnected和Undirected Graph里的isConnected. Strongly Connected Component的概念只有在Directed Graph里才会出现!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static boolean hasEulerCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
return ConnectedComponent.isConnected(graph) && getNumberOfVerticesWithOddDegree(graph) == 0;
}
private static int getNumberOfVerticesWithOddDegree(final Map<Integer, Set<Integer>> graph) {
int count = 0;
for (final int v : graph.keySet()) {
if (graph.get(v).size() % 2 != 0) {
count++;
}
}
return count;
}

An undirected graph has an Euler Path iff:

  1. Every vertex with non-zero degree belong to a single strongly connected component
  2. Only 0 or 2 vertices are allowed to have odd number as its degree, all other vertices must have even number as their degrees.

找path和找cycle几乎一模一样, 唯一的区别就是判断奇数degree的结点个数是不是0或者2

1
2
3
4
5
6
7
8
public static boolean hasEulerPath(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final int oddDegrees getNumberOfVerticesWithOddDegree(graph);
return ConnectedComponent.isConnected(graph) && (oddDegrees == 0 || oddDegrees == 2);
}

01/03/2020
Graph - 7. Articulation Points

#7. Articulation Points (Cut Vertex)

  1. What is Articulation Point?

    • Articulation points are the nodes in a graph, whose removal increases the number of connected components

  2. How to find articulation points?

    1. If an edge (v, w) is a bridge, then either v or w is an articulation point. But articulation points can exist without any bridges.
    2. If id(e.from) == lowlink(e.to), that means there is a cycle
    3. A cycle must be a connected component, and e.from is the starting node of the cycle, which indicates it’s an articulation point.
      • Except the starting node has no outgoing edges. Or only 1 outgoing edge, which is part of the cycle.
    4. So an articulation point must have 2 or more outgoing edges.

[Notes] The “outgoing” here is a logical outgoing, it does not mean the outgoing edge in directed graph, since the whole problem is on an undirected graph. It really means the edges connected to the node.

Python Find Articulation Points

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Problem: Find articulation points on a given graph
def articulation_points(graph):
"""
:type graph: Dict[int, Dict[int, int]]
:rtype: List[int], a list of articulation points in the graph
"""
res = []
if not graph:
return res
visited = set()
nodes = set()
lowlink = {}
candidates = set()
for v in graph.keys():
for w in graph[v].keys():
nodes.add(v)
nodes.add(w)
n = len(nodes)
for i in range(n):
if i not in visited:
dfs(i, -1, graph, lowlink, visited, candidates)
if i in candidates and i in graph and len(graph[i]) > 1:
res.append(i)
return res
def dfs(v, parent, graph, lowlink, visited, candidates):
"""
:type v: int
:type parent: parent
:type graph: Dict[int, Dict[int, int]]
:type lowlink: Dict[int, int]
:type visited: Set[int]
:type points: Set[int]
"""
visited.add(v)
lowlink[v] = v
for adj in graph[v]:
if adj != parent:
if adj not in visited:
dfs(adj, v, graph, lowlink, visited, candidates)
lowlink[v] = min(lowlink[v], lowlink[adj])
else:
lowlink[v] = min(lowlink[v], adj)
if v <= lowlink[adj]:
# when v < lowlink[adj], find a bridge
# when v == lowlink[adj], find a starting point of a cycle
candidates.add(v)

01/03/2020
Graph - 6. Bridges

#6. Bridges (Cut Edges)

  1. What is Bridge?

    • Bridges are the edges in a graph, whose removal increases the number of connected components

  2. Why do we want find bridges?

    • Bridges are often hint at weak points, bottle necks or vulnerabilities in a graph
  3. How to find bridges?

    • If (v, w) is an edge in the graph, the edge is a bridge iff id(v) < lowlink(w)

Java Find Bridges

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
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public List<List<Integer>> findBridges(int n, List<List<Integer>> edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) graph.put(i, new HashSet<>());
for (List<Integer> edge : edges) {
graph.get(edge.get(0)).add(edge.get(1));
graph.get(edge.get(1)).add(edge.get(0));
}
List<List<Integer>> res = new ArrayList<>();
boolean[] visited = new boolean[n];
int[] lowlink = new int[n];
int[] id = new int[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, -1, 0, graph, id, lowlink, visited, res);
}
}
return res;
}
private void dfs(int v, int parent, int i, Map<Integer, Set<Integer>> graph, int[] id, int[] lowlink, boolean[] visited, List<List<Integer>> res) {
lowlink[v] = i;
id[v] = i;
visited[v] = true;
for (int adj : graph.get(v)) {
if (adj != parent) {
if (!visited[adj]) {
dfs(adj, v, i + 1, graph, id, lowlink, visited, res);
lowlink[v] = Math.min(lowlink[v], lowlink[adj]);
if (id[v] < lowlink[adj]) {
res.add(Arrays.asList(v, adj));
}
} else {
lowlink[v] = Math.min(lowlink[v], id[adj]);
}
}
}
}
}

01/03/2020
Graph - 5. Strongly Connected Component

#5. Strongly Connected Component

  1. What is connected graph ?

    • A graph is connected if there is a path between each pair of vertices.
  2. What is strongly connected graph ?

    • A directed graph is strongly connected iff there is a path between each pair of vertices.
    • Strongly connected的概念只存在于Directed Graph

[Notes]

Strongly connected components in G are the same as they are in reversed G!

#5.1 Kosaraju’s Algorithm

  • Algorithm:
    1. Topological sort on reversed G!
    2. Run DFS based on the order from step 1

#Proof of Kosaraju’s Algorithm:

  1. What is Kernel DAG?

    • Kernel DAG是将一个graph里的每个strongly connected component变成一个vertex, 然后把所有这些SCCs给连起来. 得到的结果一定是一个DAG. 比如Tushar视频里的这个图:
      • Reference: Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm from Tushar Roy
    • 4个SCCs连起来的一定是一个DAG. 假设有一条边从(DEF)到(ABC),那么很容易证明(ABCDEF)是一个SCC而不是两个.
  2. Why Kernal DAG ?

Kernel DAG解释了为什么我们要先把G到倒过来求topological order.

  • 用上图的例子来看, 这个order保证了在第二遍找SCCs的DFS的时候我们会从(DEF)中任何一个结点或者(K)来开始DFS, 假设从(DEF)中任何一个结点开始, 根据上面的图很显然我们没有办法走到ABC或者GHIJ. 假设从K开始也很显然没有办法走到GHIJ.
  • 这样就能找到(DEF)和(K)两个strongly connected component. 接下来无论从(ABC)还是(GHIJ)中任意一个结点开始都能顺利找到自己的strongly connected component. 这样就证明了这个算法的可行性.

Java Kosaraju’a Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class StronglyConnectedComponent {
public static List<Set<Integer>> scc(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final List<Set<Integer>> res = new ArrayList<>();
final Map<Integer, Set<Integer>> reversedGraph = reverseGraph(graph);
final List<Integer> sorted = TopologicalSort.topoDFS(graph);
final Set<Integer> visited = new HashSet<>();
for (final int v : sorted) {
if (!visited.contains(v)) {
final Set<Integer> currentComponent = new HashSet<>();
getSCCByDFS(v, graph, visited, currentComponent);
res.add(new HashSet<>(currentComponent));
}
}
return res;
}
private static Map<Integer, Set<Integer>> reverseGraph(final Map<Integer, Set<Integer>> graph) {
final Map<Integer, Set<Integer>> reversedGraph = new HashMap<>();
for (final int v : graph.keySet()) {
reversedGraph.putIfAbsent(v, new HashSet<>());
for (final int adj : graph.get(v)) {
reversedGraph.putIfAbsent(adj, new HashSet<>());
reversedGraph.get(adj).add(v);
}
}
return reversedGraph;
}
private static void getSCCByDFS(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final Set<Integer> scc) {
scc.add(v);
visited.add(v);
for (final int adj : graph.keySet()) {
if (!visited.contains(adj)) {
scc.add(adj);
visited.add(adj);
getSCCByDFS(adj, graph, visited, scc);
}
}
}
}

Python Kosaraju’s Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# Problem: Find strongly connected component in a directed graph
# Algorithm
# 1. Reverse the given graph
# 2. Run topologoical sort on the reversed graph
# 3. Run dfs on the original graph, based on the topological order on the reversed graph
import toposort
def kosaraju(graph):
"""
:type graph: Dict[int, List[int]]
:rtype: List[tuple(int)], a list of tuples, each tuple is a strongly connected component
"""
if not graph:
raise Exception("invalid graph")
reversed_graph = reverse(graph)
order = toposort.topo_sort_dfs(graph)
res = []
visited = set()
for v in order:
if v not in visited:
scc = []
dfs(v, graph, visited, scc)
res.append(tuple(scc))
return res
def dfs(v, graph, visited, scc):
"""
:type v: int
:type graph: Dict[int, List[int]]
:type visited: Set[int]
:type scc: List[int]
"""
visited.add(v)
scc.append(v)
for adj in graph[v]:
if adj not in visited:
dfs(adj, graph, visited, scc)
# Reverse a directed graph
def reverse(graph):
"""
:type graph: Dict[int, List[int]]
:rtype: Dict[int, List[int]]
"""
res = {}
if not graph:
return res
for v in graph:
for adj in graph[v]:
if adj not in res:
res[adj] = []
res[adj].append(v)
return res

#5.2 Tarjan’s Algorithm

  1. What is low-link value?

    • Low-link value: low-link value of a node is the smallest node id reachable from that node when doing a dfs, including itself.

  2. How to update low-link value to find Strongly Connected Component?

    • If there is an edge from v to w in the graph, to update the low-link value of v by lowlink[v] = min(lowlink[v], lowlink[w]), the following 2 conditions must be met in order to find the strongly connected component:
      1. there is a path from v to w
      2. w must be on the stack
    • If a node v is the starting point of a strongly connected component, then it’s id(v) == lowlink(v)
  3. Algorithms:

    1. Maintains a stack, node is added to the stack when they’re visited the first time
    2. Nodes are removed from the stack when a complete SCC is found
    3. If (v, w) is an edge in the graph, to update lowlink value of v, w must be on the stack.
    4. If a node is the starting point the a SCC, it’s value (or id) must be equal to it’s lowlink value

Python Tarjan’s Algorithm

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# Problem: Tarjan's alogrithm is used to find strongly connected component in a directed graph
# Alogorithm:
# 1. maintains a stack, node is added to the stack when they're explored the first time
# 2. nodes are removed from the stack when a complete SCC is found
# 3. if (u, v) is an edge in the graph, to update lowlink value of u, v must be on the stack.
# 4. if a node is the starting point the a SCC, it's value (or id) must be equal to it's lowlink value
def tarjan(graph):
"""
:type graph: Dict[int, Dict[int]]
:rtype: List[tuple(int)], list of tuples, each tuple is a strongly connected component
"""
if not graph:
raise Exception("invalid graph")
res = []
stack = []
on_stack = set()
visited = set()
nodes = set()
lowlink = {}
for v in graph:
for w in graph[v]:
nodes.add(v)
nodes.add(w)
lowlink[v] = v
lowlink[w] = w
for v in nodes:
if v not in visited:
dfs(v, graph, stack, on_stack, lowlink, visited, res)
return res
def dfs(v, graph, stack, on_stack, lowlink, visited, res):
"""
:type v: int
:type graph: Dict[int, Dict[int]]
:type stack: List[int]
:type on_stack: Set[int]
:type lowlink: Dict[int, int]
:type visited: Set[int]
:type res: List[tuple(int)]
"""
visited.add(v)
stack.append(v)
on_stack.add(v)
for adj in graph[v]:
if adj not in visited:
dfs(adj, graph, stack, lowlink, visited, res)
if adj in on_stack:
lowlink[v] = min(lowlink[v], lowlink[adj])
# Find a SCC
if lowlink[v] == v:
scc = []
while stack:
top = stack.pop()
on_stack.remove(top)
scc.append(top)
if top == v:
break
res.append(tuple(scc))

01/03/2020
Graph - 4. Union Find

#4. Union-Find

TODO

Java

1
2

Python

1
2

01/03/2020
Graph - 3. Cycle Detection

#3. Cycle Detection

#3.1 How to detect cycle?

  1. DFS
  2. BFS
  3. Topological Sort (Only for Directed Graph)

#3.1.1 DFS to Detect Cycle

利用递归. 不同于普通遍历, 判断是否有cycle的时候要利用一个HashMap来记录每个结点的状态.

1
2
3
0 - 未访问
1 - 访问结束
-1 - 访问过但还未结束

DFS Cycle Detection for Directed Graph

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
31
32
public static void hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
Map<Integer, Integer> visited = new HashMap<>();
for (final int v : graph.keySet()) {
if (!visited.containsKey(v)) {
if (dfsHasCycle(v, graph, visited)) {
return true;
}
}
}
return false;
}
private static boolean dfsHasCycle(final int v, final Map<Integer, Set<Integer>> graph,
final Map<Integer, Integer> visited) {
final isVisited = visited.getOrDefault(v, 0);
if (isVisited == 1) return false;
if (isVisited == -1) return true;
visited.put(v, -1);
for (final int adj : graph.keySet()) {
if (dfsHasCycle(adj, graph, visited)) {
return true;
}
}
visited.put(v, 1);
return false;
}

DFS Cycle Detection for Undirected Graph

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
31
32
33
34
public static void hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
Map<Integer, Integer> visited = new HashMap<>();
for (final int v : graph.keySet()) {
if (!visited.containsKey(v)) {
if (dfsHasCycle(v, graph, visited, v)) {
return true;
}
}
}
return false;
}
private static boolean dfsHasCycle(final int v, final Map<Integer, Set<Integer>> graph,
final Map<Integer, Integer> visited, final int parent) {
final isVisited = visited.getOrDefault(v, 0);
if (isVisited == 1) return false;
if (isVisited == -1) return true;
visited.put(v, -1);
for (final int adj : graph.keySet()) {
if (adj != parent) { // Only difference with Directed graph version.
if (dfsHasCycle(adj, graph, visited, v)) {
return true;
}
}
}
visited.put(v, 1);
return false;
}

#3.1.2 BFS to Detect Cycle

BFS Cycle Detection For Directed Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static boolean hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
// 不再像DFS那样需要-1, 0, 1三种状态. BFS只需要0和1两种,所以用一个HashSet就够了.
final Set<Integer> visited = new HashSet<>();
final Queue<Integer> queue = new LinkedList<>();
for (final int v : graph.keySet()) {
queue.offer(v);
while (!queue.isEmpty()) {
final int curr = queue.poll();
if (visited.contains(curr)) return true;
visited.add(curr);
for (final int adj : graph.get(curr)) {
if (visited.contains(curr)) return true;
queue.offer(adj);
}
}
}
return false;
}

BFS Cycle Detection For Undirected Graph

Solution: 记录访问情况

需要有个parent的HashMap来记录每个结点是经过谁过来的.

parent只需要是一个link, Map<Integer, Integer>即可, 不需要是一个Map<Integer, Set<Integer>>. 因为即使有多个结点v1, v2指向w, 因为是undirected graph的关系, 完全可以看做是v1指向w, w再指向v2.

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
public static boolean hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
// 不再像DFS那样需要-1, 0, 1三种状态. BFS只需要0和1两种,所以用一个HashSet就够了.
final Set<Integer> visited = new HashSet<>();
final Queue<Integer> queue = new LinkedList<>();
final Map<Integer, Integer> parent = new HashMap<>();
for (final int v : graph.keySet()) {
queue.offer(v);
while (!queue.isEmpty()) {
final int curr = queue.poll();
if (visited.contains(curr)) return true;
visited.add(curr);
for (final int adj : graph.get(curr)) {
if (parent.get(curr) == adj) continue;
if (visited.contains(curr)) return true;
// Update parent link
parent.put(adj, curr);
queue.offer(adj);
}
}
}
return false;
}

#3.1.3 Topological Sort to Detect Cycle

判断是否有cycle的思路是利用topological sort. 如果topological sort走完之后还有vertices的indegree大于0的话. 就说明是有环.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
public static boolean hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
// Compute the indegree of all vertices
final Map<Integer, Integer> indgree = new HashMap<>();
for (final int v : graph.keySet()) {
indegree.putIfAbsent(v, 0);
for (final int adj : graph.get(v)) {
indegree.putIfAbsent(adj, 0);
indegree.put(adj, indegree.get(adj) + 1);
}
}
// Enqueue every vertex with 0 indegree
final Queue<Integer> queue = new LinkedList<>();
for (final int v : indegree) {
if (indegree.get(v) == 0) {
queue.offer(v);
}
}
// Topological sort
while (!queue.isEmpyt()) {
final int v = queue.poll();
for (final int adj : graph.get(v)) {
indegree.put(adj, indegree.get(adj) - 1);
if (indegree.get(adj) == 0) {
queue.offer(adj);
}
}
}
// Find out if any vertex still with non-zero indegree
for (final int v : indegree.keySet()) {
if (indegree.get(v) != 0) {
return true;
}
}
return false;
}

#3.2 How to detect negative cycle?

  1. Bellman-Ford
  2. Floyd-Warshall

See more details in Shortest Path Section

01/03/2020
Graph - 2. Topological Sort

#2. Topological Sort

Topological sort的概念只针对DAG! 有环的有向图也不行!

#2.1 DFS Topological Sort

Java

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
public static List<Integer> topologicalSortDFS(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final List<Integer> res = new LinkedList<>();
final Map<Integer, Integer> visited = new HashMap<>();
for (final int v : graph.keySet()) {
if (!visited.contains(v)) {
dfs(v, graph, visited, res);
}
}
return res;
}
private static void dfs(final int v, final Map<Integer, Set<Integer>> graph, final Map<Integer, Integer> visited, final List<Integer> res) {
visited.putIfAbsent(v, 0);
final int status = visited.get(v);
if (status == 1) return;
if (status == -1) throw IllegalArgumentException("The given graph is not a DAG");
visited.put(v, -1);
for (final int adj : graph.get(v)) {
dfs(adj, graph, visited, res);
}
visited.put(v, 1);
res.add(0, v);
}

Python

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
31
32
33
34
35
36
37
38
39
40
41
42
import collections
# Topological sort is only for DAG!
# DFS topological sort
def topo_sort_dfs(graph):
"""
:graph Dict:
:rtype: List
"""
res = []
if not graph:
return res
visited = collections.defaultdict(int)
for v in graph:
if visited[v] == 0:
dfs(graph, v, visited, res)
return res[::-1]
def dfs(graph, v, visited, res):
"""
:graph Dict:
:v int:
:visited set:
:res List:
"""
if v not in graph:
raise Exception("invalid vertex")
elif visited[v] == 1:
return
elif visited[v] == -1:
raise Exception("the graph has cycle")
visited[v] = -1
for adj in graph[v]:
if visited[adj] == 0:
dfs(graph, adj, visited, res)
visited[v] = 1
res.append(v)

#2.2 BFS Topological Sort

Java

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
31
32
33
34
public static List<Integer> topologicalSortBFS(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Map<Integer, Integer> indegrees = new HashMap<>();
for (final int v : graph.keySet()) {
indegrees.putIfAbsent(v, 0);
for (final int adj : graph.get(v)) {
indegrees.putIfAbsent(adj, 0);
indegrees.put(adj, indegrees.get(adj) + 1);
}
}
final Queue<Integer> queue = new LinkedList<>();
for (final int v : graph.keySet()) {
if (indegrees.get(v) == 0) {
queue.offer(v);
}
}
while (!queue.isEmpty()) {
final int front = queue.poll();
res.add(front);
for (final int adj : graph.keySet()) {
indegrees.put(adj, indegreees.get(adj) - 1);
if (indegrees.get(adj) == 0) {
queue.offer(adj);
}
}
}
return res;
}

Python

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
31
32
33
34
35
36
37
38
39
40
41
42
import collections
# Topological sort is only for DAG!
def topo_sort_bfs(graph):
"""
:graph Dict:
:rtype: List
"""
res = []
if not graph:
return res
indegree = collections.defaultdict(int)
for v in graph:
for adj in graph[v]:
indegree[adj] += 1
visited = set()
q = collections.deque()
for v in graph:
if indegree[v] == 0:
visited.add(v)
q.append(v)
while q:
size = len(q)
for _ in range(size):
v = q.popleft()
res.append(v)
for adj in graph[v]:
indegree[adj] -= 1
if indegree[adj] == 0 and adj not in visited:
visited.add(adj)
q.append(adj)
for v in indegree:
if indegree[v] != 0:
raise Exception("the graph has cycle")
return res[::-1]

01/03/2020
Graph - 1. Search

#1. Search

  • Search Algorithms work for both Direceted and Undirected graph.

#1.1 Depth First Search (DFS)

Java

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
public class DFS {
public static void traversal(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
if (!visited.contains((v))) {
dfs(v, graph, visited, res);
}
}
}
private static void dfs(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final List<Integer> res) {
visited.add(v);
res.add(v);
for (final int adj : graph.get(v)) {
if (!visited.contains(adj)) {
dfs(adj, graph, visited, res);
}
}
}
}

Python

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
31
# Directed & Undirected Graph both work
def search(graph):
"""
:graph Dict:
:rtype: List
"""
res = []
if not graph:
return res
v = next(iter(graph))
visited = set()
dfs(graph, v, visited, res)
return res
def dfs(graph, v, visited, res):
"""
:graph Dict:
:v int:
:visited Set:
:res List:
"""
if not graph or not graph[v]:
return
visited.add(v)
res.append(v)
for adj in graph[v]:
if adj not in visited:
dfs(graph, adj, visited, res)

#1.2 Breadth First Search (BFS)

Java

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
31
32
public class BFS {
public static List<Integer> traversal(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Queue<Integer> queue = new LinkedList<>();
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
if (!visited.contains(v)) {
queue.offer(v);
bfs(graph, queue, visited, res);
}
}
return res;
}
private static void bfs(final Map<Integer, Set<Integer>> graph, final Queue<Integer> queue,
final Set<Integer> visited, final List<Integer> res) {
while (!queue.isEmpty()) {
final int v = queue.poll();
res.add(v);
visited.add(v);
for (final int adj : graph.get(v)) {
if (!visited.contains(adj)) {
queue.offer(adj);
}
}
}
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import collections
# Directed & Undirected graph both work
def search(graph):
res = []
if not graph:
return res
visited = set()
queue = collections.deque()
v = next(iter(graph))
queue.append(v)
visited.add(v)
while queue:
size = len(queue)
for _ in range(size):
curr = queue.popleft()
res.append(curr)
for adj in graph[curr]:
if adj not in visited:
queue.append(adj)
return res

01/03/2020
Graph - 0. Introduction

#Graph - 0. Introduction

#Questions to Ask

Before any graph problems, ask yourself the following 4 questions:

  1. Directed or Undirected?
  2. Weighted or Unweighted?
  3. Sparse graph or Dense graph?
  4. Adjacency Matrix or Adjacency List?

#Graph Theory Problems with Cheat Sheet

  1. Search
  2. Topological Sort
  3. Cycle Detection
  4. Shortest Path Problem
    • Single Source Shortest Path Problem (SSSP)
      • Topological Sort (DAG)
      • Dijkstra (without negative edge)
        • Lazy Implementation
        • Eager Implementation with IndexHeap
      • Bellman-Ford (without negative cycle)
    • All Sources Shortest Path Problem
      • Floyd-Warshall
    • Longest Path Problem
  5. Connectivity
    • Union-Find
    • Strongly Connected Component
      • Tarjan’s Algorithm
      • Kosaraju’s Algorithm
    • Bridges (Cut Edges)
    • Articulation Points (Cut Vertex)
  6. Eulerian Path / Eulerian Cycle
  7. Hamiltonian Path / Hamiltonian Cycle
  8. Minimum Spanning Tree
    • Prim’s Algorithm
      • Lazy implementation
      • Eager implementation with IndexHeap
    • Kruskal’s Algorithm
  9. Traveling Salesman Problem
  10. Network Flow Problem
    • Ford-Fulkerson
    • Edmonds-Karp
    • Capacity Scaling
    • Dinic Algorithm
  11. Bipartite Problem
    • Maximum Cardinality Bipartite Matching (MCBM)

#Reference

Apply to all Graph related posts

© 2020 ReeeStart with help from Hexo and Twitter Bootstrap. Theme by Freemind.