資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究檢查無向圖中頂點 X 和 Y 是否在同一連通分量的查詢
圖論涵蓋了連通分量的研究，連通分量是無向圖中的子圖，其中每對頂點都由一條路徑連線，並且沒有其他頂點與之相連。
在本文中，我們將深入探討如何利用 C/C++ 程式語言來確定兩個頂點 X 和 Y 是否屬於無向圖中的同一連通分量。我們將闡明該方法的語法和原理，然後闡述至少兩種不同的解決此問題的方法。此外，我們將為每種方法提供具體的程式碼示例及其相應的結果。
語法
提供的程式碼片段在 C++ 中聲明瞭三個用於圖表示的函式。isConnected 函式接收兩個頂點 X 和 Y，並返回一個布林值，指示它們是否屬於同一連通分量。addEdge 函式接收兩個頂點 X 和 Y，並在圖中建立它們之間的連線。initializeGraph 函式接收一個整數 n 作為輸入，並使用 n 個頂點設定圖。這些函式可以使用各種圖演算法（如深度優先搜尋或廣度優先搜尋）來檢查兩個頂點的連通性以及在圖中建立頂點之間的連線。
bool isConnected(int X, int Y)
{
// Code to check if X and Y are in the same connected component
// Return true if X and Y are in the same connected component, false otherwise
}
void addEdge(int X, int Y)
{
// Code to add an edge between vertices X and Y in the graph
}
void initializeGraph(int n)
{
// Code to initialize the graph with 'n' vertices
}
演算法
步驟 1 − 使用 initialise Graph 函式初始化具有指定頂點數的圖。
步驟 2 − 使用 addEdge 函式，在頂點之間新增邊
步驟 3 − 實現圖遍歷方法，遍歷與某個頂點相關的每個頂點並將其標記為已訪問。
步驟 4 − 使用構建的圖遍歷方法確定頂點 X 和 Y 是否都已被訪問。
步驟 5 − 如果頂點 X 和 Y 都已被訪問，則返回 true；否則，返回 false。
方法
方法 1 − 使用 DFS；它是一種圖遍歷演算法，迭代訪問頂點並將其標記為已訪問，以探索圖。
方法 2 − 使用並查集方法，該方法使用資料結構來監控集合被劃分為不同的子組。它在識別無向圖的連通分量方面非常有效。
方法 1
在此方法中，它使用 DFS 檢查頂點 X 和 Y 是否在同一連通分量中，我們可以從頂點 X 開始並使用 DFS 遍歷圖。
示例 1
程式碼進行評估以驗證兩個頂點 X 和 Y 是否屬於圖中的同一連通分量。它使用深度優先搜尋 (DFS) 演算法遍歷圖並確定頂點的連通性。圖使用鄰接表表示，其中頂點之間的邊儲存為每個頂點的鄰接頂點列表。程式碼初始化 visited 陣列以監控在 DFS 遍歷期間已探索的頂點。對頂點 X 執行 DFS 函式，如果在 DFS 期間發現頂點 Y 已被訪問，則表示 X 和 Y 屬於同一連通分量。main 函式透過建立鄰接表並向其中新增邊來設定圖，然後執行多個查詢以驗證兩個頂點是否在同一連通分量中。
#include <iostream>
#include <vector>
using namespace std;
vector<int> adjList[100005];
bool visited[100005];
void dfs(int u) {
visited[u] = true;
for (int v : adjList[u])
if (!visited[v])
dfs(v);
}
bool areVerticesInSameComponentDFS(int X, int Y, int n) {
for (int i = 1; i <= n; i++)
visited[i] = false;
dfs(X);
return visited[Y];
}
int main() {
int n = 5;
int m = 4;
int edges[][2] = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
for (int i = 0; i < m; i++) {
int u = edges[i][0];
int v = edges[i][1];
adjList[u].push_back(v);
adjList[v].push_back(u);
}
int q = 2;
int queries[][2] = {{1, 4}, {2, 5}};
for (int i = 0; i < q; i++) {
int X = queries[i][0];
int Y = queries[i][1];
if (areVerticesInSameComponentDFS(X, Y, n))
cout << "Vertices " << X << " and " << Y << " are in the same connected component." << endl;
else
cout << "Vertices " << X <<" and " << Y << " are not in the same connected component." << endl;
}
return 0;
}
輸出
Vertices 1 and 4 are in the same connected component. Vertices 2 and 5 are in the same connected component.
方法 2
在此方法中，我們可以首先將每個頂點分配到一個不相交的集合中，以便使用並查集方法來確定頂點 X 和 Y 是否在同一連通分量中。然後，可以針對圖中的每條邊合併包含邊端點的集合。最後，我們可以確定頂點 X 和 Y 是否屬於同一集合，這表明它們是相關的元件。
示例 2
此程式碼實現了並查集演算法，以檢查兩個頂點是否在圖中的同一連通分量中。輸入以頂點數 n、邊數 m 和邊陣列 edges[m][2] 以及查詢數 q 和查詢陣列 queries[q][2] 的形式硬編碼。merge(u, v) 函式將包含頂點 u 的集合與包含頂點 v 的集合合併。areVerticesInSameComponentUnionFind(X, Y) 函式透過查詢兩個頂點的父節點並檢查它們是否相等來檢查頂點 X 和 Y 是否在同一連通分量中。如果它們相等，則頂點位於同一連通分量中，否則它們不在同一連通分量中。查詢結果列印到控制檯。
#include <iostream>
using namespace std;
int parent[100005];
// Function to find the parent of a set using the Union-Find algorithm
int find(int u) {
if (parent[u] == u) {
return u;
}
return find(parent[u]);
}
void merge(int u, int v) {
int parentU = find(u); // find the parent of u
int parentV = find(v);
if (parentU != parentV) {
parent[parentU] = parentV;
}
}
bool areVerticesInSameComponentUnionFind(int X, int Y) {
int parentX = find(X); // find the parent of X
int parentY = find(Y); // find the parent of Y
return parentX == parentY;
}
int main() {
int n = 5, m = 4;
int edges[m][2] = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int u = edges[i][0], v = edges[i][1];
merge(u, v);
}
int q = 3;
int queries[q][2] = {{1, 5}, {3, 5}, {1, 4}};
for (int i = 0; i < q; i++) {
int X = queries[i][0], Y = queries[i][1];
if (areVerticesInSameComponentUnionFind(X, Y)) {
cout << "Vertices " << X << " and " << Y << " are in the same connected component." << endl;
} else {
cout << "Vertices " << X << " and " << Y << " are not in the same connected component." << endl;
}
}
return 0;
}
輸出
Vertices 1 and 5 are in the same connected component. Vertices 3 and 5 are in the same connected component. Vertices 1 and 4 are in the same connected component.
結論
在此程式碼中，我們介紹了兩種確定無向圖的兩個頂點 X 和 Y 是否相關的方法。第一種方法使用深度優先搜尋 (DFS) 遍歷圖以標記已訪問的頂點，而第二種方法使用並查集演算法來跟蹤不相交的集合。
230 次瀏覽
