Graph Häufigkeit Liste Implementierung

Question

Ich erwäge Graphdatenstruktur Implementierungen und bin auf der Suche auf der „Einfall Liste“ Darstellung. Es gibt eine kurze Beschreibung davon hier:

Incidence Liste

So hat jeder Knoten in dem Graphen speichert eine Liste derjenigen Kanten, auf dem es einfällt.

Da meine Graph ein gerichteter Graph ist, ich bin nicht ganz klar aus dieser Beschreibung auf ein paar Punkte:

1. Ist der Graph selbst speichert auch eine Liste aller Kanten?
2. Do Eckpunkten speichert nur ausgehende Kanten oder ein- und ausgehend?
3. Wenn beide, sind sie in separaten Listen?

Ich bin ganz mit den anderen Grafikdarstellungen (Adjazenzliste, Adjazenzmatrix, Kantenliste, lnzidenzmatrix) vertraut, so dass dies nicht eine Frage über Graph Implementierungen im Allgemeinen ist, gerade diese besondere ein.

Alle Zeiger würden sehr geschätzt werden.

Answer 1

Nachdem recherchiert und dachte darüber weiter, habe ich zu dem Schluss gekommen, dass es nicht ein Inzidenz Liste Diagrammdaten strucure ist. Ich denke, dass die Wikipedia-Artikel das Produkt einiger Verwirrung im Kopf des Autors war. Vielen Dank an alle, die diese Frage zu lesen und zu jeder Zeit dafür ausgegeben.

Armand

Answer 2

Ich weiß, ich bin vielleicht eine alte Frage von den Toten auferweckt, aber ich fühlte es Kommentar zu eigen.

Sie können eine Inzidenz Liste Graphenstruktur machen, und Sie können es auch für Digraphe zwicken.

Betrachten wir ein LinkedList<Vertex> Objekt und ein LinkedList<Edge> Objekt. Dies würde Sie Iterierte über alle Kanten lassen und alle Ecken, enthält jedoch keine Informationen darüber, wie alles miteinander verbunden ist.

Sagen wir fügen dann mehr LinkedList<Connection> Objekte. In der Tat, ein für jeden Vertex. Ein Connection ist einfach da, wo ein Edge und ein Vertex treffen. Somit wird eine Edge Connection zwei Objekte (Für einen ungerichteten Graphen) und eine Vertex wird ein LinkedList<Connection> Objekt haben, repräsentieren Verbindungen zu jedem Edge, die mit ihm verbunden ist. Dies ist im Wesentlichen eine Inzidenz-Liste.

Sie können dies ändern, um eine digraph darzustellen, wenn Sie einige dieser Connection Objekte löschen. Genauer gesagt, werden Sie nicht diese Referenzen haben wählen müssen, wohin. Sie können wählen, eine Connectionfrom die zugehörige LinkedList<Connection> zu löschen, wenn Sie einen Edge von einem Vertex zu sehen, nicht in der Lage sein wollen (für das obige Beispiel, N2 eine leere LinkedList<Connection> hätte). Sie könnten stattdessen wählen, die Verweise auf dem Edge (Für das obige Beispiel optional zu machen, würde E1 ein Connection zeigt auf N2 und eine Connection null hat, von E1 bis N2 ermöglicht Traversal, aber nicht zurück auf N1. Sie haben die Wahl, wie zu implementieren dies würde Ihnen ganz oben sein One ist intuitiver -.. Die Kanten ausgerichtet sind, so die Anschlüsse an Kanten zu diktieren zu entfernen, die Art, wie sie gehen scheint logisch Die andere vielleicht ein wenig komplexer scheinen auf den ersten, aber Sie werden unnötig stoppen auf Hopping Kanten, die zu nichts führen, wenn Breite sucht ersten und Tiefen tun.

In Punkt Form:

1. In meinen Implementierungen einer Inzidenz Liste habe ich. Müssen Sie für Ihre Implementierung?

2. Genau genommen könnte man nur ausgehende Kanten Speicherung erhalten. Allerdings könnte Rückzieher Algorithmen von der Möglichkeit profitieren entlang Verweise auf Rückzieher sie gereist. Sie können dies implementieren um, natürlich, mit einer Art von Geschichte, so dass es wahrscheinlich nicht viel von einer Überlegung ist.

3. Wenn Sie beide tun, würden Sie wahrscheinlich eine gewisse Art und Weise müssen zu unterscheiden, ob es ein- oder ausgehender ist. Ob das durch zwei LinkedList<Connection> auf der Vertex-Objekte oder durch eine boolean pointingToVertex primitive auf Connection hat, oder was auch immer. Vielleicht würden Ihre Edge gerichtet und ungerichteten Kanten würden aus zwei Kanten entgegengesetzte Weise zeigen. Überlegungen vorgenommen werden, je nach den Bedürfnissen Ihrer Struktur.

Answer 3

ich eine Inzidenz Liste in der folgenden Art und Weise durchgeführt und kein Problem für finden konnte, ungerichtete Graphen . Ich implementierte auch mehrere Graph-Topologie-Algorithmen.

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

Karte von Sätzen Verwendung garantieren O (1) für Vertices lookup und planmäßig O (1) die Komplexität für die Kanteneinfügungs und Löschungen. anstelle einer benachbarten Liste von Scheitelpunkten einen Einfall Liste von Kanten zu halten, ist nur ein Weg, um einige bestimmten Informationen der Kante selbst zu tragen. Dies ist nützlich für abstrakte Algorithmen zu, wenn Sie zum Beispiel ein Gewicht an den Rändern in Verbindung bringen.

EDIT:

habe ich aktualisiert die Gespräche Wikipedia für die „Häufigkeit Liste“ zu gelangen.