Graph 总结一下Graph的所有算法
Questions to Ask
Before any graph problems, ask yourself the following 4 questions:
Directed or Undirected?
Weighted or Unweighted?
Sparse graph or Dense graph?
Adjacency Matrix or Adjacency List?
Graph Theory Problems with Cheat Sheet
Search
Topological Sort
Cycle Detection
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
Longest Path Problem
Connectivity
Union-Find
Strongly Connected Component
Tarjan’s Algorithm
Kosaraju’s Algorithm
Bridges (Cut Edges)
Articulation Points (Cut Vertex)
Eulerian Path / Eulerian Cycle
Hamiltonian Path / Hamiltonian Cycle
Minimum Spanning Tree
Prim’s Algorithm
Lazy implementation
Eager implementation with IndexHeap
Kruskal’s Algorithm
Traveling Salesman Problem
Network Flow Problem
Ford-Fulkerson
Edmonds-Karp
Capacity Scaling
Dinic Algorithm
Bipartite Problem
Maximum Cardinality Bipartite Matching (MCBM)
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
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
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
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
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
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 ]
3. Cycle Detection 3.1 How to detect cycle?
DFS
BFS
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) {
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();
}
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();
}
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 ;
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();
}
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 );
}
}
final Queue<Integer> queue = new LinkedList<>();
for (final int v : indegree) {
if (indegree.get(v) == 0 ) {
queue.offer(v);
}
}
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);
}
}
}
for (final int v : indegree.keySet()) {
if (indegree.get(v) != 0 ) {
return true ;
}
}
return false ;
}
3.2 How to detect negative cycle?
Bellman-Ford
Floyd-Warshall
See more details in Shortest Path Section
4. Union-Find TODO
Java
Python
5. Strongly Connected Component
What is connected graph ?
A graph is connected
if there is a path between each pair of vertices.
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:
Topological sort on reversed G!
Run DFS based on the order from step 1
Proof of Kosaraju’s Algorithm:
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而不是两个.
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
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)
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
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.
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:
there is a path from v to w
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)
Algorithms:
Maintains a stack, node is added to the stack when they’re visited the first time
Nodes are removed from the stack when a complete SCC is found
If (v, w) is an edge in the graph, to update lowlink value of v, w must be on the stack.
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
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])
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))
6. Bridges (Cut Edges)
What is Bridge?
Bridges are the edges in a graph, whose removal increases the number of connected components
Why do we want find bridges?
Bridges are often hint at weak points, bottle necks or vulnerabilities in a graph
How to find bridges?
If (v, w) is an edge in the graph, the edge is a bridge iff id(v) < lowlink(w)
Python 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
42
43
44
45
46
47
48
49
50
51
def find_bridges (graph) :
"""
:type graph: Dict[int, Set[int]]
:rtype: List[tuple(int, int)]
"""
if not graph:
raise Exception("invalid graph" )
nodes = set()
lowlink = {}
visited = set()
for v in graph.keys():
for w in graph[v]:
nodes.add(v)
nodes.add(w)
lowlink
bridges = []
n = len(nodes)
for i in range(n):
if i not in visited:
dfs(i, -1 , graph, lowlink, visited, bridges)
return bridges
def dfs (v, parent, graph, lowlink, visited, bridges) :
"""
:type v: int
:type parent: int
:type graph: Dict[int, Set[int]]
:type lowlink: Dict[int]
:type bridges: List[tuple(int, 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, bridges)
lowlink[v] = min(lowlink[v], lowlink[adj])
else :
lowlink[v] = min(lowlink[v], adj)
if v < lowlink[adj]:
bridges.add((v, adj))
7. Articulation Points (Cut Vertex)
What is Articulation Point?
Articulation points are the nodes in a graph, whose removal increases the number of connected components
How to find articulation points?
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.
If id(e.from) == lowlink(e.to), that means there is a cycle
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.
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
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]:
candidates.add(v)
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 :
Every vertex with non-zero degree belong to a single strongly connected component
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<>();
final int src = computeIndegreeAndGetSource(graph);
if (src == -1 ) {
for (final int v : graph.keySet()) {
dfs(v, graph, res);
break ;
}
} else {
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
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" )
indegree, outdegree = collections.defaultdict(lambda : 0 ), collections.defaultdict(lambda : 0 )
nodes = set()
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)
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
path = []
dfs(start, graph, path)
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 :
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 :
Every vertex with non-zero degree belong to a single connected component
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 :
Every vertex with non-zero degree belong to a single strongly connected component
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 );
}
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()) {
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 ;
}
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.
Sort all edges by weight
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);
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
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
Start with vertex 0 and greedily grow tree.
Add to tree the minimum weight edge with exactly one endpoint in tree
.
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可以有多种返回方式, 比如:
可以返回一个Queue
也可以返回一个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<>();
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 需要利用IndexHeap
来update 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<>();
final Map<Integer, Edge> vertexToMinWeightEdge = new HashMap<>();
for (final int v : graph.keySet()) {
minIndexHeap.decreaseKey(v, 0 );
break ;
}
while (!minIndexHeap.isEmpty()) {
final int v = minIndexHeap.poll();
visited.add(v);
if (vertexToMinWeightEdge.containsKey(v)) {
mst.offer(vertexToMinWeightEdge.get(v));
}
for (final int adj : graph.get(v)) {
if (visited.contains(adj)) continue ;
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;
}
}
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
Topological Sort
Relaxing based on topological order
Performance
Proof 因为是Acyclic, 而且是topological order, 所以each edge is relaxed exactly once.
distTo[w]不可能increase, 因为我们只有当distTo[v] + weight(v, w) < dist[w]的时候才更新dist[w]
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
import collections
import toposort
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
Negate all weights. (This solution allows negative weights)
Run AcyclicShortestPath Algorithm.
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:
Create an edge-weighted DAG.
Two virtual vertices representing:
Source: “Before everything start”
Destination: “After everything is done”
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
Each constraint is an edge.
The longest path of this problem is also called a “critical path”
证明:
Job和Job之间的先后顺序只会产生一条edge, 但不会有weight. 也就是weight是0.
有weight的都是每一个Job的Duration.
所以比如下图这种情况：
要保证每个Job都完成的话，只能取longest path而不是shortest path.
11.3 Dijkstra Algorithm Only work for non-negative weighed directed graph (可以有环)
.
Dijkstra有两种implementation:
Lazy Implementation
not good for dense graph
lots of duplicated tuples
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();
}
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
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 = []
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);
}
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
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
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 = [[None for j in range(n)] for i in range(n)]
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
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]
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
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
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 = [[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 ):
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
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 ]
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
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
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)
graph.add_edge(graph.s, 0 , 10 )
graph.add_edge(graph.s, 1 , 5 )
graph.add_edge(graph.s, 2 , 10 )
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 )
graph.add_edge(6 , graph.t, 15 )
graph.add_edge(8 , graph.t, 10 )
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
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 = {}
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)
graph.add_edge(graph.s, 0 , 10 )
graph.add_edge(graph.s, 1 , 5 )
graph.add_edge(graph.s, 2 , 10 )
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 )
graph.add_edge(6 , graph.t, 15 )
graph.add_edge(8 , graph.t, 10 )
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.
Find the largest capacity in the flow graph, call it U
Find the delta, which is the largest 2^x that’s less or equal to U
Find augmenting path with capacity > than delta
If no more augmenting path has capacity greater than delta, then delta /= 2
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. 太难了.
14 Bipartite Problem 14.1 Decide whether a given undirected graph is a bipartite graph Algorithm
BFS
Java IsBipartite
TODO
Python IsBipartite
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
Reference