查询是否顶点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.

登录后复制