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
|
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; } };
|
参考
- 二分图判定算法
- 环检测及拓扑排序算法