Query whether vertices X and Y are in the same connected component of an undirected graph

Graph theory covers the study of connected components, which are subgraphs in an undirected graph where every pair of vertices is linked by a path and no other vertex is connected to it.

In this article, we will delve into how to use the C/C programming language to determine whether two vertices X and Y belong to the same connected component in an undirected graph. We will clarify the syntax and rationale of the method before clarifying at least two different ways to solve this problem. In addition, we will provide specific code examples and their corresponding results for each method.

grammar

The provided code snippet declares three functions in C for graphical representation. The isConnected function takes two vertices X and Y and returns a Boolean value indicating whether they belong to the same connected component. The addEdge function takes two vertices X and Y and creates a connection between them in the graph. The InitializeGraph function takes an integer value n as input and sets up a graph with n vertices. These functions can be executed using various graph algorithms, such as depth-first search or breadth-first search, to check the connectivity of two vertices and establish connections between vertices in the graph.

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
}

algorithm

Step 1 - Use the initialize Graph function to initialize the graph with the specified number of vertices.

Step 2 - Use the addEdge function to add edges between vertices

Step 3 - Implement the graph traversal method to traverse every vertex related to a vertex and mark it as visited.

Step 4 - Use the constructed graph traversal method to determine if both vertices X and Y have been visited.

Step 5 - If both vertices X and Y are visited, return true; otherwise, return false.

method

• Method 1 - Use DFS; it is a graph traversal algorithm that iteratively visits vertices and marks them as visited in order to study the graph.

• Method 2 - Use the union search method, which uses data structures to monitor the division of the collection into different subgroups. It can effectively identify connected parts of undirected graphs.

method 1

In this method, it uses DFS to check if vertices X and Y are in the same connected component, we can start from vertex X and traverse the graph using DFS.

Example 1

The code is evaluated to verify whether two vertices X and Y belong to the same connected component in the graph. It employs a depth-first search (DFS) algorithm to traverse the graph and determine the connectivity of vertices. The graph is described using adjacency lists, where edges between vertices are stored as a list of each vertex's neighboring vertices. The code initializes the visited array to monitor the vertices that have been explored during the DFS traversal. Execute the DFS function on the vertex X. If the vertex Y is found to be visited during the DFS process, it means that both X and Y are part of the same connected component. The main function sets up the graph by creating an adjacency list and adding edges to it, and then performs multiple queries to verify that two vertices are in the same connected component.

#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;
}

Output

Vertices 1 and 4 are in the same connected component.
Vertices 2 and 5 are in the same connected component.

Method 2

In this approach, we can first assign each vertex to a disjoint set in order to use the and find method to determine whether vertices X and Y are in the same link component. The collection of edge endpoints can then be combined for each edge in the graph. Finally, we can determine whether vertices X and Y are members of the same set, indicating that they are related components.

Example 2

This code implements and finds algorithms to check if two vertices are in the same connected component of the graph. The input is hard-coded in the form of a number of vertices n, a number of edges m, and an edge array Edges[m][2], and a query number q and a query array Queries[q][2]. The function merge(u, v) merges the set containing vertex u with the set containing vertex v. The function areVerticesInSameComponentUnionFind(X, Y) checks whether vertices X and Y are in the same connected component by finding their parent nodes and checks whether they are equal. If they are equal, the vertices are in the same connected component, otherwise they are not. The query results will be printed to the console.

#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;
}

Output

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.

in conclusion

In this code, we introduce two methods to determine whether two undirected graph vertices X and Y are related to each other. The second strategy employs a union-find algorithm to keep track of disjoint sets, while the first approach uses depth-first search (DFS) to traverse the graph to mark visited vertices.

The above is the detailed content of Query whether vertices X and Y are in the same connected component of an undirected graph. For more information, please follow other related articles on the PHP Chinese website!