[SCRÂȘIT] [FOȘTIT] [CLIC] JUSTIN SOLOMON: OK, echipă. Să începem ziua. Este o plăcere să vă văd pe toți. În caz că nu-ți amintești, eu sunt Justin. Sunt al treilea instructor din 006 de care probabil ai uitat, dar o să mă vezi mult mai mult în partea de teoria grafurilor a cursului nostru, deoarece aceasta este partea de algoritmi care îmi place. Dacă m-aș reîncarna ca informatician teoretic, probabil că aș merge în acest domeniu. Bună băieți. BINE. Urmează zilele de vizită pentru admiterea doctoratului pentru următoarele două zile, în care lucrez la vocea mea de majorete a consilierului de tabără . Așa că nu mă face să vă trezesc pe toți pentru ziua aceea. Nu o să-ți placă. Dar în orice caz, deci în 6.006, dacă te uiți înapoi la schema cursului, începem oficial partea a doua a acestui curs. Există câteva corolare ale acestui fapt. Deci, dacă nu există întrebări despre asta, vom începe cu noua noastră unitate din 6.006, care este o teorie a graficelor. Dacă vă întrebați, există un grafic pe ecran aici. Dar, desigur, vom completa un pic mai multe informații astăzi pe parcursul prelegerii noastre. Când învățam să predau, ceea ce încă mai fac, de fapt, consilierul meu de doctorat mi-a spus că dacă vrei ca cineva să învețe ceva, trebuie să scrii cât mai mare posibil. Și așa că mă înclin cu adevărat în această abordare astăzi în diapozitivele noastre. Deci, în orice caz, astăzi vom avea prima noastră prelegere despre grafice, care cred că va fi oarecum o recenzie pentru mulți dintre voi. Și dacă nu este, e grozav și asta. Pentru că vom începe de la început și vom construi toate noțiunile de care avem nevoie pentru a înțelege și a procesa graficele și, sperăm, până la sfârșitul prelegerii, vom avea un anumit stil de algoritm pentru a calcula calea cea mai scurtă de la un vârf la toate celelalte. . Deci, în cazul în care am uitat puțin de terminologie, un grafic -- unii oameni numesc această rețea, dar uneori acel termen este supraîncărcat cu câteva tipuri diferite de variații ale temei -- este o colecție de două lucruri. Asta înseamnă această notație din paranteză. Există un set de vârfuri și un set de muchii. Iar marginile, așa cum puteți vedea în felul de al treilea punct de pe ecranul nostru aici, sunt un subset de v cross v. Acum, aceasta este o notație fantastică pentru ceva cu adevărat, foarte simplu. Pentru că ce îmi spune asta? Acest lucru îmi spune că o margine, ca în imaginea pe care o vedem pe ecran aici. este doar ceva care se conectează la vârfuri împreună. Deci, dacă mă gândesc că există o pereche de vârfuri, cum ar fi de la și până, atunci aceasta este o submulțime a produsului încrucișat al lui v și al lui însuși. Deci, sperăm că notația din acea a treia linie de pe ecran are sens. Aceasta este doar o notație fantastică pentru marginile sunt perechi de vârfuri. Dar, desigur, în interiorul acestei notări există două cazuri speciale care ne pasă în această clasă. Unul este atunci când aveți un grafic direcționat și unul este când aveți un grafic nedirecționat -- pentru că le-am spus în ordine opusă față de ceea ce este pe ecran. Deci, într-un grafic nedirecționat, cred că încă ne gândim la o muchie ca o pereche de vârfuri, dar într-adevăr ar fi trebuit să notez acest lucru puțin diferit - de fapt, poate o voi revizui în slide-uri înainte ca acestea să intre în OCW-- unde în loc să scriu e equals w virgulă v, ar trebui să scriu de fapt equals v virgulă w. Și observați că există o mică diferență între notația de pe diapozitiv și ceea ce am scris pe tablă, care este notația setată aici. Care este diferența dintre paranteze și linii ondulate este că acest tip este neordonat. Acesta este un set de lucruri. Și ce este pe tablă este comandat-- sau mai degrabă ce este pe ecran. Și, desigur, într- o muchie nedirecționată nu există așa ceva ca o muchie de la w la v să fie distinctă de o muchie de la v la w. Acestea sunt același lucru. Sunt nedirecționați. Este doar o noțiune de conectivitate. În timp ce într-un grafic direcționat, acum vom folosi acea notație parantetică pentru a spune că muchia de la w la v este diferită de muchia de la v la w. Asta va face o mare diferență. Deci, de exemplu, în graficul din dreapta, să-l redesenăm pe tablă aici. Deci avem patru vârfuri. Am desenat asta aseară și sper că acest exemplu funcționează cu adevărat. Așa - pot ajunge de la vârful din dreapta sus la vârful din stânga jos urmând marginile din acest grafic? Am auzit o persoană. Toată lumea la trei-- 1, 2, 3. PUBLIC: Nu. JUSTIN SOLOMON: Nu, corect. Pentru că dacă aș fi vrut să-- adică poate mă gândesc să trag această cale aici-- dar, desigur, dacă aș merge din dreapta sus în stânga jos-- acesta este cel mai urât lucru pe care l-am făcut vreodată, eu Îmi pare atât de rău, puteți observa că marginile sunt îndreptate în sus aici. Așa că ar trebui să merg împotriva curentului de apă, dar acest lucru nu este permis în cazul graficului direcționat. Desigur, anticipez deja noțiunea de cale pe care încă nu am definit-o cu adevărat. Dar cred că intuitiv, aceasta este diferența mare dintre un grafic direcționat și nedirecționat. Are sens această distincție pentru voi toți sau am reușit să vă pierd în patru minute sau mai puțin? Excelent. Așa că am răsturnat lucrurile puțin, puțin din notele de curs, pentru că m-am gândit că vom defini mai întâi ce este un grafic înainte de a vă spune care sunt implicațiile. Dar, în orice caz, cred că nu este o mare întindere a imaginației să spunem că graficele sunt literalmente peste tot în viața noastră de zi cu zi, nu. De fiecare dată când venim cu o rețea de lucruri conectate între ele, implicit abstracția potrivită adesea în spatele capului nostru este să ne gândim la un grafic. Așadar, câteva exemple simple care cred că ne- ar veni în minte ar fi ca rețelele de calculatoare - deci nodurile sau vârfurile graficului dvs. în acest caz, poate sunt computere, iar apoi marginile sunt aproximativ cablurile care le conectează împreună în Înțelegerea mea foarte grosieră a modului în care funcționează rețelele-- sau poate la o rețea socială-- nodurile sunt oameni de pe rețeaua ta de socializare, iar marginile sunt relații de prieteni sau relații inamice sau orice altceva. De fapt, cred că v-ați putea gândi atât la versiuni direcționate, cât și la versiuni nedirecționate ale acelei rețele. În rețelele rutiere, poate că lucrez pentru Google și vreau să vă spun cea mai scurtă cale între casa dumneavoastră și MIT. Desigur, pentru a face asta și, în esență, în culise, rezolvăm o versiune a calculării celei mai scurte căi dintre două vârfuri dintr-un grafic. Este o minciună mică, în sensul că există multă structură în această problemă pe care nu o vom folosi în acest curs. O rețea de drumuri este un tip foarte special de grafic, iar dacă urmați un curs avansat poate veți spune, ei bine, dacă știu puțin mai multe despre graficul meu, pot face mai bine decât cazul general despre care vom vorbi aici. Dar algoritmii de bază despre care vom vorbi în 6.006 sunt cu siguranță relevanți în acest caz și sunt cu adevărat elementele de bază pentru ceea ce se întâmplă în instrumentele care sunt folosite în fiecare zi pe telefonul dvs. când deschideți Google Maps sau Ways sau orice altceva. Și, desigur, sunt multe altele. Deci, de exemplu, un exemplu care poate este puțin mai subtil ar fi setul de stări și tranziții ale unui lucru discret. Așa că gândește-te ca la un cub Rubik. Așa că aș putea face un grafic în care nodul este fiecare configurație a cubului meu Rubik, ca fiecare rotație. Și apoi marginile sunt ca și cum pot ajunge de la această configurație la aceea făcând o tranziție simplă, ca o singură răsturnare. Nu știu de fapt terminologia din cubul lui Rubik, am impresia că o faci, pentru o rotație. Twist-- mulțumesc. Și, desigur, există multe alte locuri. Deci, de exemplu, în munca mea de zi aici la MIT, predau de obicei cursuri de grafică pe computer. Și de fapt teoria graficelor, deși vorbim despre ea foarte diferit, apare în acea lume în mod constant. Pentru că, desigur, în spatele oricărui model 3D de pe computer este o rețea uriașă de triunghiuri. Aceasta se numește suprafață triangulată, ca acest tor pe care îl vedem aici. Și acesta nu este altceva decât un grafic. Și, de fapt, dacă vă uitați la algoritmii pe care îi acoperim în șase opt trei opt, veți vedea că sunt aproximativ doar algoritmi grafici deghizați. De fapt, dacă urmezi cursul meu absolvent, un lucru pe care îl vom face este că vom petrece mult timp făcând geometrie diferențială. Și apoi vom face un pas înapoi cu 10 picioare și vom observa că exact algoritmii pe care îi folosim pentru a calcula curbura și curbura pe rețele triunghiulare, arată ca un algoritm grafic și pot fi aplicați rețelelor exact în același mod. Așa că va fi un fel de distracție plăcută acolo. Și, desigur, există un ultim tip de aplicație distractivă. De fapt, am fost plecat în ultimele două zile la o conferință despre redistribuire politică. Și lucrul amuzant este că cea mai mare parte a discuțiilor de la acea conferință a fost despre teoria grafurilor. Și motivul pentru aceasta este un fel de temă care apare mult în lumea geometriei, adică dacă îmi iau statul, în acest caz cred că acestea sunt secțiile de votare într-un stat sau altul și mă uit la relațiile de adiacență, atunci poate pun un nod pentru fiecare incintă și o margine de fiecare dată când împart o graniță între ele. Ei bine, acum am o rețea. Și poate că o regiune din graficul meu este ca o bucată conectată a acestei rețele. Și oricum, acesta este unul dintre aceste exemple în care graficele și rețelele și conectivitatea și așa mai departe apar la propriu, indiferent unde te duci. Sunt total inevitabile. Și pentru asta vom petrece destul de mult timp în această clasă aici. Acum aș putea susține cu ușurință, aș spune, cel puțin trei cursuri întregi de teoria graficelor aici la MIT și ai putea construi cu ușurință o disertație de doctorat fără a face altceva decât probleme cu adevărat simple pe grafice. Desigur, în această clasă ne limităm la doar câteva prelegeri din multe. Așa că vom face câteva ipoteze atât cu privire la problemele pe care vrem să le rezolvăm, cât și la graficele care ne interesează. Deci, în special, o ipoteză simplificatoare, care de fapt nu afectează mulți dintre algoritmii despre care vom vorbi aici, dar merită remarcată în mod explicit, este că ne vom gândi mai ales la un anumit tip de grafic, care este un grafic simplu. . Și, de fapt, adesea, în funcție de modul în care îți definești graficul, ți-ai cam făcut din greșeală graficul simplu, chiar dacă nu ai intenționat. Deci, de exemplu, am scris că muchiile noastre au fost un subset de v cross v. Ceea ce poate înseamnă că nu pot avea mai multe muchii care să traverseze aceeași pereche de vârfuri. Deci, să vedem un exemplu de grafic care nu este simplu. Îmi pare rău, nu l-am definit de fapt. Un grafic simplu este un grafic care nu are bucle proprii, deci nu poate trece de la un vârf la el însuși și fiecare muchie este distinctă. Deci, haideți să facem cel mai puțin simplu grafic la care ne putem gândi. Să zicem că am două vârfuri. Deci, poate dacă vreau să-mi fac... deci există un grafic, dreapta, două vârfuri și o muchie. Acest lucru este simplu. Dacă aș fi vrut să fiu enervant și să nu o fac simplu, poate aș lua acest avantaj și l-aș duplica de trei ori doar pentru distracție. Asta încalcă a doua presupunere. Și acum, pentru a face și mai rău, l-aș putea încălca pe primul adăugând o margine care merge de la acest vârf la sine. Acest lucru nu este simplu. Nu știu cum l-ați numi de fapt -- grafic general, cred -- complicat pentru că nu este simplu. Nu știu... un multigraf. Mereu m-am gândit la asta... oricum, nu contează. Dar, în orice caz, în această clasă nu ne vom îngrijora de această circumstanță specială. Și, desigur, în multe aplicații ale teoriei grafurilor, aceasta este o presupunere total rezonabilă . Aveți întrebări despre definiția unui grafic simplu? Bine, deci de acum încolo ori de câte ori ne gândim la un grafic, în fundul capului ne vom gândi la graficul nostru ca fiind simplu. Există o proprietate frumoasă pe care o are un grafic simplu, pe care am scris-o într-un text foarte mare pe ecran aici, și anume că muchiile sunt O mare de v pătrat. Și, de fapt, să extindem această formulă doar puțin. Deci, există un fel de două cazuri, unul este când graficul meu este nedirecționat, celălalt este când graficul meu este direcționat. Deci, dacă am un grafic direcționat... ei bine, să ne gândim la câte muchii am putea avea. Deci o muchie este o pereche de a de la vârf și a la vârf și nu o pot repeta niciodată de două ori. Este un fel de a doua presupunere aici. Deci, în special, ce știm? Știm că modul E-- sau, mai degrabă, numărul de muchii din graficul nostru este limitat în sus de ce? Ei bine, pot lua orice pereche de vârfuri-- așa-- dar trebuie să fiu puțin atent pentru că graficul meu este direcționat-- deci de la și să conteze aici. Deci, acesta este v alegeți 2 înseamnă că pot lua orice pereche unică de vârfuri, dar trebuie să pun un factor de 2 în fața ei pentru a ține cont de faptul că sursa și ținta pot fi răsturnate înainte și înapoi. Și, desigur, dacă vreau să fac nedirecționat, nu trebuie să-mi fac griji pentru asta. Vom obține că E aici este mai mic sau egal cu doar mod v alege 2. Deci, acesta este doar un mod fantezist de a spune că fiecare muchie constă din două vârfuri, iar muchiile mele sunt unice. Și un lucru, dacă scrieți aici formula pentru coeficientul nostru binom, vom vedea că ambele lucruri -- hopa, oh, da, scuze-- sunt mai rău mod v pătrat aici. Și asta are sens, pentru că, desigur, o muchie este o pereche de vârfuri. Te cam aștepți să fie un pătrat acolo. Da? PUBLIC: [INAUDIBIL] JUSTIN SOLOMON: Îmi pare foarte rău. Nu te pot auzi. PUBLIC: Deci 2 vine din faptul că este de la sursă. JUSTIN SOLOMON: Da, exact. Deci, 2 pentru cazul directorului, vine din faptul că o muchie de la v la w este diferită de o muchie de la w la v. Deci, amintiți-vă că coeficientul binomial de aici, este doar numărarea numărului de moduri în care pot alege două lucruri dintr-un set de marimea v, dar nu-i pasa de comanda. Da, alte întrebări? Fabulos. Deci de ce va conta asta? Ei bine, astfel de limite, vreau să spun că ți se pot părea puțin evidente, dar vom scrie algoritmi grafici. Și acum, când analizăm timpul de rulare și spațiul pe care îl ocupă, avem acum două numere diferite la care ne putem gândi - numărul de vârfuri și numărul de muchii. Și așa, de exemplu, dacă notez un algoritm a cărui durată de rulare este proporțională cu numărul de muchii, poate că, în general, aș putea să mă gândesc și la algoritmul ca având un timp de rulare care arată ca numărul de vârfuri la pătrat, dacă nu pun câteva ipoteze suplimentare pe graficul meu. Și așa că există o legătură între toate aceste constante diferite și este util să păstrăm asta în spatele capului. Că uneori veți vedea o grămadă de expresii diferite care codifică aproximativ aceeași relație doar într-o limbă diferită. Desigur, asta înseamnă, de asemenea, că putem fi mai precisi. Deci, uneori, un grafic este ceea ce am numi rar. Deci, în universul meu, aproape toate graficele cu care mă ocup în viața mea de zi cu zi sunt extrem de rare. Aceasta este o consecință a topologiei. Și din această cauză, un algoritm care se scalează ca numărul de muchii ar putea fi de fapt mult preferabil unui algoritm care se scalează ca numărul de vârfuri la pătrat, deoarece, în practică, adesea există mai puține muchii decât fiecare pereche posibilă. Și acesta este genul de motiv pentru care ne gândim la aceste numere. OK, deci haideți să continuăm să facem definiții plictisitoare aici. Deci, altele la care ar trebui să ne gândim implică topologia sau conectivitatea graficului nostru, în special, gândindu-ne la vecini. Deci, în general, ne gândim la perechile de vârfuri ca fiind vecine unul cu celălalt dacă există o margine între ele. Trebuie să fim puțin atenți pentru că, bineînțeles, atunci când avem un avantaj direcționat, trebuie să fim atenți cine este în felul de a dărui și de a primi partea acestei relații de vecin. Da, deci haideți să desenăm un grafic foarte, foarte simplu. Deci, aici este vârful 0, aici este vârful 1, aici este vârful 2. Și poate vom avea o muchie care urcă, o muchie care coboară și apoi un ciclu aici. BINE. Acum putem defini o mulțime de noțiuni diferite de vecini -- cum ar fi setul de vecini de ieșire, setul de vecin de intrare. Și ideea de bază aici este că vrem să ținem evidența muchiilor care trec de la un vârf și a muchiilor îndreptate într-unul. Da, de exemplu, setul de vecin de ieșire , pe care îl vom nota ca Adj plus aici - care este setul de vecin de ieșire al nodului 0 aici? Ei bine, dacă ne uităm, observați că există o margine care iese din nodul 0 și indică către nodul 2. Deci, desigur, acesta este un set care conține doar un alt nod. Și, în mod similar, setul de vecin de intrare al nodului 0, observați bine că există un vecin de intrare de la vârful 1, deci acesta este un astfel de set. Acum, desigur, într- un grafic nedirecționat, felul de distincție dintre aceste două lucruri nu contează. Deci, dacă vă uitați la punctul nostru final aici, de multe ori, în cazul nedirecționat, aruncăm doar acel plus sau minus superscript pentru că nu contează. În orice caz, există o terminologie suplimentară care contează destul de mult, și anume gradul. Și asta nu este altceva decât doar numărarea dimensiunii acestui set. Deci, gradul de ieșire este numărul de muchii care indică un vârf. Iar gradul în este numărul de muchii în care sunt punctate. Așa că observați, în acest caz, ambele numere sunt 1. Să vedem un exemplu în care nu sunt. Deci, în nodul 1, observați că sunt două margini care ies. Deci, gradul de ieșire al nodului 1 este 2. Există o margine care indică, deci gradul de intrare este 1. OK, atât de des de ce vom face asta? Ei bine, vom obține o mulțime de algoritmi grafici care au o buclă FOR peste vecinii unui vârf dat. Și apoi acest număr de grad va intra în joc. Merită să limitezi aceste lucruri doar puțin. Deci, în special, un lucru la care ne-am putea gândi -- scriu prea mare și voi rămâne fără spațiu foarte repede aici -- este următorul. Deci, să aruncăm o privire la toate nodurile posibile din interiorul graficului meu și acum să însumăm toate gradele lor. Deci voi... să vedem, dacă mă uit la acest grafic, observăm că aici sunt trei muchii adiacente acestui vârf , trei muchii adiacente celuilalt, două adiacente acestuia. Așa că le însumăm pe toate împreună. Deci, este doar o legătură convenabilă de a avea în jur-- este să însumăm aceste lucruri, pentru că vom avea algoritmi care arată ca pentru fiecare vârf, pentru fiecare vecin să facă ceva. Deci am putea la fel de bine să știm cam cât timp va dura. Să ne gândim la asta. Deci ce știm? Într-un grafic nedirecționat, fiecare muchie este adiacentă la două vârfuri. Deci, dacă ne gândim la modul în care luăm în considerare gradul, ce știm? Ei bine, știm că un fel de muchie contribuie la gradul a două vârfuri diferite. Deci, dacă ne gândim cu atenție aici, ceea ce vom vedea este că, dacă graficul nostru este nedirecționat-- oh, scuze-- este corect, așteaptă că sunt din nou înapoi. Deci, dacă am un grafic cu două vârfuri și o muchie și este nedirecționat, observați că numărul de muchii aici este 1. Care este suma gradului? Ei bine, este 1 plus 1 este egal cu 2. Da, deci există un 2 aici dacă graficul meu este nedirecționat și E dacă graficul meu este direcționat, dacă ceea ce număr este doar gradul de ieșire. Are sens? Cred că am reușit să greșesc total acea propoziție, așa că poate să încercăm din nou. Deci, dacă număr doar numărul de muchii care indică fiecare vârf și îl număr pe toate vârfurile posibile, atunci există două cazuri - unul este direcționat și unul nedirecționat. Deci, în cazul nedirecționat, obțineți un 2 aici, deoarece în esență fiecare margine este simultan în mers și ieșire. În timp ce obțineți un 1 ca coeficient în cazul direcționat. Are sens? Îmi pare rău că am greșit asta pentru o secundă. OK, excelent. OK, asta va fi o legătură utilă pentru noi mai târziu. Acum ne gândim la grafice, desigur, tocmai am petrecut ultimele două săptămâni gândindu-ne la structurile de date. Ar trebui să ne gândim cum să stocăm un grafic pe un computer și există multe opțiuni diferite. De fapt, un lucru pe care îl poți face este un fel de pereche, la fel ca atunci când am vorbit despre seturi. Există multe moduri diferite de a stoca seturile. Și o modalitate de a ne gândi la asta a fost, în funcție de modul în care vom interacționa cu acel set, am putea alege o structură de date sau alta pentru a sorta optimizarea tipurilor de interacțiuni pe care le vom avea cu acel set și a le face la fel de rapide. posibil. Aceasta este exact aceeași poveste pentru un grafic. Deci, de exemplu, cea mai proastă reprezentare din lume a unui grafic ar fi să ai doar o listă lungă de muchii. Deci, de exemplu, pentru acest grafic de aici, poate am 0, 1, care este o muchie, apoi 0, 2, aceasta este o altă muchie, apoi 1, 2 și apoi 2, 1. Există o listă mare de muchii. Este într-adevăr un set. Nu-mi pasă de comandă. PUBLIC: Primul este 1, 2. JUSTIN SOLOMON: 1-- oh, ai dreptate. Îmi pare rău. Da, marginea este în sus... mulțumesc Erik, sau nu Erik... Jason. OK, deci să spunem că am un algoritm grafic și va trebui să fac ceva de genul să verific dacă există o margine de la v la w de multe ori. Cât timp va dura asta în această structură de date? Ei bine, dacă am doar o listă dezorganizată de margini și vreau să știu dacă există o margine de la v la w, tot ce pot face este să scriu o buclă FOR care merge de-a lungul asta și spune, așa, marginea Caut. Nu. Asta e marginea pe care o caut? Nu. Deci, de fiecare dată când vreau să găsesc o muchie, îmi va lua timp proporțional cu numărul de muchii ale graficului meu, care ar putea fi până la v pătrat. Da, deci aceasta nu este o reprezentare atât de grozavă a unui grafic pe computerul meu. Deci, dacă ne gândim înapoi la structura noastră de date, putem spune, OK, deci o listă de margini probabil nu este calea de urmat. Deși observați că modul în care am notat ceea ce este un grafic arată ca o listă de margini. Dar, în orice caz, cel mai obișnuit lucru de făcut este să obțineți ceva de genul unei liste de adiacență. Deci ideea de bază a unei liste de adiacență este că ceea ce voi stoca este un set care mapează un vârf u la tot ce este adiacent lui u. Deci, cu alte cuvinte, voi ține evidența tuturor marginilor de ieșire de la fiecare vârf. Și acum trebuie să decid cum voi stoca acest obiect. Și de multe ori, va trebui să răspundem la întrebări, cum ar fi există o margine de la v la w. Deci, cum aș putea face asta? În primul rând, aș căuta v și primesc înapoi un fel de listă sau un set de toate lucrurile care sunt adiacente v. Și trebuie să întreb acel lucru. Și vreau să fie destul de rapid. Deci, poate ceea ce fac este să stochez setul de lucruri adiacente ca ceva de genul unei matrice de acces direct sau o tabelă hash pentru a face ca aceasta să arate rapid. Deci, de exemplu, cât timp ar dura-- văd, voi termina propoziția aici-- cât timp mi-ar lua să verific dacă a existat o muchie în graficul meu? Ei bine, ce aș face? Mai întâi aș scoate acest obiect și apoi m-aș uita înăuntru aici. Deci, dacă aș stoca asta ca tabel hash, atunci timpul estimat la care aș avea o comandă în sus, pentru că aceasta este o comandă și apoi aveți o altă comandă, o căutare acolo sus. Așa că am trecut de la v pătrat la unu cu un truc simplu. Da? AUDIENTĂ: Contează în ce direcție? [Inaudibil] JUSTIN SOLOMON: Aceasta este o întrebare grozavă. Deci, aceasta este o decizie de proiectare aici. Îmi pare rău, în mintea mea mă gândesc mult la graficele nedirecționate și o să fac foarte mult această greșeală. Și mă bucur că m-ai prins. Există un lucru absolut rezonabil de făcut, care este poate doar să ținem evidența muchiilor de ieșire pentru fiecare vârf. Aceasta este o decizie de proiectare. Pentru un algoritm, poate vreau să țin evidența marginilor de intrare. Oricum, trebuie doar să mă asigur că se aliniază cu ceea ce vreau să fac mai târziu cu graficul meu. Excelent punct. Ne pare rău, ca om de geometrie întâlnim rar grafice direcționate. Dar este important să ne amintim că nu toată lumea lucrează la aceleași probleme ca și mine. OK, acum, dacă aș vrea să fiu total extrem în privința asta -- ca doar un al treilea exemplu de reprezentare, care de fapt, într-un anumit sens, te- ai putea gândi ca la o listă de adiacență -- avem nevoie de o matrice de adiacență în care acum păstrez doar o matrice giant v by v de asemenea, există asta, există marginea aceea. Acum este foarte, foarte ușor să verifici dacă există o margine. Dar acum să presupunem că fac un algoritm grafic care va avea o buclă FOR peste toți vecinii unui vârf. Deci, aici, dacă aș vrea să fac bucla peste toți vecinii cu u, aș putea face asta în timp proporțional cu numărul de vecini cu u. Dar dacă am doar o matrice mare de adiacență, doar o grămadă de valori binare - ca pentru fiecare pereche de vârfuri aceste vârfuri sunt adiacente - da sau nu. Dacă vreau să iterez peste toți vecinii mei, acum trebuie să iterez peste toate nodurile și să verific dacă este numărul unu și apoi să fac ceva. Deci, de fapt, asta poate implica ceva timp suplimentar și spațiu suplimentar. Are sens? Deci, în orice caz, aceasta este un fel de reprezentare grafică a unui om leneș . Îl folosesc foarte mult când codez, deoarece matricele de adiacență sunt ușor de lucrat. Dar implică mult spațiu suplimentar și nu este întotdeauna cel mai eficient lucru, chiar dacă aveți spațiu, deoarece repetarea peste vecini poate dura de fapt destul de mult timp. OK, deci adevăratul scop al prelegerii noastre de astăzi este să începem să introducem un fel de problemă canonică de care ne îngrijorăm cu toții pe grafice, care este calculul căilor, în special căilor cele mai scurte. Deci, primul lucru pe care ar trebui să-l facem este, desigur, să definim ce este o cale pe un grafic. Așa că vom vorbi despre graficul nostru ca despre o rețea de drumuri. Să ne gândim poate la fiecare nod de aici ca la o intersecție. Deci, aceasta este aproximativ Kendall Square. Vezi că este un pătrat. Dar, în orice caz, să spunem că vreau să găsesc -- poate o întrebare ar fi dacă există o modalitate de a ajunge de la vârful 1 la vârful 3. Și apoi o întrebare mai bună de pus ar fi dacă există o cale scurtă de trec de la vârful 1 la vârful 3. Apoi, desigur, primul lucru pe care trebuie să-l fac este să-mi definesc inamicul. Am definit ceea ce caut, care este o cale. Deci o cale nu este altceva decât o succesiune de vârfuri dintr-un grafic în care fiecare pereche de vârfuri adiacente din acea secvență este o muchie. Cred că toate acestea se aliniază cu intuiția noastră a ceea ce este o cale într-un grafic. Deci, de exemplu, iată o cale p egală cu v1, v2, v3. Deci, observați că există o margine de la v1 la v2 și, de asemenea, o margine de la v2 la v3. Deci, satisface ipotezele expuse în definiția noastră. Ceea ce nu ar fi o cale în graficul nostru - ar fi ca v1 virgula v3, pentru că nu există margine acolo. Bine, deci dacă vorbim despre poteci, atunci există o noțiune foarte naturală care este lungimea. Lungimea, cred că v-ați putea gândi la numărul de vârfuri din calea dvs. minus 1 sau la numărul de muchii pe care le traversează calea. Acestea sunt același lucru. Deci, de exemplu, lungimea căii p aici este 2. Vede toată lumea asta? O eroare de codificare foarte comună pe care o întâlnesc des este să adaug 1 la acel număr din întâmplare. Pentru că, desigur, există un vârf în plus în calea ta decât există muchii. OK, și există multe diferite - ar putea exista mai multe căi între orice pereche de vârfuri. Deci, să presupunem că am un grafic nedirecționat care arată ca următorul. Deci este doar un pătrat plus o diagonală. Deci aici sunt noduri. Deci, o cale perfect valabilă de la stânga jos la dreapta sus ar fi să treci una peste și una în sus, dar, desigur, există o modalitate mai eficientă de a ajunge din stânga jos la dreapta sus, care este să treci peste diagonală. Și atunci când vorbim despre calea cea mai scurtă, nu este nimic mai mult decât lungimea căii care are cel mai puțin număr de muchii sau vârfuri între orice pereche de vârfuri din graficul meu. Bine, deci acesta este inamicul nostru. Aceasta este ceea ce căutăm. Calculează cea mai scurtă cale între vârfuri dintr-un grafic. Și acesta este lucrul despre care vom vorbi destul de mult în acest curs. Pentru că, desigur, este o chestiune foarte practică. La fel ca atunci când vreau să rezolv probleme de rutare, vreau să mut pachetele din rețea mea, aș prefera să nu-- ei bine, dacă nu fac Tor-- aș prefera să nu lovească prea multe computere între ele. Atunci poate vreau un computer cel mai scurt drum. Sau pe o suprafață poate vreau să muți informațiile într-un mod care să nu fie prea departe. Dar, desigur, există un fel de multe variații pe această temă atunci când vorbim despre calea cea mai scurtă sau chiar despre existența unei căi. Deci, acestea sunt trei tipuri de probleme de model pe care le-am putea rezolva pe un grafic. Deci prima, pe care, desigur, o numim accesibilitatea perechii individuale, ar fi ideea că iau două vârfuri s și t pe graficul meu g și vă întreb dacă există o cale între s și t. Deci, care ar fi genul de exemplu extrem în care această problemă poate să nu dea întotdeauna răspunsul da? Cumva, în mintea noastră, cred că ne gândim la toate graficele ca fiind conectate. Dar un grafic perfect valid așa cum l-am definit ar fi ca 10 vârfuri și fără muchii. Această funcție ar fi foarte ușor de codificat dacă acesta ar fi singurul grafic de care ți-ai interesat vreodată. Dar orice eveniment, existența unei căi este deja o interogare care necesită puțină gândire algoritmică. Încă nu ne-am dat seama cum să facem asta. Acum o altă problemă pe care o putem rezolva ar fi calea cea mai scurtă. Având în vedere un grafic și două vârfuri, am putea spune, ei bine, cât de departe sunt aceste vârfuri ale graficului meu dacă vreau să folosesc cea mai scurtă distanță posibilă de la unul la altul. Observați că pot folosi a doua problemă pentru a o rezolva pe prima. Pentru că care este lungimea celei mai scurte căi dintre două vârfuri care nu au o cale între ele? Infinit sau ridicare din umeri... acesta este de fapt un răspuns total valid. Da, asa este. Deci, cum aș putea implementa codul de accesibilitate? Ei bine, aș putea să numesc codul meu cea mai scurtă cale și îmi oferă infinit. Apoi revin nu, nu e accesibil. Și dacă nu-mi dă infinit, revin da. Deci, amintiți-vă că o idee cheie într-o clasă de algoritmi este această idee de reducere. Că pot folosi o funcție pentru a rezolva alta. Deci, în cazul în care, dacă putem rezolva calea cea mai scurtă, atunci cu siguranță putem rezolva problema accesibilității apelând acea bucată de cod. Și apoi, în sfârșit, am putea vorbi despre calea cea mai scurtă cu o singură sursă . Așa că observați acum că există un singur nod de intrare aici s-- așa că ceea ce spune această problemă este să-mi dați lungimea celei mai scurte căi de la s la fiecare alt vârf din graficul meu. Are sens? Ca și cum, poate, returnez o serie mare cu toate informațiile, fiecare distanță cea mai scurtă. Deci, putem rezolva calea cea mai scurtă cu o singură pereche folosind calea cea mai scurtă cu o singură sursă? Absolut. Aș putea să iau s în problema mea cu cea mai scurtă pereche, să calculez cea mai scurtă cale de la s la literalmente orice altceva și apoi să arunc toate acele informații, cu excepția celei mai scurte căi către t, iar acum sunt bine. Acum nu am justificat că acesta este cel mai rapid mod posibil de a rezolva a doua problemă, dar cel puțin arată că dacă pot rezolva problema trei, pot rezolva și problema doi. Dacă pot rezolva din două, pot rezolva și problema unu. Deci, în prelegerea de astăzi, ne vom îngrijora doar de problema trei. Cu alte cuvinte, aceste lucruri sunt oarecum enumerate în ordinea crescătoare a dificultății lor. Bine, așa că pentru a ne gândi la problema cu cea mai scurtă cale cu o singură sursă , vom face o construcție suplimentară. Și aceasta este o idee numită arborele cu calea cea mai scurtă. Am primit leneș să desenez diapozitive PowerPoint la 2:00 AM ieri și, în schimb, m-am gândit să desenez o imagine pe tablă. Deci, să desenăm un grafic. Deci aici avem a, b-- Voi folosi litere în loc de numere pentru a mă referi la noduri de acum înainte, deoarece nu vreau să confund lungimea celei mai scurte căi cu indexul nodului meu. Deci iată a, b, c-- O să-mi potrivesc notele aici-- d, e, f. Iată un grafic, din nou nedirecționat, deoarece instructorului tău îi place să se gândească la graficele nedirecționate. Dar știu că voi primi feedback că nu ar fi trebuit să fac asta mai târziu. Dar, în orice caz, să spunem că vreau să calculez calea cea mai scurtă de la a la orice altceva -- sau mai degrabă lungimea. Deci, în primul rând, chiar și fără a vorbi despre un algoritm, cred că este destul de ușor să ghicim ce este. Deci, în mod clar, cea mai scurtă cale de la a la a are lungimea 0. Cea mai scurtă lungime de la a la b este 1, de la a la c este 2-- pentru că îi pot urmări pe acești tipi. Acum devine complicat. S-a ramificat. Deci următoarea cale cea mai scurtă este lungimea 3 și apoi 4 așa. Sunt toți de acord cu mine că numerele pe care le- am decorat aici sunt lungimea drumului cel mai scurt de la a la orice altceva? Dar ce nu am făcut? Nu ți-am spus cum să calculezi calea, doar ți-am dat lungimea căii. Așa că s-ar putea să vreau o bucată de cod care, pe lângă faptul că face cea mai scurtă lungime a căii cu o singură sursă, îmi oferă și o singură sursă cea mai scurtă cale. Așa că, inițial, când mă gândesc la asta, s-ar putea să mă gândesc, ei bine, cum scriu chiar și o structură de date care poate stoca toate acele căi. Ei bine, fiecare cale ar putea avea ca v vârfuri în ea, corect. S-ar putea ca, indiferent de motiv, să existe o mulțime de ramificații în graficul meu. Și toate căile sunt super lungi. De fapt, cred că trebuie să mă gândesc dacă ramificarea le-ar face mai lungi sau mai scurte. Dar, în orice caz, aș putea avea o structură de date cu adevărat plictisitoare, care doar pentru fiecare vârf ține evidența celei mai scurte căi de la un la acel vârf. Cât de mare ar fi acea structură de date? Ei bine, dacă singura limită pe care o am pe lungimea unei căi este aceea -- cu siguranță cel mult este nevoie de toate vârfurile din graficul meu -- atunci orice cale va ocupa v spațiu. Deci, ar lua v pătrat spațiu total. N-ar fi atât de bine. Pentru că, într-un fel, am o cantitate de informații pe graficul meu care sunt liniare. Este doar lungimea drumului. Dacă vreau să reconstruiesc de fapt acea cale, inițial simt că am nevoie de mult mai mult spațiu pentru a face asta. Dar răspunsul este că, de fapt, nu. Că vom avea nevoie doar de spațiu liniar, iar ideea pentru asta este să stocăm un obiect numit arborele cu calea cea mai scurtă. Da? PUBLIC: Doar pentru [INAUDIBIL] precedent [INAUDIBIL].. JUSTIN SOLOMON: Deci întrebarea a fost despre recursivitate. De fapt, nu am notat niciun algoritm grafic. Așa că vom amâna până când vom recurge efectiv. Și apoi ne vom gândi la asta mai atent. Da, dar este o întrebare absolut rezonabilă. Există o mulțime de algoritmi de grafică recursive. Și atunci, cu siguranță, va trebui să ne numărăm foarte atent. Corect, așa că, în schimb, vom defini un obiect numit arborele cu calea cea mai scurtă. Și trucul de bază aici este să spui, ei bine, cum am ajuns de la a la c? Ei bine, există întotdeauna un vârf, care este predecesorul său, pe calea cea mai scurtă. Și cea mai scurtă cale are această proprietate cu adevărat frumoasă, și anume că cea mai scurtă cale de la a la c, dacă o trunchiez -- corect, deci merge de la a la b la c -- atunci cea trunchiată este și cea mai scurtă cale către acea anterioară vârf. Deci, să ne gândim puțin la asta, pentru că acea propoziție a fost, ca de obicei, prost formulată de către instructorul tău. Deci, să presupunem că am calea cea mai scurtă de la a la d, care este foarte clar a, b, c, d. Cred că putem fi cu toții de acord. Și acum iau ca această sublistă. Mă uit doar de la a la c. Există vreodată o circumstanță în care aceasta nu este cea mai scurtă cale sau cea mai scurtă cale de la a la c? Nu, corect pentru că dacă ar exista o cale mai scurtă de la a la c, aș putea să o îmbină aici și să găsesc cea mai scurtă cale de la a la d. Vezi asta? Deci, pe baza acestui raționament, mai degrabă decât un șir ca acest set uriaș de cele mai scurte căi, un fel de aplicare, într-un fel, de fapt, în unele sensuri, sugestii recursive, în schimb mă pot gândi doar la un vârf care se află în fața mea în calea mea cea mai scurtă. Am de gând să urmăresc înapoi. Deci, să aruncăm o privire la graficul nostru aici. În esență, obiectul pe care îl voi urmări este ca un predecesor, corect. Deci, care este predecesorul lui f pe calea cea mai scurtă? De fapt este fie d, fie e. Nu contează în acest caz. Poate că predecesorul este e pentru distracție, nu. Care este predecesorul lui e? Ei bine, în mod clar vârful anterior de pe calea cea mai scurtă este c. În mod similar, pentru d-- acum avem b și a și o grămadă de săgeți care indică în acest sens. Deci, pentru fiecare vârf, voi începe doar o săgeată îndreptată spre vârful anterior pe calea cea mai scurtă. Nu voi stoca toată calea cea mai scurtă, ci doar ultima margine. Deci, în primul rând, cât de mult spațiu de stocare necesită acest lucru? Este nevoie de v spațiu. Vezi asta? Sau dimensiunea spațiului vârfurilor. Pentru că fiecare vârf trebuie doar să stocheze un singur lucru, care este vârful anterior pe calea cea mai scurtă. Acum ce face algoritmul meu pentru trasarea celei mai scurte căi? Este foarte simplu. Încep doar să merg de-a lungul acestor margini până mă întorc la a. Acum acest obiect se numește arborele cu calea cea mai scurtă. Observați că am introdus un cuvânt suplimentar, care este copac. De ce este asta? Pot avea vreodată un ciclu în acest grafic? Nu ar avea nici un sens, nu. Acestea sunt calea cea mai scurtă. Ar trebui să puteți urmări gradientul înapoi la vârful original. Bine, cu alte cuvinte, o să-mi decorez practic graficul cu un lucru suplimentar. Îl vom numi p din v, care este vârful anterior pe calea cea mai scurtă de la punctul meu sursă la vârful meu v. Și ceea ce cred că am încercat să vă argumentez astăzi este că, dacă am această informație, asta este de fapt. suficient pentru a reconstrui calea cea mai scurtă. Continui să iau p din v și apoi p din p din v și apoi p din p din p din v și așa mai departe, ceea ce sună mai complicat decât este, până când mă întorc la vârful meu original. Și acest obiect din punct de vedere conceptual este numit arborele cu calea cea mai scurtă. Aveți întrebări despre asta? Da? PUBLIC: [INAUDIBIL] JUSTIN SOLOMON: Dacă aș avea o margine care conectează a la d, OK. PUBLIC: [INAUDIBIL] JUSTIN SOLOMON: O, OK, deci întrebarea a fost, să presupunem că colegul nostru de aici a adăugat un avantaj - aceasta este o întrebare grozavă. Știi că cineva a fost rău, rețeaua mea neuronală adversă, a blocat un avantaj aici pentru că era adversar și a vrut să eșueze codul meu cea mai scurtă cale. Și acum, cumva, copacul pe care ți l-am dat nu mai este corect. Și răspunsul meu la asta este da. De ce este asta? Ei bine, adăugând această margine aici, lungimea celui mai scurt drum al meu s-a schimbat. Cea mai scurtă cale de la a la d este acum 1. Deci acest arbore nu mai este valabil. Am nevoie de un copac nou. Deci, acum, care ar fi p-a anterioară a d aici? Ei bine, în loc să fie c, ar fi a. Da, este absolut corect. Și, de fapt, reflectă o proprietate cu adevărat enervantă a căii celei mai scurte, adică dacă adaug o margine la graficul meu, lungimea celei mai scurte căi către fiecare vârf se poate schimba. Ei bine, cred că, cu excepția vârfului sursă. Da, și asta este de fapt o mare durere de cap în anumite aplicații. Așa că, de exemplu, și apoi voi tace despre aplicații și voi face din nou matematică, lucrez mult cu modele 3D. Și există un set mare de date de modele 3D de balerini. Și balerinii sunt chiar enervanti pentru că uneori își pun mâinile împreună așa. Și apoi, brusc, cea mai scurtă cale dintre degetele tale trece de la întregul tău corp la 0. Și astfel, algoritmii incrementali pentru calcularea celei mai scurte căi pot eșua aici, corect. Pentru că trebuie să actualizez ca totul dacă am lipit din greșeală degetele așa. Deci, oricum, vă voi lăsa să vă gândiți cum ați putea rezolva această problemă. Dacă doriți să aflați mai multe, ar trebui să luați 6.838. Da? PUBLIC: [INAUDIBIL]. JUSTIN SOLOMON: Dacă vă schimbați nodul sursă, cea mai scurtă schimbare posibilă din nou. Da, așa că acesta va fi unul dintre aceste lucruri cu adevărat plictisitoare la care voi continua să răspund ca de fiecare dată când schimb ceva la problema mea-- îmi schimb sursa, îmi schimb marginile-- trebuie doar să recalculez toate cele mai scurte căi. Evident, există algoritmi care nu fac asta. Dar nu ne vom gândi încă la ele. BINE. Așa că, ca de obicei, am vorbit prea mult și mi-am lăsat aproximativ 10 minute să fac algoritmul care este interesant în prelegerea de aici -- deși, de fapt, nu este chiar atât de complicat, așa că cred că vom face bine -- ceea ce este cum calculez de fapt cele mai scurte căi? Da, și lucrul de bază pe care îl vom face este să construim pe această analogie arboreală aici. Vom defini încă un obiect, care îmi place foarte mult -- de fapt îmi place asta din notele lui Jason pentru că arată ca calcul și îmi place asta -- și aceasta este o idee a nivelului setat. Și deci acesta este un întreg set de lucruri L sub k. Și acestea sunt toate vârfurile care se află la distanță k de sursa mea. Deci, de exemplu, dacă vârful meu sursă din acest exemplu este vârful din stânga, atunci L0 conține în mod evident doar acel vârf, dreapta. L1 este următorul. L2 este al treilea. Dar acum L3 este un set de trei vârfuri, deoarece acestea sunt toate lucrurile care se află la o distanță de 3 de sursă. Asta am etichetat cu roz aici. OK, deci asta este tot ceea ce înseamnă această notație de aici. Oh, am făcut o ușoară greșeală de scriere pentru că în această clasă distanța este delta și nu d, ci orice. PUBLIC: [INAUDIBIL] JUSTIN SOLOMON: Cea mai scurtă distanță-- este absolut corect. Deci, de exemplu, aș putea avea o distanță foarte mare de la L0 la L2, corect. Aș putea doar să răsturn înainte și înapoi între L0 și L1, poate să trec la L4 și apoi să mă întorc. Dar asta nu ar fi un lucru teribil de util de calculat. Este absolut corect. Da? PUBLIC: [INAUDIBIL]. JUSTIN SOLOMON: O, fundalul roșu este setul L. Deci, de exemplu, L3 conține aceste trei vârfuri pentru că sunt toate lucrurile care sunt la distanță 3 de stânga. Mi-am desenat diagrama puțin prea tare noaptea trecută. Sunt oarecum mândru de asta. OK, deci, în esență, dacă aș dori să calculez lungimea celei mai scurte căi de la tot drumul din stânga la toate celelalte vârfuri, o modalitate de a face asta ar fi să calculez toate aceste seturi de niveluri și apoi să verific ce set de niveluri Sunt înăuntru, corect. Așa că vom introduce un algoritm numit Breadth-First search, care face aproximativ asta. Așadar, căutarea Breadth-First , felul în care o vom prezenta astăzi va fi un algoritm pentru calcularea tuturor acestor seturi de niveluri, L sub i, și apoi, din asta, putem construi lungimea și chiar forma celei mai scurte căi. . Și voi trece la notele mele scrise de mână. OK, și iată ce va face algoritmul nostru. O să-l scriu într- un mod ușor diferit de ceea ce este în note și pe ecran, dar doar puțin. Deci, în primul rând, un lucru despre care cred că putem fi cu toții de acord este că nivelul setului 0-- oh, asta-- această cretă bifurcată-- conține un nod. Care ar trebui să fie acel nod? Sursa, deoarece singurul lucru care se află la o distanță de 0 față de sursă, este nodul sursă. OK, și în plus, putem inițializa distanța de la sursă la ea însăși. Toată lumea pe trei, care este distanța de la sursă la ea însăși-- 1, 2, 3. PUBLIC: 0. JUSTIN SOLOMON: Mulțumesc. Vezi că te trezești acum, este aproape 11:00-- 12:00. Cât este ceasul? Aproape 12:00-- OK, și apoi în sfârșit-- ei bine, poate inițial nu știm cu adevărat nimic despre matricea p, așa că o facem goală. Pentru că p de sursă, cumva nu contează. Pentru că odată ce am ajuns înapoi la sursă, am terminat de calculat calea cea mai scurtă. Deci vom scrie un algoritm care calculează toate seturile de niveluri și completează această matrice p și completează distanțele într-o singură lovitură mare. Îi vom numi căutarea pe lățimea întâi. OK, deci hai să facem asta. Deci putem folosi notația aici. Și observați că, practic, are loc o inducție, și anume voi calcula setul de nivel 1 din setul de nivel 0, setul de nivel 2 din setul de nivel 1 și așa mai departe, până când voi completa toate seturile de nivel. Are sens? Deci, iată un mod ușor diferit de a nota același lucru. Voi folosi o buclă WHILE, care știu că este ușor non-kosher, dar este în regulă. Deci voi inițializa un număr i să fie 1. Acesta va fi ca contorul nostru. O să spun ÎNTÂT timp ce setul de nivel anterior nu este gol, ceea ce înseamnă că, potențial, există o cale care trece prin setul de nivel anterior în următorul. Pentru că de îndată ce unul dintre nivelurile mele este gol, observați că, la fel ca și Li pentru și mai mare, voi fi și eu gol. Nu există ca niciodată un caz când există ceva nu distanța i, ci apoi distanța i plus 5. OK, deci acum ce o să fac? Ei bine, să ne gândim înapoi la graficul nostru. Deci, ca acum, știu că tipul ăsta este la o distanță de 0. Cu asta am început. Așa că acum mă voi uita la toți vecinii acestui vârf. Și o să le fac la distanță de 1. Are sens? Și în mod similar aici, acest tip este la distanța 2. Și, în cele din urmă, o să am probleme pentru că poate... ei bine, ce este un exemplu bun aici. Nici nu voi încerca să desenez. Aș putea avea probleme dacă nu vreau să adaug un vârf de două ori la două seturi de niveluri diferite. Odată ce l-am pus în Li, atunci nu vreau să îl pun în Li plus 5 pentru că știu deja că este distanța de la mine. Are sens? OK, deci ceea ce voi face este să iterez peste toate nodurile din setul meu de nivel anterior . Și acum mă voi uita la fiecare vârf care este adiacent cu u. Pentru că ce știu? Știu că dacă pot ajunge la tine în i minus 1 pași, câți pași ar trebui să îmi ia pentru a ajunge la vreun vecin de-al tău? i pași pentru că pot trece prin cale, care este lungimea i minus 1, adaug o margine suplimentară și voi ajunge la acel tip nou. Deci ce pot face? Pot repeta peste tot v, care se află în setul adiacent de u. Dar trebuie să fiu puțin atent pentru că ce se întâmplă dacă am o margine pe spate? Deci, de exemplu, aici am un avantaj înapoi la sursă. Bănuiesc că acesta este... da, acesta este un exemplu valid. Nu aș vrea să adaug sursa la setul de nivel al treilea, deoarece am adăugat-o deja în tipul anterior. Așa că vreau să scap de unirea tuturor seturilor de nivel anterioare. Are sens? Deci, cu alte cuvinte, mă voi uita doar la vârfurile adiacente pe care nu le-am vizitat încă în algoritmul meu de calcul setat de nivel . Și tot ce trebuie să fac este să-mi actualizez matricele, corect. Deci, în special, voi adăuga vârful v la setul de nivel i pentru că nu am văzut încă v. Voi seta distanța de la s la v egală cu i, deoarece în prezent completez setul meu de nivel i. Și apoi, în sfârșit, ce este p din v? Care este vârful anterior către v în calea mea cea mai scurtă de la sursa mea? Tu ești, corect. Pentru că acesta este tipul din setul de nivel anterior din care îmi construiesc calea, corect. O să-ți pun asta. Și apoi-- îmi pare rău, am rămas fără spațiu-- dar trebuie și să măresc i. OK, deci ce face acest algoritm? Este doar construirea unui set de nivel la un moment dat. Dacă ne întoarcem la imaginea noastră, deci începe prin a inițializa L0 pentru a fi doar vârful sursă, atunci se uită la toate marginile care ies din acela-- în acest caz doar una-- face ca lungimea 1-- și așadar pe. Și astfel, aceasta este doar construirea progresivă a tuturor acestor seturi de niveluri. Acum există o dovadă destul de simplă prin inducție că acest algoritm calculează corect L, p și delte, care sunt toate informațiile de care avem nevoie pentru a calcula calea cea mai scurtă . Cred că puteți face asta în recitarea voastră dacă mai aveți nevoie de puțină practică de inducție aici. Și ultimul lucru pe care ar trebui să-l verificăm este care este timpul de rulare al acestui algoritm. O să-l storc acolo chiar în ultima secundă aici. Deci haideți să aruncăm o privire. Deci, mai întâi de toate, am făcut ceva puțin - oh, nu, este în regulă - în algoritmul meu, de fapt, în pasul zero, a trebuit să fac o matrice care să aibă dimensiunea egală cu numărul de vârfuri. Amintiți-vă că în 6.006 cât timp durează alocarea memoriei? Da, este nevoie de timp proporțional cu cantitatea de memorie pe care o aloc. Deci deja... Steph, văd mâna ta, dar nu avem timp. Deci trebuie să ajungem până la capăt. Am avut deja v timp, deoarece cea mai scurtă matrice a căii noastre ocupă v spațiu. Dar, în plus, avem acest tip de buclă FOR amuzantă în care pentru fiecare nod trebuie să-i vizitez pe toți vecinii săi. Dar mai întâi de toate, văd vreodată un nod de două ori aici? Nu, pentru că merg în ordinea distanței. Și al doilea în care am văzut un nod într-un set de niveluri, nu poate fi în altul. Aceasta este construcția noastră de bază aici. Ei bine, convenabil pentru voi, ați dovedit deja exact formula de care avem nevoie. Și dacă am noroc, nu l-am urmărit. Da, aici suntem. Deci, dacă ne uităm aici, acesta este exact scenariul în care ne aflăm. Pentru că ce am făcut? Am iterat peste toate nodurile din graficul nostru și apoi am iterat peste toți vecinii acelor noduri. Și acesta este timpul de calcul de bază în algoritmul nostru. Așa că bucla FOR, sau mai degrabă acea buclă WHILE, în codul meu durează timp proporțional cu numărul de margini. Deci, care este durata totală de rulare pentru căutarea Breadth-First? Ei bine, trebuie să construim acea matrice. Deci, la pasul zero, am suportat v timp. Și apoi trebuie să repetăm ceva care ocupă cel mai mult numărul de muchii. Deci, în general, algoritmul nostru ia O mare de mod v plus mod e timp. Acum, observați că acest lucru este... s-ar putea să vedeți asta ca fiind redundant. Apropo, asta-- Am o mică dispută cu Jason. Dar în această clasă îl vom numi un algoritm de timp liniar, deoarece este liniar în spațiul pe care îl utilizați pentru a vă stoca graficul. Cred că este puțin neplăcut personal, deoarece această scară ar putea scala pătratic în v, dar mă opresc. În orice caz, de ce avem nevoie de ambii termeni aici? Ei bine, observați că dacă nu aveam margini în graficul meu, acum acest termen va domina. Dar pe măsură ce adaug muchii graficului meu, acest lucru ar putea merge până la v pătrat. Deci, aceasta este cumva o expresie mai informativă decât doar a spune, ei bine, în cel mai rău caz, acesta este timpul v pătrat. Are sens? Este o formulă puțin mai bună . OK, așa că cu asta am scârțâit până la linia de sosire. Avem un algoritm pentru calculul celor mai scurte căi. Și ne vedem din nou, băieți, cred că marți.