Fragen Sie ab, ob sich die Scheitelpunkte X und Y in derselben verbundenen Komponente eines ungerichteten Diagramms befinden

Die Graphentheorie befasst sich mit der Untersuchung verbundener Komponenten, bei denen es sich um Untergraphen in einem ungerichteten Graphen handelt, bei dem jedes Scheitelpunktpaar durch einen Pfad verbunden ist und kein anderer Scheitelpunkt mit ihm verbunden ist.

In diesem Artikel befassen wir uns damit, wie wir mithilfe der Programmiersprache C/C++ bestimmen können, ob zwei Scheitelpunkte X und Y zu derselben verbundenen Komponente in einem ungerichteten Graphen gehören. Wir werden die Syntax und das Grundprinzip der Methode klären, bevor wir mindestens zwei verschiedene Möglichkeiten zur Lösung dieses Problems erläutern. Darüber hinaus stellen wir für jede Methode spezifische Codebeispiele und die entsprechenden Ergebnisse bereit.

Grammatik

Der bereitgestellte Codeausschnitt deklariert drei Funktionen in C++ zur grafischen Darstellung. Die Funktion isConnected nimmt zwei Scheitelpunkte X und Y und gibt einen booleschen Wert zurück, der angibt, ob sie zur gleichen verbundenen Komponente gehören. Die Funktion addEdge nimmt zwei Scheitelpunkte X und Y und erstellt eine Verbindung zwischen ihnen im Diagramm. Die Funktion „InitializeGraph“ verwendet einen ganzzahligen Wert n als Eingabe und erstellt einen Graphen mit n Eckpunkten. Diese Funktionen können mithilfe verschiedener Diagrammalgorithmen ausgeführt werden, z. B. der Tiefensuche oder der Breitensuche, um die Konnektivität zweier Scheitelpunkte zu überprüfen und Verbindungen zwischen Scheitelpunkten im Diagramm herzustellen.

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
}

Algorithmus

Schritt 1 – Initialisieren Sie das Diagramm mit der angegebenen Anzahl von Scheitelpunkten mithilfe der Funktion „Diagramm initialisieren“.

Schritt 2 – Verwenden Sie die Funktion addEdge, um Kanten zwischen Eckpunkten hinzuzufügen

Schritt 3 – Implementieren Sie eine Graph-Traversal-Methode, um jeden mit einem Scheitelpunkt verbundenen Scheitelpunkt zu durchlaufen und ihn als besucht zu markieren.

Schritt 4 – Verwenden Sie die Methode zum Durchlaufen konstruierter Graphen, um festzustellen, ob beide Scheitelpunkte X und Y besucht wurden.

Schritt 5 – Wenn beide Scheitelpunkte X und Y besucht werden, geben Sie true zurück, andernfalls geben Sie false zurück.

Methode

• Methode 1 – Verwenden Sie DFS; es handelt sich um einen Graph-Traversal-Algorithmus, der iterativ Scheitelpunkte besucht und sie als besucht markiert, um den Graphen zu untersuchen.

• Methode 2 – Verwenden Sie die Union-Suchmethode, die Datenstrukturen verwendet, um die Aufteilung der Sammlung in verschiedene Untergruppen zu überwachen. Es kann verbundene Teile ungerichteter Graphen effektiv identifizieren.

Methode 1

Bei dieser Methode wird DFS verwendet, um zu prüfen, ob sich die Scheitelpunkte X und Y in derselben verbundenen Komponente befinden. Wir können am Scheitelpunkt X beginnen und den Graphen mit DFS durchlaufen.

Beispiel 1

Der Code wertet aus, um zu überprüfen, ob zwei Scheitelpunkte X und Y zu derselben verbundenen Komponente im Diagramm gehören. Es verwendet einen Tiefensuchalgorithmus (DFS), um den Graphen zu durchqueren und die Konnektivität von Eckpunkten zu bestimmen. Der Graph wird mithilfe von Adjazenzlisten beschrieben, wobei Kanten zwischen Scheitelpunkten als Liste der benachbarten Scheitelpunkte jedes Scheitelpunkts gespeichert werden. Der Code initialisiert das besuchte Array, um die Scheitelpunkte zu überwachen, die während der DFS-Durchquerung untersucht wurden. Führen Sie die DFS-Funktion am Scheitelpunkt X aus. Wenn festgestellt wird, dass der Scheitelpunkt Y während des DFS-Prozesses besucht wird, bedeutet dies, dass sowohl X als auch Y Teil derselben verbundenen Komponente sind. Die Hauptfunktion richtet den Graphen ein, indem sie eine Adjazenzliste erstellt und ihr Kanten hinzufügt. Anschließend führt sie mehrere Abfragen durch, um zu überprüfen, ob sich zwei Scheitelpunkte in derselben verbundenen Komponente befinden.

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

Ausgabe

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

Methode 2

Bei diesem Ansatz können wir zunächst jeden Scheitelpunkt einer disjunkten Menge zuweisen, um mithilfe der Methode „and“ zu ermitteln, ob sich die Scheitelpunkte X und Y in derselben Verbindungskomponente befinden. Die Sammlung der Kantenendpunkte kann dann für jede Kante im Diagramm kombiniert werden. Schließlich können wir feststellen, ob die Scheitelpunkte X und Y Mitglieder derselben Menge sind, was darauf hinweist, dass es sich um verwandte Komponenten handelt.

Beispiel 2

Dieser Code implementiert und findet einen Algorithmus, um zu überprüfen, ob sich zwei Scheitelpunkte in derselben verbundenen Komponente des Diagramms befinden. Die Eingabe ist in Form einer Anzahl von Scheitelpunkten n, einer Anzahl von Kanten m und einem Kantenarray Edges[m][2] sowie einer Abfragenummer q und einem Abfragearray Queries[q][2] fest codiert. . Die Funktion merge(u, v) führt die Menge, die den Scheitelpunkt u enthält, mit der Menge zusammen, die den Scheitelpunkt v enthält. Die Funktion areVerticesInSameComponentUnionFind(X, Y) prüft, ob sich die Scheitelpunkte X und Y in derselben verbundenen Komponente befinden, indem sie ihre übergeordneten Knoten findet und prüft, ob sie gleich sind. Wenn sie gleich sind, befinden sich die Scheitelpunkte in derselben verbundenen Komponente, andernfalls nicht. Die Abfrageergebnisse werden auf der Konsole gedruckt.

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

Ausgabe

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.

Fazit

In diesem Code stellen wir zwei Methoden vor, um zu bestimmen, ob zwei ungerichtete Graphscheitelpunkte X und Y miteinander in Beziehung stehen. Die zweite Strategie verwendet einen Union-Find-Algorithmus, um disjunkte Mengen zu verfolgen, während der erste Ansatz die Tiefensuche (DFS) verwendet, um den Graphen zu durchqueren und besuchte Eckpunkte zu markieren.

Das obige ist der detaillierte Inhalt vonFragen Sie ab, ob sich die Scheitelpunkte X und Y in derselben verbundenen Komponente eines ungerichteten Diagramms befinden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!