Zusammenhangskomponenten zählen
Lektion 13 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Eine Zusammenhangskomponente ist eine maximale Menge von Knoten, bei der zwischen jedem Paar ein Pfad existiert. Ein Graph ohne Kanten hat so viele Komponenten wie Knoten; ein vollständig verbundener Graph hat genau eine Komponente.
Um sie zu zählen, durchlaufen Sie alle Knoten. Wann immer Sie einen finden, der noch nicht besucht wurde, handelt es sich um eine neue Komponente: Erhöhen Sie den Zähler und führen Sie dann eine BFS oder DFS von diesem Knoten aus durch, um jeden erreichbaren Knoten als besucht zu markieren. Fahren Sie mit dem nächsten nicht besuchten Knoten fort.
Diese Herausforderung gibt Ihnen SOWOHL die Knotenliste als auch die Kanten, da isolierte Knoten (ohne Kanten) immer noch als eigene Komponente zählen und wir wissen müssen, dass sie existieren.
Aufgabe
EinfachSchreiben Sie eine Funktion countConnectedComponents, die ein 2D-Int-Array adjacency und ein Int-Array vertices erhält und die Anzahl der zusammenhängenden Komponenten im Graphen zurückgibt.
Bauen Sie den Graphen auf: Führen Sie zuerst addVertex für jeden Schlüssel in vertices aus (damit isolierte Knoten vorhanden sind), und dann addEdge für jedes Paar in adjacency. Durchlaufen Sie dann alle Knoten: Jeder nicht besuchte Knoten startet eine neue Komponente (erhöhen Sie den Zähler), und führen Sie dann eine DFS/BFS von diesem Knoten aus durch, um die gesamte Komponente als besucht zu markieren.
Sie müssen die Klasse Graph verwenden (bereitgestellt in graph) – verwenden Sie keine in der Sprache eingebauten Strukturen (Maps, Sets), um die Adjazenz zu modellieren. Hilfsdaten für den Algorithmus (Visited-Sets, Stacks) dürfen Standardbibliothekstypen verwenden.
Probier es selbst
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}