[Scârțâit] [CLIC] [SCRÂȘIT] [FOȘIT] [CLIC] JUSTIN SOLOMON: Tocmai am început o nouă unitate despre teoria grafurilor, care va fi un fel de concentrare pentru următoarele două prelegeri din 6006. Și așa m-am gândit i-am revedea puțin la începutul prelegerii pentru că, ca de obicei, am amestecat multe noțiuni în prelegerea noastră anterioară, apoi am început cu câteva idei noi. Deci, practic, în prelegerea noastră anterioară, am vorbit despre un algoritm numit căutare pe lățimea întâi. Și apoi, aproape întotdeauna, îl vedeți asociat cu un al doilea algoritm numit căutare în profunzime. Și urmând tradiția și, în principiu, logica, vom face același lucru în 006 astăzi. Dar, în orice caz, pentru astăzi vom rămâne la materialul tehnic. Deci, ca o mică revizuire, cred că, de fapt, singurul lucru pe care nu l-am făcut pe acest diapozitiv a fost de fapt să desenez un grafic. Deci probabil că ar trebui să începem cu asta. Deci, dacă vă amintiți, graficul este o colecție de noduri sau vârfuri în funcție de -- nu știu, este ca o chestie europeană americană sau așa ceva -- și margini. Așa că iată un exemplu, pe care, ca de obicei, nu reușesc să-l desenez foarte clar. Deci acest grafic este un fel ca un ciclu. Așa că am direcționat margini aici, aici, aici și aici. Și, desigur, există multe tipuri de variații ale temei, nu? Deci tipul nostru de bază de definiție a unui graf este că avem o mulțime V, care este ca și mulțimea de vârfuri. Și apoi avem o mulțime E, care este un set de muchii. Și acesta a fost un subset al crucii V V. Și aceasta nu este altceva decât o notație fantezică pentru a spune că o muchie este o pereche de vârfuri, ca de la și a până la vârf. Desigur, există multe variații pe această temă. Ați putea avea un grafic direcționat versus un grafic nedirecționat. Deci, acesta este direcționat, adică marginile arată ca săgeți. Dacă nu ar avea vârfuri de săgeți, ar fi nedirecționați. Definim ceva numit un grafic simplu în care în esență nu aveți muchii repetate. Deci, de exemplu, nu puteți face așa ceva în cazul în care aveți aceeași margine de două ori. Și apoi există câteva definiții diferite care au fost oarecum utile. Deci, în special, o să șterg asta, hopa... margine inutilă aici. Poate face graficul meu puțin mai interesant. Așa că adăugați o altă margine mergând în direcția inversă. Deci, poate că am... O să-mi dau etichete vârfurilor. x, y, z și w. Apoi am vorbit despre vecinii unui punct dat, care sunt vârfurile pe care le puteți ajunge urmând muchiile în interiorul sau în afara nodului dvs. Deci, în special, vecinii care ieșesc, pe care i-am definit implicit în prelegerea anterioară, dar nu i-am numit, îi vom nota cu Adj+. Și acestea sunt toate lucrurile la care poți ajunge ieșind dintr- un vârf în următorul. Deci, de exemplu, Adj+ din w va fi mulțimea de vârfuri. Vom observa că pot ajunge de la w la y și, de asemenea, de la w la z. Da. Asa de. Nu, nu. y virgula z. BINE. Așa că, pentru a continua doar mica noastră recenzie pentru ziua respectivă, amintiți-vă că un grafic - există multe moduri diferite de a reprezenta un grafic. Genul de moarte cerebrală ar fi la fel ca o listă mare și lungă de margini. Dar, desigur, pentru algoritmii noștri nu este o modalitate deosebit de eficientă de a verifica lucruri precum, există această margine în graficul meu. Așadar, reprezentarea de bază la care cred că lucrăm în principal în acest curs este să ne gândim la un grafic ca un set de vârfuri, fiecare dintre ele mapându-se la un alt set de vârfuri. Deci, aproximativ fiecare vârf poate stoca setul său de margini de ieșire. Și deci acest lucru este destul de drăguț pentru că, desigur, foarte repede putem răspunde la întrebări precum, această margine este în interiorul graficului nostru? Sau putem itera peste vecinii unui vârf și așa mai departe, care sunt genul de lucruri tipice pe care le facem în mulți algoritmi grafici. Și apoi, în cele din urmă, în prelegerea noastră anterioară, am început să vorbim despre căi. Deci o cale este ca un lanț de vârfuri care mă poate duce de la un vârf la altul doar urmând marginile graficului meu. Există un termen pe care cred că am uitat să-l definesc data trecută pentru că nu prea a contat o tonă, care este o cale simplă, care este doar o cale care nu are același vârf de mai multe ori. Și apoi, desigur, există multe întrebări diferite pe care le-ați putea pune despre un grafic, care sunt în principiu probleme diferite care implică căi de calcul. Deci, de exemplu, cea mai scurtă cale dintre două vârfuri este un fel de cea canonică în teoria grafurilor. Sau puteți pune întrebări despre accesibilitate și așa mai departe. Deci, există recenzia noastră de bază din prelegerea noastră anterioară. Personalul nostru de curs are întrebări despre lucruri de până acum? Excelent. BINE. Și mai există o terminologie suplimentară pe care l-am înșelat puțin data trecută -- sau mai degrabă, co-instructorul meu a sugerat o mică modificare a atitudinii. Așa că m-am gândit că ar fi bine să clarific foarte repede. Există această frază interesantă, timpul liniar, pe care o cunoaștem și o iubim cu toții în teoria informatică. Și acest tip de lucru implicit, mai ales în acest curs, este că atunci când spunem timp liniar, ne referim la dimensiunea intrării. Dreapta? Și deci, dacă avem un algoritm de grafic de timp liniar, ei bine, cât spațiu este nevoie pentru a stoca un grafic? Ei bine, avem nevoie de o listă de vârfuri și o listă de muchii, dacă nimic altceva. Deci, o modalitate rezonabilă de a interpreta această expresie de timp liniar este că este un algoritm care arată ca ceea ce am arătat pe ecran. Timpii proporționali poate cu suma numărului de vârfuri și a numărului de muchii. Dacă asta te face să te simți inconfortabil, așa cum o face pentru mine, deoarece una dintre acestea se poate cam scala pe cealaltă, cred că întotdeauna este bine să adaugi mai multe detalii. Dreapta? Deci, dacă vrei să spui, liniar în suma numărului de vârfuri și muchii, e perfect. Dar dacă vezi această frază, așa ar trebui să o interpretezi. Sper că acesta este un mod corect de a spune. Excelent. BINE. Deci data trecută, am vorbit despre un algoritm numit breadth-first search -- BFS, pentru cei care știu. Căutarea pe lățime este un algoritm. Și motivul pentru care folosim cuvântul lățime este pentru că este un fel, amintiți-vă, am vorbit despre seturi de nivel data trecută pentru că am vorbit despre căutarea pe lățime, în contextul calculării celor mai scurte căi. Și, în special, avem nodul nostru sursă pe tot drumul în partea stângă. Și apoi căutarea pe lățime a construit toate nodurile care se aflau la distanța 1. Dreapta. Acesta este primul nivel stabilit, apoi toată distanța 2 distanță, apoi toată distanța 3 distanță și așa mai departe. Deci, în special, setul de nivel L3 nu este vizitat până când nu terminăm complet cu setul de nivel L2. Astăzi, vom defini un alt algoritm, care se numește căutarea depth-first, care nu face asta, ci mai degrabă începe cu primul său vârf și pur și simplu începe să meargă până la capăt până când nu mai poate face asta. . Și apoi se cam întoarce înapoi. Acesta este un mod de a gândi. Și așa că, într-un fel, în căutarea pe lățimea mai întâi, desenăm cercuri concentrice. În căutarea în profunzime, facem invers. Ne-am gândit să tragem în afară până ajungem la limita exterioară, apoi explorăm graficul în acest fel. BINE. Și acestea sunt un fel de cele două extreme în ceea ce privește genul de tehnici de căutare în graf, care sunt utilizate în mod obișnuit în cadrul blocurilor de bază pentru algoritmi în teoria grafurilor. Deci, pentru a motiva și a gândi la căutarea în profunzime, vom defini o a doua problemă, care este strâns legată de calea cea mai scurtă , dar nu exact aceeași. Și aceasta este problema accesibilității. Așa că aici am cel mai simplu grafic direcționat din lume. Deci lucrurile negre sunt marginile. Iar cercurile sunt nodurile sau vârfurile. Și am marcat un nod special cu albastru. Și numele lui este nodul sursă. Și acum întrebarea pe care vreau să o pun este, care sunt toate celelalte noduri din graficul meu la care pot ajunge urmând margini -- margini direcționate -- începând cu sursa? Deci, evident, pot ajunge la nodul din dreapta jos, nicio problemă. Și bineînțeles, odată ce ajung acolo, pot traversa și pot trece în sus pentru a ajunge la acel al doilea vârf verde. Observați că am fost cu adevărat furtun și rău și am desenat margini în acest grafic care ar putea să vă facă să credeți că nodul roșu este accesibil. Cel roșu fiind în stânga sus. Îmi dau seama acum că pentru persoanele daltoniste, acesta nu este un diapozitiv grozav. Dar, desigur, pentru că toate marginile de la vârful roșu din stânga aici arată, nu pot ajunge la el de la nodul sursă albastru. Deci problema accesibilității este doar întrebarea la ce noduri pot ajunge de la o anumită sursă? Destul de simplu, cred. Desigur, există multe modalități de a rezolva acest lucru. Dreapta? De fapt, o modalitate prin care am putea face acest lucru ar fi să folosim prelegerea noastră anterioară. Am putea calcula cea mai scurtă distanță de cale de la sursă la toate celelalte noduri. Și atunci care ar fi lungimea celei mai scurte căi de la sursă la un nod inaccesibil? Vreo părere de la publicul nostru aici? Infinit. Mulțumesc, domnule profesor Demaine. Dreapta. Deci, pe lângă aceasta, desigur, o întrebare total rezonabilă , gândindu-ne la prelegerea noastră pe calea cea mai scurtă, există un fel de două întrebări pe care le-am putea face. Dreapta? Unul este doar care este lungimea drumului cel mai scurt? Celălalt este ca, care este cea mai scurtă cale reală de la sursă la un punct dat? Putem întreba un lucru foarte asemănător aici, și anume, OK. Îmi spui că tipul verde este accesibil, dar cum? Dă-mi o cale ca dovadă sau certificat, dacă vrei să fii fantezist. Deci, pentru a face asta, la fel ca data trecută, amintiți-vă, am definit o anumită structură de date care a fost arborele cu calea cea mai scurtă. Putem face ceva foarte asemănător aici. În special, aceasta este ca amploarea abilităților mele PowerPoint aici. Dacă am o problemă de accesibilitate, mai pot stoca -- pot decora fiecare nod din graficul meu cu o altă informație, care este nodul anterior de-a lungul unei căi de la sursa mea la acel lucru. Dreapta? Și la fel ca data trecută, dacă vreau să obțin o cale reală de la sursă la w, ce aș putea face? Pot să încep cu w și apoi să continui să urmăresc acele relații cu părinții până mă întorc la sursă. Apoi, dacă răsturn ordinea acelei liste de vârfuri, primesc o cale de la sursă la țintă care este validă. Deci, acest obiect se numește arbore de căi, așa cum am vorbit, sau mai degrabă arbore părinte. Așa cum am vorbit în ultima noastră prelegere, nu există niciun motiv pentru care acest lucru ar trebui să aibă vreodată un ciclu în el. Cu siguranță este un copac. Dreapta. Deci, aceasta este problema de bază a accesibilității. Și în plus, putem calcula acest obiect P, care îmi va oferi un fel de informații despre cum a fost accesibil orice nod dat. Există o mică diferență între arborele părinte pe care l-am definit aici și arborele cu calea cea mai scurtă, pe care l- am definit data trecută, și anume, nu voi cere ca cea mai scurtă cale pe care o primesc... oh, omule... calea pe care o primesc atunci când dau înapoi de-a lungul copacului meu P este calea cea mai scurtă, este doar o cale pentru că pentru problema accesibilității, de fapt nu-mi pasă. Aș putea avea un drum lung ciudat, întortocheat și nebunesc. Și încă îmi spune că un nod este accesibil. Dreapta. Deci aceasta este configurația noastră de bază și structura noastră de date. Și acum putem introduce o problemă pentru a rezolva accesibilitatea. Din nou, avem deja un algoritm pentru a face asta, care este să calculăm cele mai scurte căi. Și amintiți-vă că algoritmul nostru cu calea cea mai scurtă din prelegerea anterioară a luat timp liniar și dimensiunea intrării. A luat v plus e timp. Acum întrebarea este, putem face ceva mai bine? Răspunsul, evident, este da, pentru că tocmai l-am întrebat și ți-am dat această problemă. BINE. Și iată o tehnică pentru a face asta, care, fără a fi surprinzător, este un algoritm recursiv. O să-mi schimb notele cu notele scrise de mână. Și acest algoritm se numește căutarea în profunzime. Și iată strategia de bază. Voi alege un nod sursă și voi eticheta acel Nod 1 aici. Presupun că de fapt ar fi avut sens pentru mine să indexez acest lucru. Poate că în slide-uri o voi repara mai târziu. Dar, în orice caz, îmi voi marca nodul sursă. Și acum mă voi uita la fiecare nod, fiecare margine care iese din acel nod și o voi vizita recursiv. Așa că acesta este un fel de buclă for din cadrul acestei vizite de funcție. Și apoi pentru fiecare nod vecin, dacă nu l-am vizitat înainte, cu alte cuvinte, momentan nu i-am dat un părinte. Aceasta este declarația noastră if aici. Atunci o să spun, ei bine, acum au un părinte. Și acel părinte sunt eu. Și o să recurg. Vedeți băieți ce face asta? Se cam târăște spre exterior în interiorul graficului nostru. Deci, să facem exemplul pe ecran. Și am conceput intenționat acest experiment -- sau acest exemplu -- pentru a arăta puțin diferit de căutarea pe lățime, cel puțin dacă alegeți să faceți comanda pe care am făcut-o. Deci, iată graficul nostru. 1, 2, 5, 3, 4. OK. Și să ne gândim la ordinea de traversare pe care o va face căutarea în profunzime. Dreapta. Deci, iată sursa noastră. Și acum ce face sursa? Este rec... deci să ne gândim la arborele nostru recursiv. Deci avem sursa până aici. Și acum va începe să apeleze recursiv funcția de vizită. Asa de. Și voi continua și le voi numerota la fel ca pe ecran. Ei bine, el are un vecin ieșitor și nu a fost încă vizitat. Deci, desigur, primul apel recursiv pe care îl voi face este către acel vecin 2. Acum și vecinul 2 recurs. Sper că acest tip de imagine schematică are ceva sens, ceea ce încerc să desenez aici. Și ei bine acum, 2 are doi vecini, un 3 și un 5. Deci să zicem că alegem mai întâi 3. Ei bine, 3 recurs acum și apelează 4. Și apoi arborele recursiv este oarecum terminat. Deci acum se stinge din nou. Și apoi, în sfârșit, ei bine, acum, cei 3-- sau, oh, băiete. Da. Cel 2 se uită la următorul său vecin, care este 5 și îl vizitează recursiv. Observați că acest lucru nu respectă seturile de nivel. Dreapta? Algoritmul de căutare în profunzime a ajuns până la sfârșitul arborelui meu în apelurile recursive și apoi s-a cam dat înapoi la 2 înainte de a apela 5. Acestea nu sunt aceeași tehnică. Unul merge până la capăt și apoi se cam întoarce înapoi. Când spun înapoi, ceea ce vreau să spun este că recursiunea este un fel de dezlegare. În timp ce în căutarea pe lățimea întâi, vizitez totul într-un singur nivel înainte de a-mi găsi calea de ieșire. Are sens această distincție? BINE. Deci, desigur, trebuie să demonstrăm că acest algoritm face ceva util. Deci hai să facem asta acum. Deci, în special, avem nevoie de o dovadă a corectitudinii. Deci afirmația noastră va fi aceea că - să vedem aici - algoritmul de căutare în profunzime vizitează toate, cred că v poate fi accesibil și că setează corect părintele în proces. BINE. Deci, pentru a demonstra acest lucru, bineînțeles, la fel ca în aproape orice în acest curs, vom folosi inducția. Și în special, ceea ce vom face este să facem inducție pe distanța de la sursă. Deci vom spune că, de exemplu, pentru toate nodurile aflate la distanța k de la sursă, această afirmație este adevărată. Și apoi vom demonstra acest lucru inductiv pe k. BINE? Deci vrem să facem inducție pe k, care este distanța până la vârful sursă. Deci, ca și în cazul tuturor dovezilor noastre inductive, trebuie să facem cazul nostru de bază și apoi pasul nostru inductiv. Deci, în cazul de bază, k este egal cu 0. Acesta este un caz foarte ușor pentru că, desigur, care este lucrul care este distanța 0 de sursă? Este sursa! Da. Și aruncați o privire la strategia noastră până în partea de sus a slide-ului. Am stabilit în mod explicit părintele corect pentru sursă și, într-un anumit sens, îl vizităm, deoarece primul lucru pe care îl facem este să numim vizita lui s. Deci nu e nimic de spus aici. Da? Sau sunt multe de spus dacă o scrii pe teme. Dar instructorul tău leneș va scrie o bifă aici. BINE. Așa că acum trebuie să facem pasul nostru inductiv. Deci ce înseamnă asta? Vom presupune că afirmația noastră este adevărată pentru toate nodurile aflate la o distanță k. Și apoi vom demonstra că același lucru este adevărat pentru toate nodurile aflate la o distanță k plus 1. OK. Deci hai să facem asta. Să considerăm un vârf v care este distanța k plus 1. Deci, cu alte cuvinte, distanța de la sursă la v este egală cu k plus 1. Și care este scopul nostru? Scopul nostru este să arătăm că părintele lui v este setat corect. Da? Ce a fost asta? PUBLIC: [INAUDIBIL]. JUSTIN SOLOMON: Oh, scuze. Am uitat că distanțele din această clasă sunt în ordine. Da. Este absolut corect. Deci ar trebui să fie distanța de la s la v. Da. Îmi pare rău. Chiar nu sunt obișnuit să mă gândesc la graficele direcționate. Dar asta e o soluție bună. BINE. Deci acum ce putem face? Ei bine, acest număr este distanța aici. Deci, în special, cea mai scurtă cale de la s la v. Amintiți-vă de argumentul nostru data trecută că, în esență, când ne uităm la calea cea mai scurtă și trunchiem cu 1, este încă cea mai scurtă cale? Acea proprietate nu contează atât de mult aici. Dar cel puțin știm că există un alt vârf pe cale, care este la o distanță de unul mai puțin. Deci, să luăm u, care este, de asemenea, un vârf, ca fiind nodul anterior pe calea cea mai scurtă de la s la v. Dreapta. Și astfel, în special, știm că distanța de la s la u este egală cu k. Și în mod convenabil, desigur, prin ipoteza noastră inductivă de aici, știm că proprietatea noastră este adevărată pentru acest tip. BINE. Deci acum algoritmul nostru, ce știm? Ei bine, pentru că proprietatea noastră este adevărată, funcția de vizită la un moment dat în viața sa este numită pe acest vârf u. Cam asta presupune inducția noastră. Deci avem două cazuri. Dreapta. Deci, atunci când vă vizităm, știm că atunci când numim această funcție de vizită, ei bine, amintiți-vă că v, prin definiție, este în Adj+ din u. Dreapta. Deci, în special, DGS va lua în considerare v atunci când este apelat. BINE. Și acum sunt două cazuri. Dreapta? Deci, fie atunci când se întâmplă acest lucru, P din v nu este egal cu None. Dreapta. Ei bine, ce înseamnă asta? Ei bine, înseamnă că am găsit deja un părinte potrivit pentru v. Și suntem într-o formă bună. În caz contrar, p din v este egal cu None. Ei bine, în acest caz, chiar următoarea linie de cod setează corect părintele. Și suntem cu toții pregătiți. Deci, în ambele aceste două cazuri, arătăm că părintele lui u a fost setat corect fie de acea linie de cod chiar aici, fie chiar anterior. Și astfel, în ambele cazuri, inducția noastră este gata. În regulă. Cred că, având în vedere feedback-ul primit de la prelegerea noastră anterioară, acum ne putem încheia LaTeX în mod corespunzător. BINE. Deci, ce tocmai am arătat? Am arătat că algoritmul de căutare depth-first poate săpa într-un grafic și să-mi spună toate lucrurile care pot fi căutate, sau mai degrabă, sunt accesibile dintr-o anumită sursă, practic doar apelând Visit pe acea sursă și apoi extinzându-se în exterior în mod recursiv. BINE. Deci, cred că acest lucru este cu siguranță simplu dintr-o perspectivă intuitivă. Este ușor să te pierzi când scrii acest tip de dovezi formale de inducție, deoarece ele se simt întotdeauna puțin ca tautologie. Așa că ar trebui să mergi acasă și să te convingi că nu este așa. BINE. Deci, desigur, ce facem în această clasă? Urmăm întotdeauna același tip de tipar plictisitor. Primul lucru pe care îl facem este să definim un algoritm. Al doilea lucru pe care îl facem, ne asigurăm că este algoritmul potrivit. Care este al treilea lucru pe care trebuie să-l facem? PUBLIC: Analizează-l. JUSTIN SOLOMON: Analizează. Asta e corect. În special, asigurați-vă că se termină înainte de moartea termică a universului. Și într-adevăr, cercetarea în profunzime nu durează atât de mult, ceea ce este un lucru bun. Deci, să ne gândim puțin la asta. Deci, ce se va întâmpla în căutarea în profunzime, ei bine, vom vizita fiecare vârf cel mult o dată, cam prin definiție aici. Și în fiecare caz, vom vizita doar marginile învecinate. Putem trece vreodată o margine de mai multe ori? Fara drept. Pentru că funcția de vizită este apelată o singură dată pe vârf. Și marginile noastre sunt direcționate. Dreapta. Așa că gândește-te bine la de la fiecare margine, de la vârful este vizitat o singură dată. Și, prin urmare, fiecare margine este vizitată o singură dată. Vizităm vreodată... ah, da. PUBLIC: Funcționează DFS pentru un grafic nedirecționat? JUSTIN SOLOMON: Un grafic nedirecționat. Absolut. Deci, există feluri diferite de a gândi la asta. Una este să ne gândim la un graf nedirecționat ca un graf direcționat cu două margini îndreptate în orice direcție, ceea ce cred că este în această clasă așa cum l-am notat de fapt în prelegerea anterioară. Da. De fapt, acesta este probabil o modalitate rezonabilă de a o reduce. Deci hai să rămânem cu asta. Dreapta. Acum, DFS vizitează vreodată un vârf care nu este accesibil de la sursă? Ei bine, răspunsul este nu, pentru că tot ce fac este să-mi sun recursiv vecinii. Și așa, prin definiție, dacă nu sunt accesibil, DFS nu o va vedea niciodată. Deci, dacă mă gândesc cu atenție la timpul meu de rulare, nu este chiar același lucru cu căutarea pe lățime. Amintiți-vă că căutarea pe lățimea întâi a durat v plus e timp. În căutarea în profunzime, este nevoie doar de timp pentru că mă extind în exterior de la vârful sursă, lovind fiecare margine adiacentă fiecărui vârf pe care l-am văzut până acum. Dar nu ajung niciodată la un vârf pe care să nu-l fi... care să nu fie accesibil. Dreapta? Și pentru că acest lucru atinge fiecare margine o singură dată, suntem într-o formă bună. Și văd aici o întrebare. Da. PUBLIC: BFS ajunge la vârfuri care nu sunt accesibile? JUSTIN SOLOMON: BFS ajunge la vârfuri care nu sunt accesibile? Cred că nu, acum că ai menționat asta. Dar cel puțin în proba mea plictisitoare a ordinului v time data trecută, primul nostru pas al BFS, rezerva spațiu proporțional cu v, ceea ce este suficient pentru a face deja acel timp de rulare corect. Buna intrebare. Da. Așadar, cred că modul în care am vorbit despre asta, în care poți întinde un mic set după un timp, dacă te gândești la asta ca fiind accesibilitate, atunci nu. Nu ajunge la el în bucla for. Dar doar prin construcție, când am început ne-am luat deja timpul despre care vorbim aici. Așa că rețineți că acești timpi de rulare nu sunt exact la fel. Deci, de exemplu, dacă graficul meu nu are margini, BFS totuși va lua timp, deoarece încă trebuie să ia ordine în funcție de timp, cel puțin într-un fel de moarte cerebrală în care l-am implementat data trecută. Evident, în acest caz, probabil că am putea face ceva mai bun. În timp ce modul în care am definit algoritmul DFS, durează doar timp. Văd confuzie pe chipul instructorului meu. Nu? BINE. Bun. Singurul lucru de observat este că aceștia sunt algoritmi pentru sarcini ușor diferite într-un anumit sens. Modul în care am notat căutarea pe lățimea întâi data trecută, convenabil, ne oferă calea cea mai scurtă. Există algoritmi de căutare pe lățimea întâi care nu. Cred că în această clasă ne gândim într-un fel la căutarea pe lățimea întâi -- o motivăm în ceea ce privește problema celei mai scurte drumuri. Dar este doar un fel de strategie de lucru în exterior de la un vârf. În timp ce aici, așa cum am scris căutarea în profunzime, nu există niciun motiv pentru care calea pe care o ajungem ar trebui să fie cea mai scurtă. Dreapta? Deci, să ne gândim la un exemplu extrem, să spunem că am un grafic de ciclu. Așa că primesc o buclă mare ca asta. Să presupunem că fac căutarea în profunzime pornind de la acest vârf. Ei bine, ce se va întâmpla? Ei bine, acest tip își va suna vecinul recursiv, care apoi își va suna vecinul recursiv, care își va suna apoi vecinul recursiv și așa mai departe. Deci, desigur, când fac căutarea în adâncime, când ajung la acest vârf, există un lanț de 1, 2, 3, 4 vârfuri în spatele lui. Este aici cea mai scurtă cale de la sursă la țintă? Ei bine, clar că nu. Dreapta? Aș fi putut traversa acea margine. Pur și simplu am ales să nu o fac. BINE. Deci, acesta este algoritmul de căutare în profunzime. Este, în esență, o strategie recursivă în care îmi traversez toți vecinii și fiecare dintre vecinii mei își traversează vecinii și așa mai departe. BINE. Deci, de ce am putea dori să folosim acest algoritm? Ei bine, am rezolvat deja problema accesibilității. Deci haideți să rezolvăm câteva lucruri folosind aceeași strategie de bază aici. Deci, există unele noțiuni pe care le-am cam-- de fapt, într-un anumit sens, deja le-am folosit în prelegerea de aici. Dar am putea la fel de bine să- i spunem pentru ceea ce sunt, care este această idee de conectivitate. Deci, un grafic este conectat dacă există o cale care trece de la fiecare vârf la fiecare alt vârf. Dreapta. Acum conectivitatea într-un grafic direcționat este un fel de obiect ciudat. De exemplu, gândiți-vă la un grafic direcționat cu doar două muchii. Și o margine merge de la u la v. Apoi pot ajunge de la v la u, dar nu invers. Este o noțiune cam ciudată. Așadar, aici, în 6006, ne vom îngrijora în mare parte cu privire la conectivitate numai pentru graficele nedirecționate, deoarece acestea sunt-- vârfurile vin practic în niște gropi mari conectate. Sau termenul mai tehnic pentru un grup mare conectat este o componentă conectată. Da? Deci, să vedem un exemplu. Deci, să presupunem că am un grafic, care are o muchie și apoi un triunghi. Acesta este un singur grafic. Vezi asta? Există o colecție de vârfuri și există o colecție de margini. Dar are două componente conectate - tipul din dreapta și tipul din stânga, ceea ce înseamnă că fiecare vârf de aici este accesibil de la orice alt vârf de aici. Fiecare vârf de aici este accesibil de la fiecare vârf de aici. Dar nu există margine care să meargă de la triunghi la segmentul de linie. Da? Și astfel, în problema componentelor conectate, ni se oferă un grafic ca tipul ăsta. Și inițial, noi nu, știi... OK. Când îl desenez așa, este destul de clar că graficul meu are două componente conectate. Poate că algoritmul meu de încorporare a graficelor a eșuat și a atras un astfel de avantaj. Ei bine, atunci poate-- nu știu-- este încă destul de evident că există două componente conectate. Dar îți poți imagina un univers în care nu știi asta a priori. Iar problema pe care încercați să o rezolvați este doar să enumerați toate aceste aglomerări de vârfuri care sunt accesibile unul de la celălalt într-un grafic nedirecționat. Și în mod convenabil, putem folosi căutarea în profunzime pentru a rezolva această problemă destul de ușor. Dreapta? Deci cum am putea face asta? Ei bine, într-un anumit sens, cum putem găsi o componentă conectată? Deci, să presupunem că aleg doar un vârf în graficul meu. Ei bine, ce știu despre totul în componenta sa conectată? Ei bine, este accesibil din acel vârf. Amintiți-vă, tocmai am rezolvat problema accesibilității, care spune că, dacă am un vârf, acum vă pot spune toate celelalte vârfuri care sunt accesibile de la acest tip. Așa că aș putea apela DFS pe, ei bine, orice vârf al acestui ciclu aici. Sunați chestia cu accesibilitatea. Și știu că pentru fiecare vârf există unul din două lucruri. Fie vârful are un părinte în acel obiect P, fie este sursa. Deci pot găsi foarte ușor componenta conectată corespunzătoare acelui vârf. Are sens? Am găsit toate componentele conectate? Nu. Am găsit unul. L-am găsit pe cel corespunzător vârfului arbitrar pe care tocmai l-am ales. Deci cum as putea sa repar asta? Ei bine, este super simplu. Aș putea pune o buclă for în exterior, care doar se întinde peste toate vârfurile, poate. Și dacă acel vârf nu face încă parte dintr-o componentă conectată, atunci trebuie să fac una nouă. Deci, apelez DFS pe acel vârf. Colectez toate nodurile pe care le-am primit. Și repet. Deci acesta este algoritmul pe care în această clasă îl vom numi DFS complet. Apropo, ai putea face același lucru cu căutarea pe toată lățimea. Asta e perfect. Doar prin analogie aici. Dreapta. Deci, ce este plin D-- oh, creta asta este mai ușoară. Ei bine, voi repeta peste toate nodurile mele. Unde eu reprezintă bucla. De-- corect. Deci, dacă v nu este vizitat, atunci voi face DFS începând cu v. Cred că am folosit visit pentru a ne referi la asta în diapozitivul anterior. Și asta va umple un fel de inundație întreaga componentă conectată. Și apoi pot colecta acea componentă conectată și pot continua. Trebuie să fim puțin atenți pentru că, desigur, nu vrem să verificăm lucrurile... ceva de vizitat pentru a lua cumva mult timp și a face algoritmul meu mai lent decât trebuie să fie. Dar, desigur, avem o structură de date setată despre care știm că poate face asta și poate comanda măcar o dată în așteptare. BINE. Deci acesta este algoritmul DFS complet. Este foarte simplu. De DFS pentru că am sunat DGS pe fiecare vârf. Și este plin pentru că am făcut buclă peste toate vârfurile. Dreapta. Și deci, dacă ne gândim bine, cât timp durează acest algoritm ? Este puțin cam furiș pentru că, cumva, am o buclă for peste toate vârfurile. Apoi mi-aș putea imagina un univers în care obțin, de exemplu, vârfuri înmulțite cu un alt număr , pentru că există o buclă for și apoi există ceva în interiorul ei. Cred că așa suntem obișnuiți să ne gândim la durata de rulare a buclelor for. Dar în acest caz, asta de fapt nu se întâmplă, deoarece nu există niciodată un caz în care o margine să fie traversată de mai multe ori. Pentru că dacă sunt într-o componentă conectată, atunci, prin definiție, nu pot fi într-o altă componentă conectată. Dreapta? Și deci ceea ce se întâmplă este, într-un fel, acest apel inocent către DFS-- Presupun că dacă ai fi ca un LISP sau un programator, cumva nu ți-ar plăcea asta. Are un efect secundar, și anume că am marcat toate vârfurile din acea componentă conectată ca „nu mă mai atinge”. Dreapta. Și implicit am cam eliminat marginile în acest proces. Deci, dacă vă gândiți cu atenție, durata de rulare a acestui algoritm DFS complet este v plus e timp, deoarece fiecare margine este atinsă nu mai mult de o dată. Un fel de amortizat pentru toate apelurile diferite către DGS aici. Și există asta pentru buclă peste vârfuri. Deci, este clar o comandă v de care aveți nevoie aici. Are sens acest argument? Deci, din nou, o numim liniară în dimensiunea intrării. O să o spun de câte ori ca să-mi trec corect în capul meu . BINE. Dreapta. Deci aceasta este problema de bază. Apropo, asta apare tot timpul. Pare cumva un algoritm ciudat în moarte cerebrală. Cumva, de ce ai vrea un algoritm care găsește componente conectate. Cum ar fi, de ce ai avea chiar un grafic care este deconectat sau așa ceva? Dar, desigur, asta se poate întâmpla foarte multe. Deci, de exemplu, poate lucrați la o companie de social media, iar oamenii au prieteni. Dar de exemplu, Eric și cu mine suntem prieteni. Și nu suntem prieteni cu nimeni altcineva. Avem o... există un fel de jurământ de sânge. Atunci s-ar putea să nu fie atât de ușor de găsit în grafic, deoarece, desigur, suntem doar doi dintre o mulțime de studenți din această clasă, toți având interconexiuni diferite care sunt doar enumerate pe baza listei de margini. Și, deși , în mod ilustrat, este cam greu să desenezi un algoritm de componentă de conectare într-un mod care să nu-l facă să sune ca o tehnică inutilă de la început, pentru că este foarte clar că există două componente conectate acolo. Desigur, încă trebuie să putem scrie cod pentru a rezolva acest gen de lucruri. BINE. Deci, pentru o dată, cred că am ajuns aproape la timp la prelegere astăzi. Deci avem o aplicație suplimentară a căutării în profunzime mai întâi în clasa noastră de astăzi, care se află cam la capătul opus al spectrului. Așa că tocmai am vorbit despre grafice care sunt nedirecționate și ne gândim la cicluri. Acum, la capătul opus ne-am putea gândi la un DAG. Deci un DAG este un grafic aciclic direcționat. Se poate gândi cineva la un caz special de DAG? Presupun că ar trebui să o definesc mai întâi. Și apoi vom reveni la acea întrebare, care înseamnă exact cum sună. Deci este un grafic care are margini direcționate acum și nu are niciun ciclu în el. Deci, de fapt, graficul pe care ți l-am dat până la începutul prelegerii cred că în secret a fost un exemplu al unuia dintre acestea. Deci, să spunem că am margini direcționate. Poate dacă fac din cap un triunghi, e puțin mai ușor de văzut. Nu sunt atât de sigur. În orice caz, așa că voi avea o margine în sus și o margine la dreapta și, în mod similar, o margine în jos și o margine la dreapta. Acest grafic arată ca un ciclu. Dar nu pentru că singura direcție pe care mă pot deplasa este din partea stângă în partea dreaptă. Deci acesta este un grafic direcționat. Și nu conține niciun ciclu, ceea ce înseamnă că nu există nicio cale pe care să o poată lua de la un vârf care se întoarce la sine de-a lungul marginilor direcționate. BINE. Și DAG-urile apar tot timpul. Acum că am definit ce este un DAG, poate cineva să-mi dea un exemplu de DAG pe care l-am văzut deja în 6006? PUBLIC: Un copac. JUSTIN SOLOMON: Un copac. Cel puțin dacă orientăm toate marginile îndreptate în jos în copac. Da. În caz contrar, devine cam discutabil dacă este sau nu un DAG. Dacă nu există nicio direcție către margini, atunci definiția pur și simplu nu se aplică. BINE. Deci, în procesarea graficelor aciclice direcționate, există un lucru cu adevărat util pe care îl puteți face și care va apărea în această clasă aparent destul de puțin, ceea ce este destul de interesant pentru mine, sunt curios să văd cum arată, adică pentru a calcula o ordine topologică pe grafic. Suntem la topologii aici. Așa că, ca profesor de geometrie în slujba mea de zi cu zi, sunt emoționat. Dar în acest caz, o ordine topologică este un lucru destul de simplu. De fapt, este definit pe ecran și oricum am un scris de mână prost. Deci, să rămânem cu asta. Deci ordonarea topologică. Deci ne gândim la f ca la o funcție care atribuie poate fiecărui nod un index în matrice. Bănuiesc că nu ar trebui să folosesc cuvântul matrice aici. Dar la fel ca un index, o ordonare. Deci, acesta este primul vârf. Și acesta este al doilea vârf. Și așa mai departe. Atunci o ordine topologică este una care are proprietățile arătate aici, și anume că, dacă am o muchie direcționată de la u la v, atunci f din u este mai mică decât f din v. Deci, cu alte cuvinte, dacă mă uit la ordonarea că Încep ordinea topologică, trebuie să apari înaintea v. Da? Să ne uităm din nou la exemplul nostru. Deci, să dăm nume nodurilor noastre. Deci iată A, B, C, D. Ei bine, care trebuie să fie în mod clar primul nod în ordinea mea topologică? A. Corect. Merge până în partea stângă. Da. Ei bine, după aceea e un pic de zbucium. Ce știm? Știm că B și C trebuie să apară înaintea lui D. Deci, poate doar pentru a fi enervant, fac A, C, B-- asta este un B-- și apoi D. Deci este o ordine topologică. Observați că lucrurile din stânga apar în graficul meu înaintea lucrurilor din dreapta, unde cuvântul „înainte” aici înseamnă că există o margine care indică de la unul la altul. BINE. Apropo, ordonările topologice sunt unice? Nu. Deci, dacă ne uităm la exemplul nostru de grafic aici, ABCD este, de asemenea, o ordine topologică. Și ceea ce înseamnă asta este cumva foarte eliberator. Înseamnă că atunci când proiectăm un algoritm pentru găsirea unei ordini topologice, deci există câteva decizii de proiectare pe care le putem lua. Și trebuie doar să găsim unul dintre multe. Dar, în orice caz, vom defini o noțiune de ordine puțin diferită. Și apoi vom arăta că sunt strâns legați unul de celălalt. Și aceasta este ordinea finală. Deci, în ordinea finală, vom apela DFS complet pe graficul nostru. Amintiți-vă, asta înseamnă că repetăm ​​toate nodurile noastre. Și dacă nu am văzut încă acel nod, numim DFS pe el. Și acum vom face o ordine în care, de îndată ce apelul la un nod în acea funcție de vizită este complet, adică am iterat deja peste toți vecinii mei, apoi îmi adaug nodul la ordine. Asta are sens? Este ca un pic înapoi față de ceea ce ne-am obișnuit să ne gândim. Deci, este ordinea în care DFS complet termină vizitarea fiecărui vârf. Da? Și acum iată afirmația, este că dacă avem o ordine de finisare inversă, adică luăm ordinea de finisare și apoi o întoarcem înapoi. Exact asta ne va oferi o ordonare topologică a vârfurilor din graficul nostru. Dreapta. Deci hai să facem asta foarte repede. Deci, cu alte cuvinte, afirmația noastră aici -- cred că, da, să vedem -- este că dacă am un grafic direcționat. Deci G este un DAG. Atunci hai să vedem aici. Apoi... hopa. Notele mele sunt invers. Așa că ar trebui să trec la notele mele... ale lui Jason, care, desigur, sunt corecte. Dreapta. Deci, dacă am un grafic care este un DAG, atunci inversul ordinii de finisare este o ordine topologică. Apropo, nu vom demonstra inversul că, dacă am o ordine topologică, că, cumva, acel lucru este inversul DFS, cel puțin așa cum poate l-am codificat. Există o declarație ușor diferită , și anume, există un DFS care are această comandă? Dar acesta este unul despre care ne vom îngrijora altă dată în piață sau orice altceva. BINE. Deci haideți să vedem aici. Deci trebuie să dovedim acest lucru. Deci ce vom face? Ei bine, ceea ce trebuie să verificăm este ordinea topologică este că, dacă mă uit la orice margine a graficului meu, se supune relației pe care o am pe ecran aici. Deci, în special, vom lua UV în interiorul setului meu de margini. Și atunci ceea ce am nevoie este ca u să fie ordonat înainte de v folosind inversul ordinii de finisare pe care am definit-o aici. BINE. Deci, să ne gândim înapoi la apelul nostru la algoritmul DFS, unde apelăm această funcție de vizită. Dreapta. Deci avem două cazuri. Fie u ești vizitat înainte de v. Sau nu este. Da. Deci hai să facem acele două cazuri. Deci, cazul numărul 1 este, u este vizitat înainte de v. OK. În regulă. Deci ce înseamnă asta? Ei bine, amintiți-vă că există un avantaj. Ca, ilustrat, ce se întâmplă? Ei bine, se întâmplă tot felul de chestii grafice. Și apoi ești tu. Și știm că există o margine direcționată de la u la v. Aceasta este imaginea noastră. Dreapta? Și poate că se întâmplă și alte lucruri în afara noastră. Deci, în special, ei bine, prin felul în care am definit această funcție de vizită, ce știm? Știm că, atunci când sunăm la vizită pe u, ei bine, v este unul dintre vecinii săi. Deci, în special, o vizită la u va numi vizită v. Și știm că pentru că ei bine, u este vizitat înainte de v. Deci, în prezent, părintele lui v este l când ajung la tine. Asta are sens? Acum, iată unde ordinea inversă, va trebui să o păstrăm în cap pentru că acum, ei bine, vizita lui u numește vizita lui v. Așa că observați că vizita lui v trebuie să se termine înainte de vizita lui u. Dreapta? V completează înainte de vizita de u. Bine. Deci, în sens invers, sortare... în ordine inversă de finisare aici, ce înseamnă asta? Ei bine, dacă acest lucru se termină înaintea celuilalt tip, atunci ei sunt răsturnați înapoi în listă, ceea ce este exact ceea ce vreau pentru că există un avantaj de la u la v. OK. Deci cazul 1 este gata. Acum avem cazul 2, care este că v este vizitat înainte de u. BINE. Așa că acum voi face o observație suplimentară. BINE. Așa că acum mă voi întoarce la celelalte note ale mele pentru că îmi place mai mult schema mea. Dreapta. Deci, care este imaginea noastră de bază aici? Oh nu. Eu... Oh, știi ce a fost? Am mai tipărit o copie a acestuia. Asta e ok. O pot face din capul meu. BINE. Deci iată vârful meu sursă. Numele lui este S. Acum, există o grămadă de margini și orice altceva. E un drum lung. Și acum, în cele din urmă, ce se întâmplă? Bine. Am un nod v. Și undeva acolo în univers este un alt nod u. Și ce știu? Știu că prin presupunere, știu că există un avantaj de la u la v. Are sens? Deci asta este imaginea noastră de până acum. BINE. Deci ce știm? Știm că graficul nostru este aciclic. Da? Cam prin definiție, aceasta este presupunerea noastră. Deci putem ajunge la tine de la v? Cu alte cuvinte, există o cale de la v la u? Deci ar arăta așa. Nu, deoarece graficul nostru este aciclic și tocmai am desenat un ciclu. Deci acesta este un X mare. Aici e o față încruntă. Nu pot face asta. Are păr, spre deosebire de instructorul tău. BINE. Deci corect. Deci, ce înseamnă asta? Bine. Deci, după imaginea asta, presupun, știm că nu poți fi contactat de la v. Da. Deci ce înseamnă asta? Ei bine, înseamnă că vizita la v se va finaliza și nu te va vedea niciodată, pentru că ține minte, vizita la v numește întotdeauna lucruri care sunt un fel de descendenți ai lui v. Deci, cu alte cuvinte, vizita lui v se completează fără a te vedea. Ei bine, este exact același lucru pe care l-am arătat în primul nostru caz. Dreapta? Deci, prin același raționament, ce înseamnă asta? În ordinea noastră inversă de finisare , ordonarea de la u la v este păstrată. BINE. Așadar, acest fel completează demonstrația noastră aici că ordinea inversă de finisare îmi oferă o ordine topologică, ceea ce este destul de plăcut. Și așadar, acesta este un mod convenabil de a lua toate nodurile într-un graf aciclic direcționat și de a le ordona într- un mod care respectă topologia sau conectivitatea acelui graf. Așa că vom încheia cu o ultimă problemă, despre care nu am un slide. Dar este in regula. Și asta este detectarea ciclului. Deci, mai rămâne un pic de exercițiu pentru cititor aici. Deci problema pe care o căutăm acum este că ni se oferă un grafic direcționat. Există un G în grafic, în cazul în care vă întrebați. Dar acum, nu știm dacă este un DAG sau nu. Și deci întrebarea pe care încercăm să o punem este, există un ciclu în graficul nostru aciclic direcționat? Așa că tocmai ni s-a dat graficul și vrem să știm, putem face asta? Să ne gândim puțin la logica acestui lucru. Deci ce știm? Știm că, dacă graficul nostru ar fi un DAG, atunci aș putea apela DGS, aș putea obține ordinea și apoi cred că aș putea întoarce ordinea înapoi. Așa că am putut calcula ordinea inversă de finisare. Și mi-ar oferi o ordine topologică a graficului meu. Deci, dacă aș fi un DAG, aș primi o comandă topologică atunci când sun DFS. Deci, să presupunem că am rulat DFS. Am primit orice comandă am primit. Și acum am găsit o margine în direcția greșită. Pot să verific din nou lista mea de margini și găsesc una care nu respectă relația pe care o văd în al doilea punct aici. Graficul meu poate fi un DAG? Nu. Pentru că dacă graficul meu ar fi un DAG, algoritmul ar funcționa. Tocmai ți-am dovedit-o. Dreapta? Deci, dacă graficul meu ar fi un DAG, atunci aș putea face ordinea inversă de finisare. Și ceea ce aș primi este o ordine topologică. Deci, dacă am găsit un certificat că comanda mea nu a fost topologică, ceva nu a mers prost și singurul lucru care ar putea merge prost este că graficul meu nu este un DAG. Da. Nu este un DAG. De fapt, un fel de exercițiu lăsat cititorului și/sau secțiunii dvs., mai avem secțiune? Cred că, de acum, este că acesta este un dacă și numai dacă, ceea ce înseamnă că singura dată când aveți chiar și o ordonare topologică în graficul dvs. este dacă graficul dvs. este un DAG. Acesta este un fapt foarte ușor de verificat, apropo. Aceasta nu este o problemă deosebit de provocatoare. Dar ar trebui să vă gândiți bine, deoarece este un exercițiu bun pentru a vă asigura că înțelegeți definițiile, adică dacă aveți o ordine topologică, graficul dvs. este un DAG. Dacă nu aveți o ordine topologică, graficul dvs. nu este un DAG. Deci, cu alte cuvinte, v-am dat în secret un algoritm pentru a verifica dacă un grafic este un DAG. Dreapta? Ce as putea sa fac? Aș putea calcula ordinea inversă de finisare. Verificați dacă respectă relația de pe al doilea punct aici pentru fiecare margine. Și dacă o face, atunci suntem în formă bună. Graficul meu este un DAG. Dacă nu, ceva a mers prost. Și singurul lucru care ar fi putut merge prost este să nu fii DAG. BINE. Deci, cu alte cuvinte, în secret tocmai am rezolvat-- ei bine, cred că în felul în care am scris-o aici, am rezolvat problema de detectare a ciclului aici, ceea ce înseamnă că, ei bine, am un ciclu dacă și numai dacă nu sunt un DAG, pe care îl pot verifica folosind această tehnică. Desigur, cuvântul „detecție” aici înseamnă probabil că vreau de fapt să găsesc acel ciclu și încă nu ți-am spus cum să faci asta. Tot ce știm cum să facem până acum este să spunem că undeva în acest grafic există un ciclu. Și asta nu e așa de bine. Așa că putem face o informație suplimentară în cele două minute rămase pentru a ne completa povestea aici, și anume să ne modificăm puțin algoritmul pentru a nu spune doar degetele în sus, degetele în jos, există un ciclu în acest grafic , dar și pentru a returna efectiv vârfurile ca ciclu. Și iată proprietatea pe care o vom face, care urmează, și anume că, dacă G conține un ciclu, corect, atunci DFS complet va traversa o margine de la un vârf v la un strămoș al lui v. Cred că avem" am definit cu atenție termenul „strămoș” aici. În esență, dacă vă gândiți la felul de rulare a algoritmului DFS, atunci un strămoș este ca ceva care apare în arborele apel recursiv înainte de a ajunge la v. OK. Deci, cum am putea demonstra asta? Ei bine, hai să facem un ciclu. Și îi vom da un nume. În special, vom spune că este un ciclu de la v0 v1 la vk. Și apoi este un ciclu, deci se întoarce la v0. BINE. Și pot comanda acest ciclu oricum vreau. Observați că dacă permut vârfurile din această listă într-un mod ciclic, adică iau ultimele câteva dintre ele și le lipesc la începutul listei, este tot un ciclu. Acesta este lucrul bun cu ciclurile. Deci, în special, fără pierderea generalității, vom presupune că v0 este primul vârf vizitat de DFS. Ce înseamnă asta? Asta înseamnă, cum ar fi, când îmi fac algoritmul DFS care face toate aceste apeluri recursive, primul vârf care va fi atins de această tehnică este v0. BINE. Ei bine, acum ce se va întâmpla? Ei bine, gândiți-vă la arborele apel recursiv care începe cu v0. Până la finalizare, orice lucru accesibil din v0 va fi, de asemenea, complet. Vezi asta? Deci, de exemplu, v0 undeva în arborele său de apeluri ar putea apela v2. Și observați că v2 nu a fost deja vizitat. Deci, de fapt, va fi. Pentru v1 trebuie să sun v2 și așa mai departe. Și în special, vom ajunge până la vârful k. Dreapta? Deci, cu alte cuvinte, vom vizita un vârf vk. Și observați ce se va întâmpla. Deci, amintiți-vă de algoritmul nostru. De fapt, probabil că ar trebui să-l punem pe ecran ar fi mai ușor decât să vorbim o grămadă despre asta. Ei bine, vk va repeta acum fiecare dintre vecinii lui vk. Și în special, va vedea vârful v0. Dreapta? Așa că vom vedea marginea de la vk la v0, care este un fel de margine prin definiție, deoarece am considerat că acesta este un ciclu aici. Dar observați că acesta este exact ceea ce ne-am propus să demonstrăm, și anume că DFS complet traversează o margine de la un vârf la unul dintre strămoșii săi. Iată un vârf k. Iată strămoșul v0. De ce știm că este un strămoș? Ei bine, pentru că v0 a fost numit în arborele nostru de apeluri înaintea oricăruia dintre acești tipi. Dreapta? Așa că ne-am dorit un algoritm care nu numai că a detectat ciclul, ci și mi-a oferit ciclul. Ce as putea sa fac? Ei bine, este în esență o mică modificare a ceea ce avem deja. Dreapta. Deci... hopa. Dreapta. Dacă vreau să calculez ordinea topologică sau orice altceva, pot face doar DFS. Și asta îmi va spune că, da sau nu, există un ciclu. Dacă vreau să găsesc de fapt acel ciclu, tot ce trebuie să fac este să verific acea proprietate de ordine topologică în același timp în care a traversat graficul în timpul DFS. Și în secunda în care găsesc o margine care se întoarce înapoi, am terminat. Și deci acesta este algoritmul nostru de bază aici. Și aceasta este o tehnică pentru a găsi de fapt ciclul într-un grafic folosind algoritmul DFS.