資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 程式中的 DFS 檢查給定圖是否為二分圖
假設我們有一個連通圖；我們需要檢查該圖是否為二分圖。如果可以透過使用兩種顏色進行圖著色，使得一組節點用同一種顏色著色。
因此，如果輸入類似於
則輸出將為 True
為了解決這個問題，我們將遵循以下步驟 -
- 定義一個函式 insert_edge()，它將接收一個邊陣列 adj、u、v，
- 將 v 插入到 adj[u] 的末尾
- 將 u 插入到 adj[v] 的末尾
- 從主方法執行以下操作，
- 對於 adj[v] 中的每個 u，執行
- 如果 visited[u] 為 false，則 -
- visited[u] := true
- color[u] := color[v] 的反值
- 如果 !is_bipartite_graph(adj, u, visited, color)，則 -
- 返回 false
- 否則，當 color[u] 等於 color[v] 時，則 -
- 返回 false
- 如果 visited[u] 為 false，則 -
- 返回 true
示例（C++）
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void insert_edge(vector<int> adj[], int u, int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
for (int u : adj[v]) {
if (visited[u] == false) {
visited[u] = true;
color[u] = !color[v];
if (!is_bipartite_graph(adj, u, visited, color))
return false;
}
else if (color[u] == color[v])
return false;
}
return true;
}
int main() {
int N = 6;
vector<int> adj_list[N + 1];
vector<bool> visited(N + 1);
vector<int> color(N + 1);
insert_edge(adj_list, 1, 2);
insert_edge(adj_list, 2, 3);
insert_edge(adj_list, 3, 4);
insert_edge(adj_list, 4, 5);
insert_edge(adj_list, 5, 6);
insert_edge(adj_list, 6, 1);
visited[1] = true;
color[1] = 0;
cout << (is_bipartite_graph(adj_list, 1, visited, color));
}輸入
insert_edge(adj_list, 1, 2); insert_edge(adj_list, 2, 3); insert_edge(adj_list, 3, 4); insert_edge(adj_list, 4, 5); insert_edge(adj_list, 5, 6); insert_edge(adj_list, 6, 1);
輸出
1
更新於: 2020-08-27
580 次檢視
廣告