Ist bipartit
Lektion 14 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Ein Graph ist bipartit, wenn man seine Knoten so in zwei Gruppen aufteilen kann, dass jede Kante einen Knoten der einen Gruppe mit einem Knoten der anderen Gruppe verbindet. Denken Sie an Rot und Blau: Jede Kante hat einen roten Endpunkt und einen blauen Endpunkt.
Die Breitensuche (BFS) bietet einen sauberen Test. Beginnen Sie bei einem beliebigen Knoten, färben Sie ihn rot und gehen Sie nach außen. Jeder neue Nachbar erhält die entgegengesetzte Farbe des Knotens, von dem wir gekommen sind. Wenn wir jemals eine Kante sehen, die zwei Knoten mit der gleichen Farbe verbindet, ist der Graph nicht bipartit. Der klassische Übeltäter ist ein Zyklus ungerader Länge: Ein Dreieck 0-1-2-0 zwingt Knoten 0 dazu, sowohl rot als auch blau zu sein.
Eines sollte man beachten: Wenn der Graph mehrere Zusammenhangskomponenten hat, muss man für jede eine neue 2-Färbung starten. Das einfachste Muster ist eine einzelne Schleife über alle Knoten, die eine BFS startet, wann immer sie einen ungefärbten Knoten findet.
Aufgabe
EinfachSchreiben Sie eine Funktion isBipartite, die ein 2D-Int-Array adjacency und ein Int-Array vertices erhält und true zurückgibt, wenn der Graph bipartit ist, andernfalls false.
Bauen Sie den Graphen auf (jeweils addVertex, dann jeweils addEdge). Führen Sie dann eine 2-Färbung mittels BFS über jede zusammenhängende Komponente durch: Weisen Sie der Startknoten die Farbe 0 zu, und geben Sie jedem Nachbarn die Farbe 1 - color[u]. Wenn Sie jemals eine Kante finden, bei der beide Endpunkte bereits dieselbe Farbe haben, geben Sie false zurück. Andernfalls geben Sie true zurück.
Sie müssen die Graph-Klasse verwenden (bereitgestellt in graph) – verwenden Sie keine in der Sprache eingebauten Typen (Maps, Sets), um die Adjazenz zu modellieren. Hilfsdaten für den Algorithmus (Color-Map, Queue) dürfen Standardbibliotheks-Typen 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("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}