查詢是否頂點X和Y在無向圖的同一連通分量中-C++-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都是同一個連通分量的一部分。主函數透過建立鄰接清單並在其中新增邊來設定圖，然後執行多個查詢來驗證兩個頂點是否位於同一個連接元件中。

#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 的父節點來檢查頂點 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.

登入後複製