Tiefensuche - Eulerkreis < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 11:11 Mi 10.11.2004 | | Autor: | mausi |
so ne schwere aufgabe bitte mal helfen!!!!heul
Mit dem Algorithmus Euler kann bestimmt werden,ob ein
Eulerkreis in einem Graph existiert.Entwickeln Sie aus dem folgenden informalen Algorithmus,
der in einem Graph den Eulerkreis ermittelt,eine Pseudocodenotation.Beschreiben Sie auch die
von Ihnen genutzten ADTs und deren Operationen.
Algorithmus zur Bestimmung des Eulerkreises (Annahme:es existiert ein Eulerkreis):
1.Nimm einen Knoten x mit einer noch nicht betrachteten Kante.
2.Konstruiere über eine Tiefensuche (depth-first-search)einen Kreis Kx (bis alle Kanten von x
verbraucht sind).
3.1.Nimm den ersten Knoten y aus Kx,der noch nicht besuchte Kanten hat.
3.2.Konstruiere über Tiefensuche einen Kreis Ky (bis alle Kanten von y verbraucht sind).
3.3.Füge diesen Kreis Ky in Kx ein.
3.4.Gehe zu 3.1.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:51 Mi 10.11.2004 | | Autor: | mausi |
also ich hab mal ne pseudocodenotation zum eulerkreis und zur tiefensuche
Algorithmus: Eulerkreis
FÜR i := 1 BIS Knotenzahl WIEDERHOLE
Kantenzahl [i ] := 0;
ENDE_WIEDERHOLE
FÜR i := 1 BIS Knotenzahl WIEDERHOLE
FÜR j := 1 BIS Knotenzahl WIEDERHOLE
WENN Kante von i nach j existiert
DANN Kantenzahl [i] := Kantenzahl [i] + 1;
ENDE_WIEDERHOLE
ENDE_WIEDERHOLE
i := 0;
WIEDERHOLE
i := i+ 1;
WENN Kantenzahl [i] gerade
DANN Eulerkreis := TRUE
SONST Eulerkreis := FALSE;
BIS (NOT Eulerkreis) ODER (i = Kantenzahl);
WENN Eulerkreis
DANN Ausgabe : "Eulerkreis existiert"
SONST Ausgabe : "Eulerkreis exisitiert nicht"
so und nu tiefensuche
Tiefensuche (Depth-First Search)
DFS
---
Vorbedingung: G ist ein gerichteter Graph mit n Knoten
fuer u = 0 bis n - 1
color[u] = white
setze index = n - 1
fuer u = 0 bis n - 1
falls color[u] = white
setze index = DFS-visit(u,color,index,sort)
Nachbedingung: sort[0..n-1] ist eine topologische
Sortierung von G
DFS-visit(u,c,i,s)
------------------
setze c[u] = gray
setze a = arrayOfAdjacentVertices(u)
fuer j = 0 bis a.length - 1
setze v = a[j]
falls color[v] = white
setze i = DFS-visit(v,c,i,s)
setze c[u] = black
setze s[i] = u
gib i - 1 zurueck
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:07 Sa 20.11.2004 | | Autor: | Eva |
Hallo Mausi,
tut mir leid, es kann Dir keiner mit Deiner Frage hier weiterhelfen ![[sorry]](/images/smileys/sorry.gif "[sorry]") .
Da die Fälligkeit bereits abgelaufen ist, gehe ich davon aus, dass Du an einer Antwort nicht mehr interessiert bist.
Viele Grüße,
Eva
|
|
|
|
