Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


29. Elementare Algorithmen für Graphen



Übungen

  1. Welche Darstellung eines ungerichteten Graphen ist am zweckmäßigsten, um schnell zu bestimmen, ob ein Knoten isoliert (mit keinem anderen Knoten verbunden) ist oder nicht?
  2. Angenommen, Tiefensuche wird für einen binären Suchbaum benutzt, und von jedem Knoten aus wird die rechte Kante vor der linken genommen. In welcher Reihenfolge werden die Knoten besucht?
  3. Wie viele Speicherbits sind erforderlich, um die Adjazenzmatrix für einen ungerichteten Graphen mit V Knoten und E Kanten darzustellen, und wie viele sind für die Darstellung mittels einer Adjazenzliste erforderlich?
  4. Skizzieren Sie einen Graph, der nicht auf einem Blatt Papier gezeichnet werden kann, ohne daß sich zwei Kanten schneiden.
  5. Erstellen Sie ein Programm zum Löschen einer Kante aus einem Graph, der mittels Adjazenzlisten dargestellt ist.
  6. Schreiben Sie eine Variante von adjlist, bei der gewährleistet ist, daß die Adjazenzlisten nach der Reihenfolge der Knotenindizes geordnet bleiben. Erörtern Sie die Vorteile dieses Ansatzes.
  7. Zeichnen Sie die Tiefensuch-Wälder, die sich für das Beispiel aus diesem Kapitel ergeben, wenn dfs die Knoten in umgekehrter Reihenfolge (von V rückwärts bis 1) durchsucht, für beide Darstellungsarten.
  8. Exakt wie oft wird visit bei der Tiefensuche in einem ungerichteten Graphen aufgerufen, ausgedrückt über die Anzahl der Knoten V, die Anzahl der Kanten E und die Anzahl der zusammenhängenden Komponenten C?
  9. Geben Sie die Adjazenzlisten an, die erzeugt werden, wenn die Kanten für den Graph aus dem Beispiel in umgekehrter Reihenfolge eingelesen werden wie bei der Erzeugung der Struktur in Abbildung 29.4.
  10. Geben Sie den Tiefensuch-Wald für den Graph aus dem Beispiel in diesem Kapitel an, wenn die rekursive Routine listdfs auf die Adjazenzliste aus der vorangegangenen Übung angewandt wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]