Într-un prim arbore de adâncime, există marginile care definesc arborele (adică marginile care au fost utilizate în traversare).
Există câteva margini rămase care leagă unele dintre celelalte noduri. Care este diferența dintre o margine transversală și o margine frontală?
Din Wikipedia:
Pe baza acestui arbore întins, marginile din graficul original poate fi împărțit în trei clase: muchiile înainte, care indică de la un nod al copacului la unul dintre descendenții săi, muchiile posterioare, care indică de la un nod la unul dintre strămoșii săi și muchiile transversale, care nu fac niciuna. Uneori marginile copacilor, marginile care aparțin copacului însuși, sunt clasificate separat de marginile anterioare. Dacă graficul original nu este direcționat, atunci toate marginile sale sunt margini de copac sau margini din spate.
Nu este o margine care nu este utilizată în traversare care punctele de la un nod la altul stabilesc o relație părinte-copil?
Comentarii
- În legătură: cs.stackexchange.com/questions/99988/… caută să stabilească un algoritm care, pentru un grafic direcționat, va prefera să facă margini înainte, în loc de muchii transversale, în timpul prima căutare în profunzime.
Răspuns
Wikipedia are răspunsul:
Toate tipurile de margini apar în această imagine. Urmăriți DFS pe acest grafic (nodurile sunt explorate în ordine numerică) și vedeți unde intuiția eșuează.
Acest lucru va explica diagrama: –
Marginea din față: (u, v), unde v este un descendent al lui u, dar nu o margine de copac .Este o margine non-copac care conectează un vârf la un descendent dintr-un arbore DFS.
Marginea transversală: orice altă margine. Poate merge între vârfuri în același copac cu adâncime sau în copaci cu adâncime diferită. (layman)
Este orice altă margine din graficul G. Conectează vârfuri în doi arbori DFS diferiți sau două vârfuri în același arbore DFS, nici unul dintre strămoși al celuilalt. (formal)
Comentarii
- De ce nu este imposibil ca 6 să fie traversate mai întâi (partea dreaptă mai întâi)? Dacă s-ar fi întâmplat așa, cum s-ar fi numit marginea 2- > 3?
- @soandos, vă sugerez să vă faceți timp pentru a urmări algoritmul. Presupunând că Wikipedienii ‘ nu au făcut o greșeală, imaginea descrie o rulare de bună-credință a DFS pe acest grafic și, prin urmare, există o modalitate de a încadra algoritmul în această urmă. Tipurile de margini sunt descrise suficient de clar în Wikipedia și puteți consulta și acest exemplu.
- Înțeleg că acesta este un mod valid de a face un DFS. Pur și simplu întreb ce dacă s-a făcut în sens invers.
- Apoi, rezultatele ar fi diferite. Îmi ‘ îmi pare rău, ‘ ar trebui să îl rezolvați singur.
- @soandos În general, există poate fi foarte bine traversări DFS multiple. Noțiunile utilizate aici sunt relative la una dată traversare și vor diferi pentru mai multe traversări.
Răspuns
O traversare DFS într-un grafic nedirecționat nu va lăsa o margine transversală deoarece toate marginile care sunt incidente pe un vârf sunt explorate.
Cu toate acestea, într-un grafic direcționat, puteți întâlni o margine care duce la un vârf care a fost descoperit înainte astfel încât acel vârf să nu fie un strămoș sau descendent al vârfului actual. O astfel de margine se numește margine transversală.
Comentarii
- Aporov, Vă mulțumim pentru răspuns. Încă mi se pare că atunci când ajungi la vârful 6 în DFS așa cum este diagramat în Wikipedia, ai trei margini de parcurs de la 6. În acel moment, vârful 6 este ” curent „. În cele din urmă veți traversa marginea până la vârful 3. Deși 3 a fost deja vizitat, totuși, deoarece există o margine de la 6 la 3, atunci 3 este un descendent al curentului ” ” vertex 6. Dacă este așa, încalcă definiția unei muchii transversale. Trebuie să existe ceva mai mult la definiție care să nu fie ‘ t făcându-se foarte explicit.
- De fapt, DFS conține doar margini de arbore pentru marginile din spate (Introducere în Algoritmi Thm. 22.10).
Răspuns
Într-o traversare DFS, nodurile sunt terminate odată ce toți copiii lor sunt terminat. Dacă marcați timpii de descoperire și de terminare pentru fiecare nod în timpul traversării, puteți verifica dacă un nod este descendent comparând timpii de început și de sfârșit. De fapt, orice traversare DFS își va partiționa marginile conform următoarei reguli.
Fie d [nod] timpul de descoperire al nodului, la fel să fie f [nod] timpul de finalizare.
Teorema parantezei Pentru toate u, v, se aplică exact una dintre următoarele:
1.d [u] < f [u] < d [v] < f [ v] sau d [v] < f [v] < d [u] < f [u] și nici unul dintre u și v nu este descendent al celuilalt.
d [u] < d [v] < f [v] < f [u] și v este un descendent al lui u.
d [v] < d [u] < f [u] < f [v] și u este un descendent al lui v.
Deci, d [u] < d [v] < f [u] < f [v] nu se poate întâmpla.
Like paranteze: () [], ([]) și [()] sunt OK, dar ([)] și [(]) nu sunt OK.
De exemplu, luați în considerare graficul cu margini:
A -> B
A -> C
B -> C
Fie ca ordinea de vizitare să fie reprezentată de un șir de etichete de noduri, unde „ABCCBA” înseamnă A -> B -> C (terminat) B (terminat) A (terminat), similar cu ((())).
Deci „ACCBBA” ar putea fi un model pentru „(() ())”.
Exemple:
„CCABBA”: Apoi A -> C este o cruce muchie, deoarece CC nu este în interiorul lui A.
„ABCCBA”: Atunci A -> C este o margine înainte (descendent indirect).
„ACCBBA”: Atunci A -> C este o margine de copac (descendent direct).
Surse:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm