面试中常见的图论问题

Posted on Edited on

面试中常见的图论问题

[TOC]

二分图问题：

LeetCode 785. Is Graph Bipartite?

这是一个直白的二分图问题：二分图问题，就是可否将图的所有节点分成两个集合，有连边两个点不在一个集合。

将二分图问题可以看成二染色问题，即使用两种颜色对图进行染色，相连的两个点，颜色不能相同。

解决办法：遍历染色

DFS+染色：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isBipartite(int[][] graph) {
        // 染色状态; 0-未染色，1-蓝色，-1-红色
        int[] colors = new int[graph.length];
        for (int i = 0; i < colors.length; i++) {
            if(colors[i]==0 && !dfs(i, 1, colors, graph)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int v, int color, int[] colors, int[][] graph) {
        colors[v]=color;
        for(int adjV:graph[v]){
            if(colors[adjV]==color) return false;
            if(colors[adjV]==0 && !dfs(adjV, -color, colors, graph)){
                return false;
            }
        }
        return true;
    }
}

也可以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
public class Solution {
    public boolean isBipartite(int[][] graph) {
        // 染色状态; 0-未染色，1-蓝色，-1-红色
        int[] colors = new int[graph.length];
        for (int i = 0; i < colors.length; i++) {
            if(colors[i]==0 && graph[i].length>0){
                colors[i] = 1;
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                while(!q.isEmpty()){
                    int curr = q.poll();
                    for(int adjV:graph[curr]){
                        if(colors[adjV]==0){
                            colors[adjV]=-colors[curr];
                            q.offer(adjV);
                        }
                        else if(colors[adjV]==colors[curr]) return false;
                    }
                }
            }
        }
        return true;
    }
}

886. Possible Bipartition

这道题加了点丰富的背景，但是很容易看出来还是一个二分图问题。据说这道题是今年字节跳动的笔试题

多了一点构建图。

DFS+染色：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        // 构建图
        List<Integer>[] graph = new ArrayList[N+1];
        for (int i = 1; i < N+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] l : dislikes) {
            graph[l[0]].add(l[1]);
            graph[l[1]].add(l[0]);
        }
        // 状态数组
        int[] colors = new int[N+1];
        for (int i = 1; i < N+1; i++) {
            if(colors[i]==0 && !dfs(i, graph, colors, 1)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int pid, List<Integer>[] graph, int[] colors, int color){
        colors[pid] = color;
        for (int other_pid : graph[pid]) {
            if(colors[other_pid]==color) return false;
            if(colors[other_pid]==0 && !dfs(other_pid, graph, colors, -color)){
                return false;
            }
        }
        return true;
    }
}

拓扑排序问题

详细介绍见我这篇博客：BFS DFS 判断DAG(有向无环图)

207. Course Schedule

这道题原先用Python写过。BFS+入度，和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
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表建图
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        //记录每个节点的入度
        int[] indegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new ArrayList<>();
        }
        for(int[] prq:prerequisites){
            // 需要先修的课程指向后修的课程
            graph[prq[1]].add(prq[0]);
            // 后修的课程入度+1；
            indegree[prq[0]]++;
        }
        // BFS 拓扑排序
        Queue<Integer> q = new LinkedList<>();
        int cnt=0;
        for (int i = 0; i < numCourses; i++) {
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int curr = q.poll();
            cnt++;
            for(int adjV:graph[curr]){
                indegree[adjV]--;
                if(indegree[adjV]==0) q.offer(adjV);
            }        
        }
        return cnt==numCourses;
    }
}
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 class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表建图
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        // 状态数组
        int[] mark = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new ArrayList<>();
        }
        for(int[] prq:prerequisites){
            // 需要先修的课程指向后修的课程
            graph[prq[1]].add(prq[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if(!dfs(i, mark, graph)) return false;
        }
        return true;
    }
    private boolean dfs(int v, int[] mark, ArrayList<Integer>[] graph) {
        mark[v]=1;
        for(int adjV:graph[v]){
            if(mark[adjV]==0){
                if(!dfs(adjV, mark, graph)) 
                    return false;
            }else if(mark[adjV]==1)
                return false;
        }
        mark[v]=2;
        return true;
    }
}

210. Course Schedule II

这道拓扑排序，唯一的不同就是讲排序结果输出，用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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        // 建图，
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        int cnt = 0;
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new ArrayList<>();
        }
        for(int[] p: prerequisites){
            graph[p[1]].add(p[0]);
            indegree[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<numCourses; i++){
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int cur = q.poll();
            res[cnt++] = cur;
            for(int adjV: graph[cur]){
                indegree[adjV]--;
                if(indegree[adjV]==0)
                    q.offer(adjV);
            }
        }
        return cnt==numCourses?res:new int[0];
    }
}

并查集检查冗余

并查集详细介绍：并查集原理及联通分量个数问题

注：并查集上的点至少有两个属性：（data, parent),其中指向parent，这种映射关系，完全可以用数组的index-value代替，故我们可以有两个数组 parent，rank(用于UF的优化，路径压缩等等),而data作为index存在，映射关系则用数组实现。

684. Redundant Connection

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
class Solution {
    class UF{
        private int[] parent;
        private int[] rank;
        public UF(int n){
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public int find(int p){
            // 查找集合根节点
            int r = p;
            while(r!=parent[r]){
                r = parent[r];
            }
            // 路径压缩
            int k = p;
            while(k!=r){
                int par = parent[k];
                parent[k] = r;
                k = par;
            }
            return r;
        }
        public void union(int p, int q) {
            int rootp = find(p);
            int rootq = find(q);
            if (rootp==rootq) return;
            if(rank[rootp]>=rank[rootq]){
                if(rank[rootp]==rank[rootq]){
                    rank[rootp]+=1;
                }
                parent[rootq]=rootp;
            }else{
                parent[rootp]=rootq;
            }
        }
        public boolean connect(int p, int q){
            return find(p)==find(q);
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        UF uf = new UF(edges.length+1);
        for(int[] edg:edges){
            int p=edg[0],q=edg[1];
            if(uf.connect(p, q)){
                return edg;
            }
            uf.union(p, q);
        }
        return new int[]{-1, -1};
    }
}

547. Friend Circles

单纯的并查集问题

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
class Solution{
    class UnionFind{
        private int numSets = 0;
        private int[] parent, rank;
        public UnionFind(int n){
            numSets = n;
            parent = new int[n];
            rank = new int[n];
            for(int i=0;i<n; i++){
                parent[i]=i;
            }
        }
        public int find(int p){
            int r = p;
            while(r!=parent[r]){
                r = parent[r];
            }
            int k = p;
            while(k!=r){
                int j = parent[k];
                parent[k]=r;
                k = j;
            }
            return r;
        }
        public void union(int p, int q){
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP==rootQ) return;
            if (rank[rootP]>=rank[rootQ]){
                if (rank[rootP]==rank[rootQ]){
                    rank[rootP]+=1;
                }
                parent[rootQ]=rootP;
            }else{
                parent[rootP]=rootQ;
            }
            numSets-=1;
        }
        public int getNumSets() {
            return numSets;
        }
    }
    public int findCircleNum(int[][] M) {
        UnionFind uf = new UnionFind(M.length);
        for(int i=0;i<M.length;i++){
            for(int j=i+1; j<M.length;j++){
                if(M[i][j]==1) uf.union(i, j);
            }
        }
        return uf.getNumSets();
    }
}

图论还有最短路问题，网络流问题（这个面试应该不会问）等等。以后遇到了接着补充