Graph类型题总结
Graph类型题总结
Graph类型题常见的有1. Topological sorting 2. connected component 3. find cycle。同时要注意有向/无向的区别。
Topological sorting
Toplogical sorting一定是针对有向图，常见的做法是
- DFS遍历有向图，最早被遍历完的是需要排到最后面的，时间复杂度O(m+n)
- 设置三种遍历时的状态，VISITED = 1, UNVISITED = 0, VISITING = -1
- DFS每一个node，如果：
- node的状态是UNVISITED: 将状态变为VISITING，然后DFS所有它指向的node，所有指向的node都遍历完以后再变为VISITED，加入到结果中
- node的状态是VISITED: 说明这个node已经加入到结果中了，直接返回
- node的状态是VISITING: 证明图中有环
- 注意: DFS的结果是最后执行的先加入到结果中去
- BFS，通过判断indegree数量，indegree先为零的先拍在前面，时间复杂度O(n+m)
- 新建一个数组，数组中储存所有node的indegree数量
- 遍历数组，找到所有的source node(indegree为0)加入到Queue中
- 依次从Queue中弹出node加入到排序结果中，对于该node指向的nodes，它们的indegree减1，同时判断它们是不是indegree变成0，是的话加入Queue
- 最终如果排序结果的长度与原长度相等，证明所有node都参与了排序，不存在环，否则证明有环
Course Schedule: topological sorting的代表性题目，可以使用DFS和BFS来做，这道题本质上是检测有没有环，所以我们可以看出来，进行Toplogical sort的前提就是是DAG(无环)。
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
48class Solution {
//DFS
private final int UNVISITED = 0;
private final int VISITED = 1;
private final int VISITING = -1;
public boolean canFinish(int numCourses, int[][] prerequisites) {
//construct graph
List<List<Integer>> al = new LinkedList();
for(int i =0;i<=numCourses-1;i++){
al.add(new LinkedList<>());
}
for(int[] pre:prerequisites){
int start = pre[1];
int end = pre[0];
al.get(start).add(end);
}
//do dfs
int[] visited = new int[numCourses];
for(int i =0;i<=numCourses-1;i++){
if(dfs(i, al, visited)==false){
return false;
}
}
return true;
}
private boolean dfs(int node, List<List<Integer>> al, int[] visited){
if(visited[node]==VISITED){
return true;
}
else if(visited[node]==VISITING){
return false;
}
else {
visited[node] = VISITING;
for(int i:al.get(node)){
if(dfs(i, al, visited)==false){
return false;
}
}
visited[node] = VISITED;
return true;
}
}
}Course Schedule II: topological sorting的代表性题目，可以使用DFS和BFS来做
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
51class Solution {
// BFS
public int[] findOrder(int numCourses, int[][] prerequisites) {
// construct graph and indegree count
List<List<Integer>> al = new LinkedList<>();
int[] indegree = new int[numCourses];
for(int i = 0;i<=numCourses-1;i++){
al.add(new LinkedList<>());
}
for(int[] pre:prerequisites){
int start = pre[1];
int end = pre[0];
al.get(start).add(end);
indegree[end]++;
}
Queue<Integer> q = new LinkedList<>();
for(int i =0;i<=numCourses-1 ;i++){
if(indegree[i]==0){
q.offer(i);
}
}
List<Integer> ans = new LinkedList<>();
while(!q.isEmpty()){
int node = q.poll();
ans.add(node);
for(int j:al.get(node)){
indegree[j]--;
if(indegree[j]==0){
q.offer(j);
}
}
}
int[] res = new int[ans.size()];
for(int i =0;i<=ans.size()-1;i++){
res[i] = ans.get(i);
}
if(res.length==numCourses){
return res;
}
else {
return new int[0];
}
}
}Alien Dictionary: 字母的前后顺序关系是一种有向图，又由于题中说可能有多种结果，所以使用topological sort
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
58class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> map = new HashMap<>();//这里必须用set，因为针对相同的edge如果重复计入会导致indegree问题
Map<Character, Integer> indegree = new HashMap<>();
for(String s: words){
for(char c: s.toCharArray()){
indegree.put(c,0);//所有字母都要有indegree
map.put(c, new HashSet<>());//所有字母都要有map
}
}
for(int i =1;i<=words.length-1;i++){
String s1 = words[i-1];
String s2 = words[i];
for(int j = 0;j<=s1.length()-1;j++){
char c1 = s1.charAt(j);
char c2 = s2.charAt(j);
if(c1!=c2){
Set<Character> l = map.getOrDefault(c1, new HashSet<>());
if(!l.contains(c2)){//非常重要，使用set判断是不是已经有了这个edge，以此来保证indegree不会出错
l.add(c2);
map.put(c1,l);
indegree.put(c2, indegree.getOrDefault(c2, 0)+1);
}
break;
}
}
}
String ans = "";
Queue<Character> q = new LinkedList<>();
for(Map.Entry<Character, Integer> e: indegree.entrySet()){
char key = e.getKey();
int value = e.getValue();
if(value==0){
q.offer(key);
}
}
while(!q.isEmpty()){
char c= q.poll();
ans = ans + c;
for(char ch:map.get(c)){
indegree.put(ch, indegree.get(ch)-1);
if(indegree.get(ch)==0){
q.offer(ch);
}
}
}
if(ans.length()!=indegree.size()){
return "";
}
else {
return ans;
}
}
}
Connect Component
找connected components (dfs, bfs, union find)。对于找无向图的connected component还是很简单的，无非是前面提到的三种方法，如果对于有向图要寻找SCC(Strong Connected Component)则比较复杂。
三种方法的时间复杂度都是O(m+n)
200. Number of Islands：可以把矩阵抽象成graph，这道题可以不用设置visited[]数组，直接改变grid的值即可(visited过的变成0)
1 | class Solution { |
1 | // Union Find |
- Number of Connected Components in an Undirected Graph
- Friend Circles
都是无向图
图里是否有环
Bipartite
Bipartite的定义是一个图可以分为两个集合，这个图中所有的edge连接的vertice必须分别在两个集合
解法是分别使用DFS或者BFS为两个集合染色，一个集合红色，一个集合蓝色，如果某个点出现两个色证明不是Bipartite
BFS
1 | /* |
DFS
1 | class Solution { |