AlgoDat SoSe2000, Aufgabe 66 Einfuegen in die verschiedenen Darstellungen eines Graphen Zwei Realisierungen als Pseudocode, die ersten pruefen nicht, ob die Kante schon drin ist, die zweiten tun es. Christian Semrau gsemrau@cs.uni-magdeburg.de Die folgenden Algorithmen pruefen NICHT, ob die Kante bereits enthalten ist, gegebenenfalls ist sie nach dem Einfuegen mehrfach im Graphen enthalten. Es wird auch nicht gecheckt, ob die zu verbindenden Knoten existieren. a) Kantenliste: neuerKnoten erhoehe Element 0 um 1 // die Knotenzahl ende neuerKnoten O(1) neueKante (von, nach) haenge hinten an haenge hinten an // gegebenenfalls vorher das Feld umkopieren erhoehe Element 1 um 1 // die Kantenzahl ende neueKante O(1) ausser wenn umkopiert werden muss, dann O(m) b) Knotenliste: neuerKnoten erhoehe Element 0 um 1 // die Knotenzahl haenge eine 0 hinten an // keine ausgehenden Kanten fuer den neuen Knoten ende neuerKnoten O(1) ausser wenn umkopiert werden muss, dann O(n+m) neueKante (von, nach) gehe zu den Daten des Knoten erhoehe die Kantenzahl des Knoten um 1 fuege rechts von der Kantenzahl ein ende neueKante O(n+m) c) Adjazenzmatrix: neuerKnoten kopiere die Matrix in ein Feld das um 1 groesser in beiden Koordinaten ist belege die unterste Zeile und die rechte Spalte mit 0 ende neuerKnoten O(n*n) neueKante(von, nach) erhoehe das Matrixelement um 1 ende neueKante O(1) d) Adjazenzliste: neuerKnoten haenge eine neue leere Liste an das "Listen-Feld" an // gegebenenfalls vorher umkopieren ende neuerKnoten O(1), ausser wenn umkopiert werden muss, dann O(n) neueKante(von, nach) haenge die Zahl vorn an die Liste an ende neueKante O(1) ---------------------------------------------------------------------- Nun mit Erzeugen von noch nicht vorhandenen Knoten beim Einfuegen einer Kante, und jede Kante kann nur noch einmal im Graphen sein. Das Knoten-Einfuegen bleibt so wie es ist. a) Kantenliste: // die Kanten sind nach dem Anfangsknoten aufsteigend sortiert neueKante(von, nach) suche die Stelle, an der die Kante eingefuegt werden muesste (binaer) wenn sie dort noch nicht steht, dann mache Platz fuer zwei Elemente (umkopieren) fuege ein fuege ein erhoehe Element 1 um 1 // die Kantenzahl setze Element 0 auf das Maximum von Element 0, und // soviele Knoten erzeugen wie noetig ende neueKante O(m) b) Knotenliste: // die Zielknoten eines jeden Knoten sind aufsteigend sortiert neueKante(von, nach) wenn einer der Knoten oder noch nicht existiert (Element 0 ist kleiner als bzw ), dann bestimme das Maximum von und haenge soviele 0 hinten an, wie die Differenz des Maximums und des Element 0 ist setze Element 0 auf das Maximum suche und merke die Stelle, wo die Daten des Knoten beginnen suche die Stelle, wo der Zielknoten eingefuegt werden muesste (binaer) wenn er noch nicht enthalten ist, dann mache Platz fuer ein Element (umkopieren) fuege die Zahl ein erhoehe die Kantenzahl des Knoten um 1 ende neueKante O(n+m) c) Adjazenzmatrix: neueKante(von, nach) wenn einer der Knoten oder noch nicht existiert (Element 0 ist kleiner als bzw ), dann bestimme das Maximum von und kopiere die Matrix in ein neues Feld mit der Groesse des Maximums belege die hinzugekommenen Zeilen und Spalten mit 0 setze das Matrixelement auf 1 ende neueKante O(1), ausser wenn neue Knoten erzeugt werden muessen, dann O(n*n) d) Adjazenzliste: // die Zielknoten in jeder Liste sind aufsteigend sortiert neueKante(von, nach) wenn einer der Knoten oder noch nicht existiert (Element 0 ist kleiner als bzw ), dann bestimme das Maximum von und kopiere das "Listen-Feld" in eine neues Feld mit der Groesse des Maximums belege die hinzugekommenen Elemente mit einer leeren Liste suche in der Liste nach der Stelle, an der der Zielknoten eingefuegt werden muesste wenn der Zielknoten noch nicht drin ist, dann fuege ihn ein ende neueKante O(m/n), ausser wenn neue Knoten erzeugt werden muessen, dann O(n)