Wie implementiere ich einen Bipartite Graph in Java?

Es sollte ziemlich einfach sein, mit einer Adjazenzliste zu implementieren. Wenn es sich um ein ungerichtetes zweiteiliges Diagramm handelt, könnte ich eine Inzidenzmatrix vorschlagen.

Sie müssten also ein Array verknüpfter Listen oder ein Array einer Art dynamisch zugewiesener Liste für jeden Knoten haben. Es sollte das Hinzufügen von Kanten ziemlich natürlich machen, zum Beispiel in Ihrem Beispiel haben Sie eine Kante:

Person A- & gt; Person B

Dann würden Sie den Array-Index für Person A aufrufen und den Index für Persona B zurücksetzen:

[Person A] = Person B

Dann bekommst du vielleicht eine andere Kante

Persona A- & gt; Person C

Dann würde Ihr Index dort aussehen wie:

[Persona A] = Person B, Person C

Als letztes Beispiel wäre dies die Adjazenzliste für Ihr Beispieldiagramm:

[A] B

[B] D

[C] B

[D] B

[E] A, C

Jeder Index enthält eine Liste der Knoten, die von diesem Knoten aus erreichbar sind.

"Welche Dinge (Algorithmen) sollte ich berücksichtigen und darüber nachdenken, wenn ich die BipartiteGraph-Klasse erstelle? Vielleicht Traversierungs- / Sortieralgorithmen?"

Es hängt wirklich davon ab, was Sie mit dem Graphen machen wollen ...

Zur Referenz: Ähnliche Fragen zu Code in Sun Forums

Adjazenz-Liste-eines-gerichteten-gewichteten-Graphen

VERSUCH DIESES: -

Dies ist eine c # Implementierung, aber das Konzept kann auch in Java verwendet werden. Ich habe Adjacency Matrix verwendet, um Graph darzustellen. Überprüfen, ob im Diagramm ein Zyklus oder ein ungeradzahliger Zyklus vorliegt.

Ein Graph heißt Bipartite, wenn es in diesem Graph eine Partition gibt, in der u und v steht (u union v) = Graph und (u intersection v) = null Wenn Sie das Bild unten betrachten, 1,2,3,4,5,6,7 sind die Eckpunkte in der Grafik G. Betrachten wir die Eckpunkte auf der linken Seite (1,4,5,6) als U und auf der rechten Seite ( 2,3,7) als V

Stellen Sie sich vor, dass im Diagramm momentan keine rote Verbindung vorhanden ist. Sie können sehen, dass eine Verbindung von u zu v und v zu Ihnen als einem ungerichteten Graphen besteht. aber es gibt keine Verbindung mit in der Partition. Das ist das Konzept, das ich verwenden werde.

Betrachten Sie das Diagramm wie unten gezeigt, es ist das gleiche Diagramm oben, außer dass es mehr wie eine Baumstruktur gezeichnet ist. In diesem Fall, wenn Sie sehen können, dass die Knoten auf den alternativen Ebenen 1, 3, 5 zusammen eine Partition bilden und 2,4 eine weitere Partition bilden können. Wir können also leicht sagen, dass der Graph BiPartite ist. Was ist, wenn zwischen den Elementen auf der gleichen Ebene eine rote Kante liegt? dann ist der Graph nicht zweiteilig. Wenn Sie den BFS-Algorithmus ändern könnten, können wir dies erreichen.

Hier ist der Code dafür.

Ein gerichteter Graph ist einer, in dem eine Kante, die die Knoten A und B verbindet, eine Richtung hat; Wenn es eine Kante von A nach B gibt, heißt das nicht, dass es eine Kante von B nach A gibt. In Ihrem Beispiel haben die Kanten eine Richtung. (B bis D wären zwei Kanten, eine von B nach D und eine von D nach B.)

Eine Möglichkeit, dies zu implementieren, wäre in ähnlicher Weise wie bei einer verknüpften Liste, wobei die Knoten untereinander Referenzen haben. In Bezug auf Ihr Beispiel würde nodeA einen Verweis auf nodeB haben, aber nicht umgekehrt. nodeE hätte einen Verweis auf nodeA und nodeC und so weiter. Sie erstellen wirklich eine (Art von) Datenstruktur, die eine Vorstellung von Knoten und vielleicht Kanten hat. Es gibt eine Reihe von Möglichkeiten, wie Sie es tun könnten.

Eine mögliche Java-Implementierung wäre eine Klasse namens AdjacencyList mit einem Map<Vertex, List<Vertex>> , der einen Eckpunkt und seine benachbarten Eckpunkte enthält. AdjacencyList wäre dann in der Lage, Operationen auf seiner Map durchzuführen.

Was Algorithmen und Dinge betrifft, die Sie im Auge behalten sollten, werfen Sie einen Blick auf die Eigenschaften von zweiteiligen Graphen auf Wikipedia

• Ein Graph ist genau dann zweigliedrig, wenn er keinen ungeraden Zyklus enthält. Daher kann ein zweiteiliger Graph keine Clique der Größe 3 oder mehr enthalten.
• Jeder Baum ist zweigeteilt.
• Zyklusgraphen mit einer geraden Anzahl von Vertices sind zweigeteilt.

Ein guter Test wäre die Implementierung eines Zweifärbungsalgorithmus, um zu bestätigen, dass der Graph tatsächlich zweigeteilt ist. Tiefe erste Suche, Breite erste Suche sind gute Übungen der Implementierung.

1.) Wählen Sie einen zufälligen Knoten. Setzen Sie es auf die "linke" Seite des zweiteiligen Graphen.

2.) Wählen Sie alle Knoten neben dem Knoten, die Sie in 1 ausgewählt haben und setzen Sie alle auf die "rechte" Seite.

3.) Die restlichen Knoten gehören alle zur "linken" Seite des zweiteiligen Graphen.

ENDE