Demander si les sommets X et Y se trouvent dans le même composant connecté d'un graphe non orienté

La théorie des graphes couvre l'étude des composants connectés, qui sont des sous-graphes dans un graphe non orienté où chaque paire de sommets est liée par un chemin et aucun autre sommet n'y est connecté.

Dans cet article, nous verrons comment utiliser le langage de programmation C/C++ pour déterminer si deux sommets X et Y appartiennent au même composant connexe dans un graphe non orienté. Nous clarifierons la syntaxe et la justification de la méthode avant de clarifier au moins deux manières différentes de résoudre ce problème. De plus, nous fournirons des exemples de code spécifiques et leurs résultats correspondants pour chaque méthode.

Grammaire

L'extrait de code fourni déclare trois fonctions en C++ pour la représentation graphique. La fonction isConnected prend deux sommets X et Y et renvoie une valeur booléenne indiquant s'ils appartiennent au même composant connecté. La fonction addEdge prend deux sommets X et Y et crée une connexion entre eux dans le graphique. La fonction InitializeGraph prend une valeur entière n en entrée et configure un graphique avec n sommets. Ces fonctions peuvent être exécutées à l'aide de divers algorithmes de graphe, tels que la recherche en profondeur d'abord ou la recherche en largeur d'abord, pour vérifier la connectivité de deux sommets et établir des connexions entre les sommets du graphe.

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
}

Algorithme

Étape 1 - Initialisez le graphique avec le nombre de sommets spécifié à l'aide de la fonction d'initialisation du graphique.

Étape 2 - Utilisez la fonction addEdge pour ajouter des arêtes entre les sommets

Étape 3 - Implémentez une méthode de parcours graphique pour parcourir chaque sommet lié à un sommet et le marquer comme visité.

Étape 4 - Utilisez la méthode de parcours de graphe construit pour déterminer si les deux sommets X et Y ont été visités.

Étape 5 - Si les deux sommets X et Y sont visités, renvoyez vrai sinon, renvoyez faux ;

Méthode

• Méthode 1 - Utilisez DFS ; il s'agit d'un algorithme de parcours de graphique qui visite les sommets de manière itérative et les marque comme visités afin d'étudier le graphique.

• Méthode 2 - Utilisez la méthode de recherche par union, qui utilise des structures de données pour surveiller le partitionnement de la collection en différents sous-groupes. Il peut identifier efficacement les parties connectées de graphiques non orientés.

Méthode 1

Dans cette méthode, il utilise DFS pour vérifier si les sommets X et Y sont dans le même composant connecté, nous pouvons partir du sommet X et parcourir le graphique en utilisant DFS.

Exemple 1

Le code évalue pour vérifier si deux sommets X et Y appartiennent au même composant connecté dans le graphique. Il utilise un algorithme de recherche en profondeur (DFS) pour parcourir le graphique et déterminer la connectivité des sommets. Le graphe est décrit à l'aide de listes de contiguïté, où les arêtes entre les sommets sont stockées sous forme de liste des sommets voisins de chaque sommet. Le code initialise le tableau visité pour surveiller les sommets qui ont été explorés lors du parcours DFS. Exécutez la fonction DFS sur le sommet X. Si le sommet Y est visité pendant le processus DFS, cela signifie que X et Y font partie du même composant connecté. La fonction principale configure le graphique en créant une liste de contiguïté et en y ajoutant des arêtes, puis effectue plusieurs requêtes pour vérifier que deux sommets se trouvent dans le même composant connecté.

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

Sortie

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

Méthode 2

Dans cette approche, nous pouvons d'abord attribuer chaque sommet à un ensemble disjoint afin d'utiliser la méthode and find pour déterminer si les sommets X et Y sont dans le même composant de lien. La collection de points finaux de bord peut ensuite être combinée pour chaque bord du graphique. Enfin, nous pouvons déterminer si les sommets X et Y sont membres du même ensemble, indiquant qu’ils sont des composants liés.

Exemple 2

Ce code implémente et trouve un algorithme pour vérifier si deux sommets sont dans la même composante connectée du graphe. L'entrée est codée en dur sous la forme d'un nombre de sommets n, d'un nombre d'arêtes m et d'un tableau d'arêtes Edges[m][2], ainsi que d'un numéro de requête q et d'un tableau de requêtes Queries[q][2] . La fonction merge(u, v) fusionne l'ensemble contenant le sommet u avec l'ensemble contenant le sommet v. La fonction areVerticesInSameComponentUnionFind(X, Y) vérifie si les sommets X et Y sont dans le même composant connecté en trouvant leurs nœuds parents et vérifie s'ils sont égaux. S'ils sont égaux, les sommets sont dans la même composante connexe, sinon ils ne le sont pas. Les résultats de la requête seront imprimés sur la 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;
}

Sortie

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.

Conclusion

Dans ce code, nous introduisons deux méthodes pour déterminer si deux sommets de graphe non orienté X et Y sont liés l'un à l'autre. La deuxième stratégie utilise un algorithme de recherche d'union pour suivre les ensembles disjoints, tandis que la première approche utilise la recherche en profondeur d'abord (DFS) pour parcourir le graphique afin de marquer les sommets visités.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!