数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
