leetcode演算法之圖
今天來盤一盤 **圖 ** 這類題目
這類題目對我來說也是比較難的，比較難搞。
有向無環圖的拓撲排序（BFS， DFS）
利用並查集處理連通域問題
使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1
圖
BFS與DFS
- 785 判斷二分圖 (Medium)
- 207 課程表 (Medium)
- 210 課程表 II (Medium)
並查集
並查集是一種樹型的數據結構，主要用於處理連通域的問題，用於處理一些不交集的合併及查詢問題。主要的操作有如下的步驟：
Find：確定元素屬於哪一個子集。它可以被用來確定兩個元素是否屬於同一子集。
Union：將兩個子集合併成同一個集合。
- 684 冗餘連接 (Medium)
BFS與DFS
785 判斷二分圖 (Medium)
使用染色法，0代表一種顏色，1代表另外一種顏色， -1表示未染色，相鄰的元素不能染成同樣的顏色。
- DFS
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> colors(n, -1);
for (int i = 0; i< n; i++){
if (colors[i] == -1){
if (!dfs(graph, colors, i, 0))
return false;
}
}
return true;
}
bool dfs(vector<vector<int>>& graph, vector<int>& colors, int index, int c){
colors[index] = c;
for (int i = 0; i < graph[index].size(); i++){
int node = graph[index][i];
if (colors[node] != -1){
if (colors[node] == c) return false;
else continue;
}
else
if ( ! dfs(graph, colors, node, 1-c))
return false;
}
return true;
}
};
- BFS
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> colors(n, -1);
queue<pair<int, int>> q;
for (int i = 0; i<n; i++){
if ( colors[i] != -1) continue;
q.push(make_pair(i, 0));
while (! q.empty()){
auto nodeLevel = q.front();
int node = nodeLevel.first;
int level = nodeLevel.second;
q.pop();
if (level % 2 == 0){
if (colors[node] == 1)
return false;
colors[node] = 0;
}
else{
if (colors[node] == 0)
return false;
colors[node] = 1;
}
for (auto node1 : graph[node]){
if (colors[node1] == -1)
q.push(make_pair(node1, level+1));
}
}
}
return true;
}
};
207 課程表 (Medium)
- DFS
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 不能有環， dfs
vector<int> visited(numCourses, -1); // -1表示沒有訪問過， 0表示被其他節點訪問過，1表示被本節點訪問過
vector<vector<int>> edges(numCourses, vector<int>());
// 構建鄰接表
for (int i = 0; i < prerequisites.size(); i++){
int start = prerequisites[i][1];
int end = prerequisites[i][0];
// cout<<start<<" "<<end<<endl;
edges[start].push_back(end);
}
for( int i = 0; i < numCourses; i++){
if (visited[i] != -1) continue;
if (! dfs(edges, visited, i))
return false;
}
return true;
}
bool dfs(vector<vector<int>>& edges, vector<int>& visited,int index){
if (visited[index] == 1) return false;
if (visited[index] == 0) return true;
visited[index] = 1;
for (auto node : edges[index]){
if (! dfs(edges, visited, node))
return false;
}
visited[index] = 0;
return true;
}
};
- BFS（入度表）
/*
1. 轉換為鄰接表並生成入度表
2. 將入度為0的節點入隊。
3. 遍歷整個隊列，如果隊列不為空，將隊首出列，並將鄰接節點的入度減一，將入度為0的節點重新入度。
*/
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 不能有環， dfs
vector<int> indegrees(numCourses, 0);
vector<vector<int>> edges(numCourses, vector<int>());
// 構建鄰接表與入度表
for (int i = 0; i < prerequisites.size(); i++){
int start = prerequisites[i][1];
int end = prerequisites[i][0];
edges[start].push_back(end);
indegrees[end]++;
}
queue<int> q;
// 將入度為0的節點入隊
for (int i = 0; i < numCourses; i++){
if (indegrees[i] == 0)
q.push(i);
}
while (!q.empty()){
int node = q.front();
q.pop();
// 將鄰接的節點入度數減一，並將入度為0的節點入隊
for (auto j : edges[node]){
indegrees[j]--;
if (indegrees[j] == 0)
q.push(j);
}
}
// 如果有的節點入度數不為0，那麼說明存在環
for (auto i: indegrees){
if (i != 0) return false;
}
return true;
}
};
210 課程表 II (Medium)
- DFS
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edges(numCourses, vector<int>());
for (int i= 0; i < prerequisites.size(); i++){
int start = prerequisites[i][1];
int end = prerequisites[i][0];
edges[start].push_back(end);
}
// for(auto p: edges){
// for (auto v:p)
// cout<<v<<" ";
// cout<<endl;
// }
vector<int> visited(numCourses, -1); // -1表示沒有訪問過， 0表示被其他節點訪問過，1表示被本節點訪問過
vector<int> res;
for( int i = 0; i < numCourses; i++){
if (visited[i] != -1) continue;
if (! dfs(edges, visited, res, i))
return {};
}
reverse(res.begin(), res.end());
return res;
}
bool dfs(vector<vector<int>>& edges, vector<int>& visited, vector<int>& res, int index){
if (visited[index] == 1) return false;
if (visited[index] == 0) return true;
visited[index] = 1;
for (auto node : edges[index]){
if (!dfs(edges, visited, res, node))
return false;
}
res.push_back(index);
visited[index] = 0;
return true;
}
};
- BFS
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edges(numCourses, vector<int>());
vector<int> indegress(numCourses, 0);
// 構建鄰接表，入度表
for (int i= 0; i < prerequisites.size(); i++){
int start = prerequisites[i][1];
int end = prerequisites[i][0];
edges[start].push_back(end);
indegress[end]++;
}
queue<int> q;
vector<int> res;
// 將入度為0的節點入隊
for (int i = 0; i < numCourses; i++){
if (indegress[i] == 0)
q.push(i);
}
// 遍歷隊列
while (!q.empty()){
int node = q.front();
res.push_back(node);
q.pop();
// 將鄰接節點的入度數減一，並將入度為0的節點入隊。
for (auto i : edges[node]){
indegress[i]--;
if (indegress[i] == 0)
q.push(i);
}
}
// 如果存在入度不為0的節點，說明存在一個環
for (auto i: indegress){
if ( i != 0)
return {};
}
return res;
}
};
並查集
684 冗餘連接 (Medium)
經典的並查集的套路程式碼。
class Solution {
public:
int find(vector<int>&parent, int index){
// 查找一個給定節點的父親節點。遞歸的操作。
if (parent[index] != index)
parent[index] = find(parent, parent[index]);
return parent[index];
}
void Union(vector<int>& parent, int index1, int index2){
// index2的父親節點轉換為index1與index2共同的父親節點。
parent[find(parent,index1)] = find(parent,index2);
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> parent(n+1, 0);
// 初始化的情況下，每個節點的父親節點都是自身
for (int i = 1; i< n+1; i++){
parent[i] = i;
}
for (auto edge: edges){
int node1 = edge[0], node2 = edge[1];
// 對於兩個節點，如果其父親節點不一樣就融合這兩個節點
if (find(parent, node1) != find(parent, node2))
Union(parent, node1, node2);
else
return edge;
}
return {};
}
};
更多分類刷題資料
-
微信公眾號： 小哲AI
-
GitHub地址： //github.com/lxztju/leetcode-algorithm
-
csdn部落格： //blog.csdn.net/lxztju
-
AI研習社專欄：//www.yanxishe.com/column/109
