Syvä sukellus graafin läpikulkuihin

Maailmanlaajuisesti on yli 2,07 miljardia aktiivista Facebook-käyttäjää kuukausittain vuoden 2017 kolmannella neljänneksellä. Tärkein Facebook-verkon osa on käyttäjien välinen sosiaalinen sitoutuminen. Mitä enemmän ystäviä käyttäjällä on, sitä kiinnostavammista keskusteluista tulee kommentteja viesteihin, viesteihin jne. Jos olet käyttänyt Facebookia melko säännöllisesti, sinun on tiedettävä ystävien suositusominaisuudesta.

Facebook suosittelee joukkoa ihmisiä, jotka voimme lisätä ystävinä. Useimmiten nämä ovat ihmisiä, joista emme ole koskaan ennen kuulleet. Mutta silti Facebook katsoo, että meidän pitäisi lisätä ne. Kysymys kuuluu: miten Facebook antaa joukon suosituksia tietylle henkilölle ?

Yksi tapa tehdä tämä perustuu yhteisiin ystäviin. Esimerkki: - Jos käyttäjä A ja C eivät tunne toisiaan, mutta heillä on yhteinen ystävä B, todennäköisesti myös A: n ja C: n tulisi olla ystäviä. Entä jos A: lla ja C: llä on 2 yhteistä ystävää ja A: lla ja D: llä 3 yhteistä ystävää? Kuinka tilaus tehdään ehdotuksia varten?

Tässä tapauksessa näyttää melko ilmeiseltä ehdottaa D: tä yli C: n A: lle, koska heillä on enemmän yhteisiä ystäviä ja he ovat todennäköisesti yhteydessä toisiinsa.

Kaksi ihmistä ei kuitenkaan välttämättä aina ole yhteisiä ystäviä, mutta heillä voi olla yhteisiä 2. tai 3. asteen yhteyksiä.

N asteen liitännät

  • A ja B ovat ystäviä. (0 astetta)
  • A ja B ovat 1. asteen ystäviä, joten heillä on yhteinen ystävä.
  • A ja B ovat 2. asteen ystäviä, jos heillä on ystävä, joka on toisen asteen ystävä. esim .: - A - C - D - B, sitten A ja B ovat toisen asteen ystäviä.
  • Vastaavasti A ja B ovat N: n asteen ystäviä, jos niiden välillä on N yhteyttä. esim .: - A - X1 - X2 - X3… .. - XN - B.

Tarkasteltaessa tätä suositusta koskevaa lähestymistapaa meidän on pystyttävä löytämään ystävyysaste, jonka kaksi tiettyä käyttäjää jakavat Facebookissa.

Syötä kaavion läpikulut

Nyt kun tiedämme, kuinka Ystäväsuosituksia voidaan tehdä, sanotaan tämä ongelma uudelleen, jotta voimme tarkastella sitä algoritmisesta näkökulmasta.

Kuvitellaan kaikkien Facebookin käyttäjien suuntaamaton kaavio , jossa pisteet V edustavat käyttäjiä ja reunat E edustavat ystävyyssuhteita. Toisin sanoen: jos käyttäjät A ja B ovat ystäviä Facebookissa, huippujen A ja B välillä on reuna. Haasteena on selvittää kahden käyttäjän välisen yhteyden aste.

Muodollisemmin meidän on nähtävä lyhyin etäisyys kahden solmun välillä suuntaamattomassa, painottamattomassa kaaviossa.

Tarkastellaan kahta kärkeä tässä suuntaamattomassa kuvaajassa A ja C. C: n saavuttamiseksi on kaksi erilaista polkua:

1. A → B → C ja

2. A → G → F → E → D → C

Haluamme selvästi mennä pienimmälle polulle, kun yritämme nähdä kahden ihmisen välisen yhteyden asteen sosiaalisessa verkostossa.

Toistaiseksi niin hyvä.

Ennen kuin jatkat, katsotaanpa tämän ongelman monimutkaisuus. Kuten aiemmin todettiin, Facebookilla on noin 2,07 miljardia käyttäjää vuoden 2017 kolmannella neljänneksellä. Tämä tarkoittaa, että kaaviossamme on noin 2,07 miljardia solmua ja vähintään (2,07 miljardia - 1) reunaa (jos jokaisella henkilöllä on ainakin yksi ystävä) .

Tämä on valtava mittakaava tämän ongelman ratkaisemiseksi. Lisäksi näimme myös, että kaaviosta voi olla useita polkuja päästä tietystä lähdepisteestä kohdepisteeseen, ja haluamme, että lyhyin ratkaisee ongelmamme.

Tarkastelemme kahta klassista graafin läpikulun algoritmia ongelmamme ratkaisemiseksi:

1. Syvyys Ensimmäinen haku ja

2. Leveys ensimmäinen haku.

Syvyys Ensimmäinen haku

Kuvittele, että olet jumissa tällaisessa sokkelossa.

Sinun täytyy päästä pois jotenkin. Lähtökohdasta poistumispaikkaan voi olla useita reittejä. Luonnollinen tapa päästä ulos sokkelosta on kokeilla kaikkia polkuja.

Oletetaan, että sinulla on kaksi vaihtoehtoa siinä vaiheessa, kun seisot. Ilmeisesti et tiedä kumpi johtaa sokkelosta. Joten päätät tehdä ensimmäisen valinnan ja siirtyä eteenpäin sokkelossa.

Teet jatkuvasti liikkeitä ja jatkat eteenpäin ja olet umpikujassa. Nyt haluaisit mieluiten kokeilla eri polkua, joten palaat takaisin edelliseen tarkistuspisteeseen, jossa teit yhden valinnoista, ja yrität sitten uutta eli toista polkua tällä kertaa.

Teet tätä, kunnes löydät uloskäynnin.

Tietyn polun rekursiivinen kokeilu ja paluu ovat kaksi komponenttia, jotka muodostavat syvyyden ensimmäisen haun algoritmin (DFS).

Jos mallinnamme sokkelo-ongelman graafina, pisteet edustaisivat yksilön asemaa sokkelossa ja kahden solmun väliset suunnatut reunat edustaisivat yhtä siirtoa paikasta toiseen. DFS: n avulla henkilö kokeili kaikkia mahdollisia reittejä, kunnes poistuminen löytyy.

Tässä on näyte näennäiskoodista samalle.

1 procedure DFS(G,v):2 label v as discovered3 for all edges from v to w in G.adjacentEdges(v) do4 if vertex w is not labeled as discovered then5 recursively call DFS(G,w)

Saat syvemmän sukelluksen tähän algoritmiin tutustumalla: -

Syvä sukellus kaavion läpi: DFS-läpikulku

Hyvästä tai pahasta, aina on enemmän kuin yksi tapa tehdä jotain. Onneksi meille, ohjelmistojen ja… medium.com -maailmassa

Ajan monimutkaisuus: O (V + E)

Leveys ensimmäinen haku

Kuvittele tarttuvaa tautia, joka leviää vähitellen alueelle. Joka päivä sairaudesta kärsivät ihmiset tartuttavat uusia ihmisiä, joiden kanssa he ovat fyysisessä kontaktissa. Tällä tavoin tauti tekee eräänlaista etsintää (BFS) väestön yli. "Jono" on joukko ihmisiä, jotka ovat juuri saaneet tartunnan. Kaavio on alueen fyysinen yhteysverkko.

Kuvittele, että sinun on simuloitava taudin leviämistä tämän verkon kautta. Haun juurisolmu on potilas nolla, ensimmäinen tunnettu taudista kärsivä. Aloitat vain heillä, joilla on tauti, eikä kukaan muu.

Toistat nyt ihmisiä, joiden kanssa he ovat yhteydessä. Jotkut saavat taudin. Toista nyt ne kaikki. Anna myös ihmisille, joilla he ovat kosketuksissa taudin kanssa, ellei heillä ole jo ollut sitä. Jatka, kunnes olet tartuttanut kaikki tai olet tartuttanut kohteen. Sitten olet valmis. Näin leveys ensimmäinen haku toimii.

BFS-hakualgoritmi tutkii pisteitä kerrokselta kerrokselta alkaen ensimmäisestä kärjestä ja siirtymällä seuraavaan kerrokseen vasta kun kaikki nykyisen kerroksen pisteet on käsitelty.

Tässä on näyte näennäiskoodista BFS: lle.

1 procedure BFS(G, v):2 q = Queue()3 q.enqueue(v)4 while q is not empty:5 v = q.dequeue()6 if v is not visited:7 mark v as visited (// Process the node)8 for all edges from v to w in G.adjacentEdges(v) do9 q.enqueue(w)

Tutustu BFS: n syvempään ymmärtämiseen tutustumalla tähän artikkeliin.

Ajan monimutkaisuus: O (V + E)

Lyhyimmät polut

Siirrytään eteenpäin ja ratkaistaan ​​alkuperäinen ongelma: etsitään lyhin polku kahden annetun kärjen välillä suuntaamattomasta kaaviosta.

Tarkasteltaessa näiden kahden algoritmin ajan monimutkaisuutta emme todellakaan pysty erottamaan näiden kahden välistä eroa tämän ongelman kannalta. Molemmat algoritmit löytävät polun (tai pikimmin lyhimmän polun) määränpäämme annetusta lähteestä.

Katsotaanpa seuraavaa esimerkkiä.

Oletetaan, että haluamme selvittää lyhimmän polun solmusta 8-10 . Katsotaanpa solmut, joita DFS ja BFS tutkivat ennen määränpäähän saapumista.

DFS

  • Prosessi 8 → Prosessi 3 → Prosessi 1.
  • Takaisin kohtaan 3.
  • Prosessi 6 → Prosessi 4.
  • Takaisin kappaleeseen 6.
  • Prosessi 7.
  • Paluu 6 → Takaisin 3 → Takaisin 8.
  • Prosessi 10 .

A total of 7 nodes are being processed here before the destination is reached. Now let’s look at how BFS does things.

BFS

  • Process 8 → Enqueue 3, 10
  • Process 3 → Enqueue 1,6
  • Process 10.

Woah, that was fast! Just 3 nodes had to be processed and we were at our destination.

The explanation for this speedup that we can see in BFS and not in DFS is because DFS takes up a specific path and goes till the very end i.e. until it hits a dead end and then backtracks.

This is the major downfall of the DFS algorithm. It might have to expand 1000s of levels (in a huge network like that of Facebook, just because it selected a bad path to process in the very beginning) before reaching the path containing our destination. BFS doesn’t face this problem and hence is much faster for our problem.

Additionally, even if DFS finds out the destination, we cannot be sure that the path taken by DFS is the shortest one. There might be other paths as well.

That means that in any case, for the shortest paths problem, DFS would have to span the entire graph to get the shortest path.

In the case of BFS, however, the first occurrence of the destination node ensures that it is the one at the shortest distance from the source.

Conclusion

So far we discussed the problem of Friends Recommendation by Facebook and we boiled it down to the problem of finding the degree of connections between two users in the network graph.

Then we discussed two interesting Graph Traversal algorithms that are very commonly used. Finally, we looked at which algorithm performs the best for solving our problem.

Breadth First Search is the algorithm you want to use if you have to find the shortest distance between two nodes in an undirected, unweighted graph.

Let’s look at this fun problem to depict the difference between the two algorithms.

Assuming that you’ve read the problem statement carefully, let’s try and model this as a graph problem in the first place.

Let all possible strings become nodes in the graph and we have an edge between two vertices if they have a single mutation between them.

Easy, right?

We are given a starting string (read source vertext) eg:- “AACCGGTT” and we have to reach the destination string (read destination vertex) “AACCGGTA” in minimum number of mutations (read minimum number of steps) such that all intermediate strings (nodes) should belong to the given word bank.

Yritä ratkaista tämä ongelma itse, ennen kuin tarkastelet alla olevaa ratkaisua.

Jos yrität ratkaista sen DFS: n avulla, keksit varmasti ratkaisun, mutta on olemassa testitapauksia, jotka ylittävät LeetCode-alustan sallitun aikarajan. Tämä johtuu aiemmin kuvatusta ongelmasta, miksi DFS vie niin kauan (prosessoi 7 solmua eikä 3 BFS: ssä) päästä kohdepisteeseen.

Toivottavasti saat pääidean kahden päädiagrammin läpikäynnin takana ja niiden välisen eron, kun sovellus on lyhimpiä polkuja suuntaamattomassa painottamattomassa kaaviossa.

Suosittele (❤) tätä viestiä, jos luulet tämän olevan hyödyllinen jollekulle!