拓扑排序和二分图

1 拓扑排序(有向图)

课程表Ⅱ

1.1 BFS(易理解)

创建一个表示入度的数组,初始将入度为0的节点加入队列,后续依次弹出队列,每次弹出node,减小node指向的节点的入度,入度为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
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
vector<int> inDegree(numCourses);
for (auto& e : prerequisites) {
g[e[1]].push_back(e[0]);
++inDegree[e[0]];
}
queue<int> q;
vector<int> ret;
for (int i = 0; i < numCourses; ++i)
if (inDegree[i] == 0) q.push(i);
while (!q.empty()) {
int node = q.front(); q.pop();
ret.push_back(node);
for (auto e : g[node]) {
--inDegree[e];
if (inDegree[e] == 0)
q.push(e);
}
}
return ret.size() == numCourses ? ret : vector<int>();
}
};

1.2 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
// visited用来减少计算量
// used用来判断成环
class Solution {
public:
vector<bool> visited; // 不重置
vector<bool> used; // 每次递归,回溯重置
vector<int> postOrder;
// 判断有环,顺便记录下后序遍历的节点
bool isCircle(vector<vector<int>>& g, int node) {
if (used[node]) return true; // 有环
if (visited[node]) return false; // 优化速度(防止同一个连通集重复计算)
visited[node] = true;
used[node] = true;
for (auto e : g[node])
if (isCircle(g, e)) return true; // 有环直接返回
postOrder.push_back(node); // 后序遍历位置(递归后面)
used[node] = false;
return false;
}

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
for (auto& e : prerequisites) g[e[1]].push_back(e[0]);
visited.resize(numCourses, false);
used.resize(numCourses, false);
for (int i = 0; i < numCourses; ++i)
if (isCircle(g, i)) return vector<int>(); // 有环直接返回
reverse(postOrder.begin(), postOrder.end());
return postOrder;
}
};

2 二分图(无向图?)

图的节点只有两种颜色:红和蓝,相同颜色不能相邻,判断是否是二分图,可有两种方法:DFS和BFS

可能的二分法

2.1 DFS

注意visited不要重置

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
class Solution {
public:
vector<bool> visited;
vector<bool> color;
bool core(vector<vector<int>>& g, int node) {
visited[node] = true;
for (auto e : g[node]) {
if (!visited[e]) {
color[e] = !color[node];
if (core(g, e) == false)
return false;
}
else {
if (color[e] == color[node])
return false;
}
}
return true;
}

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> g(n + 1);
for (auto& e : dislikes) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
visited.resize(n + 1, false);
color.resize(n + 1, false);
for (int i = 1; i <= n; ++i) {
if (visited[i]) continue;
if (core(g, i) == false) return false;
}
return true;
}
};

2.2 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
class Solution {
public:
vector<bool> visited;
vector<bool> color;
bool core(vector<vector<int>>& g, int node) {
queue<int> q;
q.push(node);
while (!q.empty()) {
int cur = q.front(); q.pop();
visited[cur] = true;
for (auto e : g[cur]) {
if (!visited[e]) {
color[e] = !color[cur];
q.push(e);
}
else {
if (color[e] == color[cur])
return false;
}
}
}
return true;
}

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> g(n + 1);
for (auto& e : dislikes) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
visited.resize(n + 1, false);
color.resize(n + 1, false);
for (int i = 1; i <= n; ++i) {
if (visited[i]) continue;
if (core(g, i) == false) return false;
}
return true;
}
};

参考

  1. 二分图判定算法
  2. 环检测及拓扑排序算法