Posts by toblinga

ich auch nicht, das war echt eine klasse idee!

Is im prinzip nichts anderes als testen ob 2-Zusammenhängender Graph....

DANKE!

Ich glaub auch dassn dieser Code Teta(n^2) hat, da das was i kleiner wird vernachlässigbar ist.

michaelh:
Wenn in der 2. (inneren) Schleife eine Konstante laufzeit hat, die nicht von n abhängig ist, dann ist es egal, wie z.B. dein 2. Besipiel ansonsten ist jede Schleife relevant...

Na sollte das selbe sein...

stimmt
ich hab mal wieder falsch gedacht ...

Ich würde Selectionsort verwenden...

Kommentare?

Quote from kaltra

Wenn Du Dich in C befindest, muss Du pop() aufrufen, um wieder zu B zu gelangen. (Beachte: C wurde nie abgelegt... Du musst es Dir ja nie für Rücksprünge merken. siehe unten)
Deswegen gibt es ja den Stack, um sich Knoten für "Rücksprünge" merken zu können.
Um bei Bedarf wieder zu B zurückkehren zu können, muss ich ihn mir BEIM VERLASSEN wieder mit push(B) ablegen

Na das hast du falsch verstanden, lies dir einfach den Post von IRBaboon (ober von mir aus einem anderem Thema zitiert) durch. Da ist alles beschrieben. Da Baboon LVA Leiter von AlgoDat ist, glaube ich, dass das gesetzt ist was er uns hier im Forum mitteilt.

Wieso, pop'st du das erste mal B?
push(A) => push(B) => push(C) [hier geht es nicht mehr weiter also zurück]POP(C) [jetzt sind wir wieder bei B] push(D)=>push(E)=>push(F)[selbe Geschichte wie bei C, geht nicht mehr weiter also zurück] pop(F)...usw.

Glaube dass man der Lösung von IRBaboon 100% vertrauen kann

Quote

Der Link ist leider immer noch falsch (es steht zwar richtig da, aber verweist immer noch auf eine Pruefung im Jahre 2006), und du interessierst dich wohl fuer Bsp. 4A, nicht 2A.

Tja, kurz gesagt:
Tiefensuche: Man startet bei einem Knoten, markiert alle Knoten, die man besucht, und geht immer so lange weiter, bis man nicht mehr weiter kann. Backtracking = so lange zurueck gehen, bis man einen Knoten findet, wo noch nicht alle Nachbarn besucht (markiert) wurden, und dort das Spielchen fortsetzen, bis man alle Knoten markiert hat, die vom Startknoten aus erreichbar sind.
Breitensuche: Markiere Startknoten und lege alle von ihm direkt (also ueber eine Kante) erreichbaren Knoten in eine Queue (first in first out) und markiere sie ebenfalls. Dann entnimmt man aus der Queue das erste Element und macht das selbe Spielchen wieder: alle direkt erreichbaren Knoten, die noch nicht markiert sind, in die Queue stecken und markieren. Naechster Knoten in der Queue: ..., solange, bis die Queue leer ist.

Bsp. 4A (20070130): Tiefensuche, Startknoten A, Nachbarschaftsfunktion liefert benachbarte Knoten in lexikographischer Ordnung:
A --> B --> C --> (back) --> D --> E --> F --> (back) --> G --> H --> J --> I --> (back) --> K --> L --> M --> (back) --> (back) ... (schon alle Knoten besucht, Backtracking bis zum Startknoten A zurueck).

Breitensuche, Startknoten A, gleiche Nachbarschaftsfunktion (e() = enqueu, d() = dequeue):
e(A) // Initialisierung
d() // --> A (erstes Element der Queue wird entnommen, das ist das A)
e(B)
e(G) // alle Nachbarn von A abgearbeitet
d() // --> B
e(C)
e(D)
d() // --> G
e(E)
e(H)
d() // --> C (nothing to do)
d() // --> D
e(K) // E ist schon besucht worden und ist daher schon markiert)
d() // --> E
e(F)
...

Jetzt klar?

I.R.Baboon

Display More

was ich nicht verstehe bei dir , warum du push(b) pop() push(b) Also warum nimmst du B und E 2 mal in stack auf?

ja hast recht
deine variante schaut gut aus,
was mir jedoch in der angabe fehlt ist die Durchmusterungsreihenfolge...

ich hab mir das so überlegt:
3+4*5/6

......*
..+..../
3..4.5..6

Danke fürs suchen, jezt wissen wird ganz genau

Hallo,
hat das jemand schon durchgedacht, bzw. eine Lösung?

Danke schon mal im Voraus...

danke, da ich jetzt den unterschied kenne ist mir das klarer

thx!

Du schreibst:
...
enq(E)
enq(K)

Ich würde
...
enq(E)
enq(H)

Quote from michaelh

ich komm auf folgendes:

enq(A)
deq()
enq(B)
enq(G)
deq()
enq(C)
enq(D)
deq()
deq()
enq(E)
enq(K)
...

warum nimmst du wieder einen runter?? nachdem du K raufgegeben hast??
kannst du mir das nochmals erklären?

Display More

enq(K) oder enq(H) in der lezten zeile?

Hallo!

schaft die jeamd, da steh ich voll auf der Leitung
Ich bekomm den beknackten baum nicht hin

Danke für eure Hilfe

ich steh vieleicht auf der leitung, aber mir fehlen bei den operationen E und H... müssten die nicht vor K kommen?

Hallo!
wollte kurz fragen ob jemand den Pseudocode für diese Aufgabe geschrieben hat...

Subordinates(m,num){
anz = 0;
h=NULL;
falls m.vg != NULL {
h=m.nv;
solange h.koll != NULL{
anz++;
h=h.koll;
}
}
falls anz >= num
Ausgabe m.name;
falls m.koll != NULL
Subordinates(m.koll,num);
Subordinates(m.vg,num);
}

Kann mir da bitte jemand seine Meinung sagen

Thx!

Quote from enemy2k

und hier noch einmal mit der Breitensuche....

enq(A)
deq()
enq(B)
enq(G)
deq()
enq(C)
enq(D)
deq()
deq()
enq(K)
deq()
enq(F)
deq()
enq(J)
deq()

{A,B,G,C,D,E,H,K,F,J,......}

Display More

Bei der folge {A,B,G,C,D,E,H,K,F,J,......} kann ich dir folgen hab ich das selbe wie du, jedoch wie kommst du auf die Queueoperationen?

Die Tiefensuche hab ich auch identisch, auch die push und popÄS

Quote from Lidi

minimale Höhe : 1

maximale Höhe : ld(2^m) = m

Stimmt das so???

Ich denke dass der auch total unbalaciert sein kann also kann er n hoch werden. Da m-Abhängig wäre meine antwort (2^m)-1
Bin mir nicht sicher ob man noch 1 für die Wurzel wegrechnen muss... also (m^2)-2