Algorithmen auf Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
Ich habe hier zwei Versionen von Algorithmen zur topologischen Sortierung vor mir liegen, und hätte zwei Fragen dazu:
Algorithmus 1:
[mm]\begin{array}{l}
\texttt{Topological Sorting }(G):\\
\texttt{Input: }G=(V,E),\texttt{ ein gerichteter azyklischer Graph}\\
\qquad\qquad\qquad\qquad\quad\texttt{ mit }n\texttt{ Knoten}\\
\texttt{Output: Topologische Sortierung von }G\texttt{ mittels }\!\operatorname{label}.\\
\textbf{begin}\\
\qquad\texttt{Initialize }v.\operatorname{Indegree}\!\texttt{ for all vertices;}\\
\quad\qquad\qquad\qquad\qquad\texttt{/\* e.g. by DFS \*/}\\
\qquad\texttt{G\_label} := 0;\\
\qquad\textbf{for }i:=1\textbf{ to }n\textbf{ do}\\
\quad\qquad\textbf{if }v_i.\operatorname{Indegree} = 0\textbf{ then}\\
\qquad\qquad\texttt{put }v_i\texttt{ in Queue};\\
\qquad\textbf{repeat}\\
\quad\qquad\texttt{remove vertex }v\texttt{ from Queue};\\
\quad\qquad\texttt{G\_label} := \texttt{G\_label}+1;\\
\quad\qquad v.\operatorname{label} := \texttt{G\_label};\\
\quad\qquad\textbf{for }\texttt{all edges }(v,w)\textbf{ do}\\
\qquad\qquad w.\operatorname{Indegree} := w.\operatorname{Indegree}-1;\\
\qquad\qquad \textbf{if }w.\operatorname{Indegree} = 0\textbf{ then }\texttt{put }w\texttt{ in Queue};\\
\qquad\textbf{until }\texttt{Queue is empty}\\
\textbf{end}
\end{array}[/mm]
Algorithmus 2:
[mm]
\textbf{TopoSort}\left(G\right):
\begin{itemize}
\item 1.) Führe Depth-First-Search zur Berechnung der Endzeiten aller Knoten auf dem Graphen $G$ aus.
\item 2.) Füge jeden abgearbeiteten Knoten an den Kopf einer verketteten Liste ein.
\item 3.) \textbf{return} verkettete Liste
\end{itemize}
[/mm]
Ich habe nun den zweiten Algorithmus ausgeführt und Folgendes erhalten:
[Dateianhang nicht öffentlich]
Wenn ich es richtig verstehe, müßte das die topologische Sortierung sein:
[mm] $v_7, v_{12}, v_{11}, v_{13}, v_{14}, v_8, v_5, v_4, v_6, v_9, v_{10}, v_3, v_2, v_1$
[/mm]
Ich würde nun gerne wissen, ob
(1) der erste Algorithmus identisch mit dem Zweiten ist (nicht vom Ergebnis her, sondern von der Idee).
(2) Außerdem habe ich einige Zweifel, daß ich oben eine topologische Sortierung rausgekriegt habe, da die Indizes der Knoten nicht aufsteigend sind. Andererseits kann ich die Knoten beliebig durchnummerieren.
Danke für eure Hilfe!
Viele Grüße
Karl
P.S.:
(1) Zur Erinnerung:
Eine topologische Sortierung eines gerichteten azyklischen Graphen $G = [mm] \left(V,E\right)$ [/mm] ist eine lineare Anordnung der Knoten von [mm] $G:v_1,\ldots,v_n$, [/mm] so daß [mm] $\left(v_i,v_j\right) \in [/mm] E [mm] \Rightarrow [/mm] i < j$.
(2) Ich habe diese Frage auch ![[]](/images/popup.gif) im Usenet gestellt.
Dateianhänge:
Anhang Nr. 2 (Typ: gif) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:08 So 04.09.2005 | | Autor: | Frank05 |
> Ich habe hier zwei Versionen von Algorithmen zur
> topologischen Sortierung vor mir liegen, und hätte zwei
> Fragen dazu:
[...]
> Wenn ich es richtig verstehe, müßte das die topologische
> Sortierung sein:
>
> [mm]v_7, v_{12}, v_{11}, v_{13}, v_{14}, v_8, v_5, v_4, v_6, v_9, v_{10}, v_3, v_2, v_1[/mm]
![[notok]](/images/smileys/notok.gif "[notok]") Das kann nicht sein. Das widerspricht deiner Def. weiter unten.
Betrachten wir die Kante von [mm]v_9[/mm] nach [mm]v_7[/mm]. In deiner Sortierung waeren das jetzt die Knoten 10 und 1 und wir haben eine Kante von 10 nach 1 woraus folgt, dass [mm]10<1[/mm].. oder eben auch nicht.
Inhaltlich macht das natuerlich auch keinen Sinn. Diese Kante stellt ja gerade eine Abhaengigkeit dar und besagt quasi 'bitte erst [mm]v_9[/mm] behandeln, bevor [mm]v_7[/mm] dran ist'.
Aber wenn du deine Sortierung einfach umdrehst hast du eben diese lineare Anordnung, die du suchst.
> (1) der erste Algorithmus identisch mit dem Zweiten ist
> (nicht vom Ergebnis her, sondern von der Idee).
(Ich setze voraus, dass auch fuer Algo2 die Eingabe beschraenkt sein soll auf einen DAG)
Ja und Nein.
Nein: Die Reihenfolge in der das Ergebnis aufgebaut wird unterscheidet sich. Beim ersten wird der erste Knoten des Ergebnisses auch als erster Knoten in die Liste eingetragen, beim zweiten als letzter (jeweils auf eine Zusammenhangskomponente bezogen natuerlich).
Dass sich das Ergebnis unterscheiden kann ist denke ich klar (da die topo.Sort. nicht eindeutig ist und 'for all edges' ebenfalls nicht)
Ja: Wenn du von einem Algo. zum andern kommen willst kannst du einfach den inversen Graph betrachten (also alle Kantenrichtungen umdrehen). Dann werden Knoten mit indegree = 0 zu den Knoten, die in der BFS vorher abgearbeitet werden und umgekehrt Knoten, die vorher in der BFS zuerst abgearbeitet wurden haben dann indegree = 0.
> (2) Außerdem habe ich einige Zweifel, daß ich oben eine
> topologische Sortierung rausgekriegt habe, da die Indizes
> der Knoten nicht aufsteigend sind. Andererseits kann ich
> die Knoten ja so durchnummerieren wie mir beliebt.
Anstatt die Knoten zu nummerieren benenn sie doch einfach mit Stadtnamen, oder mit Farben oder mit Fruechten oder sonstigen Abartigkeiten  .. es spielt keine Rolle! Die topo.Sort. ist (vgl. Def.) lediglich eine Anordnung. Niemand hat behauptet, dass die Anordnung was mit Indizes zu tun haben muss.
Was dich vielleicht verwirrt ist, dass man haeufig eine topo.Sort. durchfuehrt und danach die Knoten neu bennent (naemlich anhand ihrer Reihenfolge in der gefundenen Anordnung).
> Eine topologische Sortierung eines gerichteten azyklischen
> Graphen [mm]G = \left(V,E\right)[/mm] ist eine lineare Anordnung der
> Knoten von [mm]G:v_1,\ldots,v_n[/mm], so daß [mm]\left(v_i,v_j\right) \in E \Rightarrow i < j[/mm].]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:57 Di 06.09.2005 | | Autor: | Karl_Pech |
Hallo Frank,
Danke für deine Antwort! Ich übe das Ganze jetzt nochmal, und melde mich, wenn etwas nicht klappt.
Viele Grüße
Karl
|
|
|
|
