Frage nach der Art und Weise Diagramme unterrichtet werden

Question

Ich bin aus Argentinien, aber ich denke, dass jeder, der schon einmal eine Datenstruktur Klasse Know nehmen hat, was ein Graph ist. Wenn Sie das tun, vielleicht wissen Sie, welche Art von Implementierungen sind „gemeinsame“ oder „Standar“. Es kann durch eine Liste oder eine Anordnung implementiert werden. Wikipedia sagt auch dies. Neben Mark Allen Weiss, Bruno Preiss und Luis Joyanes Aguilar.

Die Sache ist. Niemand hat jemals denken, dass dies keine guten Weg, es zu tun? Die empfohlene Methode ist durch eine Liste. Aber angenommen, dass Ecken nur eine Kante zwischen ihnen haben können, ich glaube nicht, dass eine Liste die gute Schnittstelle ist, dies zu tun. Ich meine, wenn die Vertex V1 mit Vertex V2 verbunden ist, dann gibt es nur eine und nur eine Kante.

Glauben Sie nicht, es ist ein Set statt einer Liste sein?

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

Ich will nur einige Meinungen wissen, was denken Sie?

Danke !!

Edit: Auch, wenn wir denken, dass die Grafik nicht wiederholt Elemente hat, ein HashSet wäre eine gute Wahl sein, um die Suche nach dem Scheitelpunkt in der Einführung zu minimieren.

Answer 1

Sie sind zu Recht darauf hin, dass die adjacencies für einen Scheitelpunkt sind am genauesten durch einen Satz modelliert (oder im Fall eines Multigraphen, eine multiset). So tun, warum Datenstrukturen Bücher über Arrays schreiben und verkettete Listen statt? Ich kann mich drei Gründe:

1. Die Idee, dass Programmiersprachen Sätze als primitive Datentypen umfassen soll, ist ziemlich neu. Ältere Schriftsteller wäre es nicht in Betracht gezogen haben, verwenden und modernen Autoren neigen dazu, die Traditionen des Feldes.

folgen

2. Einer der Zwecke eines Datenstrukturen Kurses ist es, zu ermöglichen, um die Darstellung von Daten auf einem niedrigen (Beton) Ebene zu denken, als auch auf einem hohen (Auszug) Ebene. Ein Satz ist ein abstrakter Datentyp, dass (im Gegensatz zu verknüpften Listen und Arrays) keine offensichtliche Low-Level-Implementierung haben: einige Sätze werden am besten als verkettete Listen dargestellt, einige als Hash-Tabellen, einige als Arrays, und so weiter. So ist es natürlich für einen Datenstruktur natürlich ist die hohe Repräsentation von Mengen ihrer Low-Level-Implementierung zu überspringen, die Sie sowieso, um zu wissen, haben das Verhalten von Algorithmen zu analysieren, die sie verwenden.

3. Es ist wichtig, nicht zu dogmatisch, wie Datentypen darzustellen, weil Algorithmen am effizientesten insbesondere Darstellungen ausgedrückt werden kann. Beispiel 1 Um die Wege der Länge Zahl n zwischen jedem Paar von Scheitelpunkten in einem Diagramm, das Diagramm durch seine Adjazenzmatrix repräsentieren, und die Matrix mit dem Strom erhöhen n . Wenn Sie auf die die adjacencies eines Knotens als einen Satz von Kanten bestehen, dann werden Sie diesen Algorithmus verpassen (die Verwendung von Standardtechniken parallelisiert werden können). Beispiel 2. Knuth „ Tanzen Verbindungen “ Algorithmus für die genaue Abdeckung Problem Sätze von Spalten repräsentiert mit doppelt verkettete Listen, so dass die von gelöschten Elementen Links können für eine effiziente Rückverfolgung wiederverwendet werden.

Answer 2

Bei einer relativ höher C / C ++ Programmierer Ebene, wie ein Graph / Netzwerk implementiert wird, hängt sehr stark ab, was Operationen darauf ausgeführt werden. Sein ein OR Person selbst, ich bin wahrscheinlich in meiner Antwort / example hier vorgespannt ist. Einige der effizientesten Algorithmen, die auf Graphen implementiert werden kann / Netzwerke sind Polynomialzeit-Algorithmen. Die meisten, wenn nicht alle, Polynomialzeit-Algorithmen kann ich mich vorstellen (Dijkstra kürzesten Weg Problem, Transportproblem, max-Flow-Problem, etc.) sind Spezialfälle des Mindest-Cost-Flow (MCF) Problem. Rechnerisch ist eine der effizientesten Möglichkeiten zur Herstellung einer MCF Problemlösung über den Netzwerk-Simplex-Algorithmus (in mir selbst, die eine Spezialisierung des Simplex-Algorithmus ist ein allgemeines lineares Programm zu lösen).

Im Netzwerk-Simplex-Algorithmus, ein Spanning Tree (über den Satz von Knoten) muss effizient dargestellt werden. Um einen Spanning-Tree in einem Diagramm darstellt, kann eine Vielzahl von Datenstrukturen verwendet werden. Dazu gehören die folgenden Knoten Länge

predecessor[], thread[] and depth[] arrays.

In den effizientesten Implementierungen von Netzwerk-simplex-Algorithmen, dass ich stößt, wird diese nicht als Arrays dargestellt, sondern eine Art von dynamisch erzeugten Speicherblock über

calloc(number_of_nodes, sizeof(struct vertex));

Ich bin nicht sicher (bei einer relativ unteren Ebene) intern an den Compiler, was / wie diese Speicherzuordnung implementiert ist -. Ob es sich um eine Liste / set / Karte

So in der Zusammenfassung, die am besten Weg, um eine grafische Darstellung zu implementieren, ist stark abhängig von den Operationen, die damit ausgeführt werden.

Netzwerk-Simplex-Algorithmus und die Datenstrukturen benötigt, um effizient die gleichen implementieren können in dieses Buch zu finden .

Answer 3

Auf seinem abstrakten, hat ein Set ein Prädikat zu testen, ob ein Element innerhalb des Satzes ist. Es kann auch Betreiber unterstützt die Vereinigung und Durchschnitt bieten. Der Unterschied ist nicht notwendig, berechenbar.

Auf seiner Zusammenfassung, eine Liste unterstützt Iteration, Unterliste und Anfügen.

Die meisten Algorithmen auf Graphen benötigen Sie Iterierte über die Kanten, so eine Struktur, die Iteration unterstützt bevorzugt. Die meisten Algorithmen versuchen Sie nicht die gleiche Kante zweimal hinzuzufügen, so die Entfernung von Duplikaten ist nicht erforderlich.

Natürlich sind die meisten Sätze in Bibliotheken sind endlich, extensionale Sätze, die Iteration auch unterstützen, so dass Sie sie verwenden können, wenn Sie immer noch die Kosten für die Überprüfung auf Duplikate haben.

Einige Graphen-basierten Systeme verwenden Sie setzen als den zugrunde liegenden Mechanismus, aber sie sind der Umgang mit unendlichen Graphen anstatt endlich diejenigen, in denen intensionalen Sätze nützlich werden.