Deep Dive Into Graph Traversals

Det er over 2,07 milliarder aktive Facebook-brukere månedlig over hele verden fra 3. kvartal 2017. Det viktigste aspektet ved Facebook-nettverket er det sosiale engasjementet mellom brukerne. Jo flere venner en bruker har, desto mer engasjerende blir samtalene via kommentarer på innlegg, meldinger osv. Hvis du har brukt Facebook ganske regelmessig, må du vite om Friends Recommendation-funksjonen.

Facebook anbefaler et sett med mennesker som vi kan legge til som venner. Dette er folk som vi aldri har hørt om før. Men likevel mener Facebook at vi bør legge dem til. Spørsmålet er: Hvordan kommer Facebook med et sett med anbefalinger for en bestemt person ?

En måte å gjøre dette på er basert på felles venner. f.eks: - Hvis en bruker A og C ikke kjenner hverandre, men de har en felles venn B, så burde A og C sannsynligvis også være venner. Hva om A og C har to felles venner og A og D har 3 felles venner? Hvordan vil bestillingen være for forslag?

I dette tilfellet virker det ganske åpenbart å foreslå D over C til A fordi de har flere felles venner og er mer sannsynlig å bli koblet.

Imidlertid kan to personer ikke alltid ha felles venner, men de kan ha felles 2.-graders eller 3.-graders forbindelser.

Nth Degree Connections

  • A og B er venner. (0 grader)
  • A og B er første grads venner, betyr at de har en felles venn.
  • A og B er 2. grads venner hvis de har en venn, som er en 1. grads venn med den andre personen. f.eks: - A - C - D - B, så er A og B 2. grads venner.
  • Tilsvarende er A og B N- graders venner hvis de har N-forbindelser i mellom. f.eks: - A - X1 - X2 - X3 ... .. - XN - B.

Når vi ser på denne tilnærmingen for anbefalingen, må vi kunne finne graden av vennskap som to gitte brukere deler på Facebook.

Angi grafgjenkjenninger

Nå som vi vet hvordan venneanbefalinger kan gjøres, la oss gjenta dette problemet slik at vi kan se på det fra et algoritmisk perspektiv.

La oss forestille oss en ikke-rettet graf av alle brukerne på Facebook , der hjørner V representerer brukerne og kantene E representerer vennskap. Med andre ord: hvis brukerne A og B er venner på Facebook, er det en kant mellom hjørnene A og B. Utfordringen er å finne ut graden av forbindelse mellom to brukere.

Mer formelt må vi se den korteste avstanden mellom to noder i en ikke-rettet, uvektet graf.

Tenk på to hjørner i denne ikke-rettet grafen A og C. Det er to forskjellige veier for å nå C:

1. A → B → C og

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

Det er klart at vi ønsker å gå den minste veien når vi prøver å se graden av forbindelse mellom to personer på det sosiale nettverket.

Så langt så bra.

Før vi fortsetter, la oss se på kompleksiteten i dette problemet. Som nevnt tidligere har Facebook rundt 2,07 milliarder brukere per 3. kvartal 2017. Det betyr at grafen vår vil ha rundt 2,07 milliarder noder og minst (2,07 milliarder - 1) kanter (hvis hver person har minst en venn) .

Dette er en enorm skala å løse dette problemet på. I tillegg så vi også at det kan være flere baner å nå fra en gitt kildepunkt til en destinasjonspunkts i grafen, og vi vil at den korteste skal løse problemet vårt.

Vi vil se på to klassiske algoritmer for grafgjennomgang for å løse problemet vårt:

1. Dybde første søk og

2. Bredde første søk.

Dybde første søk

Se for deg at du blir sittende fast i en labyrint som denne.

Du må komme deg ut på en eller annen måte. Det kan være flere ruter fra startposisjonen til utgangen. Den naturlige tilnærmingen til å komme seg ut av labyrinten er å prøve alle stiene.

La oss si at du har to valg på det punktet hvor du for øyeblikket står. Åpenbart vet du ikke hvilken som fører ut av labyrinten. Så du bestemmer deg for å ta førstevalget og gå videre i labyrinten.

Du fortsetter å bevege deg og du fortsetter fremover og du treffer en blindvei. Nå vil du ideelt sett prøve en annen vei, og så gå tilbake til et tidligere sjekkpunkt der du tok et av valgene, og deretter prøve en ny, dvs. en annen vei denne gangen.

Du fortsetter å gjøre dette til du finner utgangen.

De to komponentene som danner dybden første søkealgoritmen (DFS) er rekursivt å prøve ut en bestemt bane og backtracking .

Hvis vi modellerer labyrintproblemet som en graf, vil toppunktene representere individets posisjon på labyrinten, og rettet kant mellom to noder vil representere et enkelt trekk fra en posisjon til en annen posisjon. Ved å bruke DFS, ville personen prøve alle mulige ruter til avkjørselen er funnet.

Her er et eksempel på en pseudokode for det samme.

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)

For en dypere dykking i denne algoritmen, sjekk ut: -

Deep Dive Through A Graph: DFS Traversal

På godt og vondt er det alltid mer enn én måte å gjøre noe på. Heldigvis for oss, i verden av programvare og ... medium.com

Tidskompleksitet: O (V + E)

Bredde første søk

Tenk deg en smittsom sykdom som gradvis sprer seg over en region. Hver dag smitter menneskene som har sykdommen nye mennesker de kommer i fysisk kontakt med. På denne måten gjør sykdommen en slags bred-første-søk (BFS) over befolkningen. "Køen" er settet med mennesker som nettopp har blitt smittet. Grafen er det fysiske kontaktnettverket i regionen.

Tenk deg at du må simulere spredningen av sykdommen gjennom dette nettverket. Rotnoden til søket er pasient null, den første kjente lidelsen av sykdommen. Du begynner med bare dem med sykdommen, og ingen andre.

Now you iterate over the people they are in contact with. Some will catch the disease. Now iterate over all of them. Give the people they’re in contact with the disease too, unless they’ve already had it. Keep going until you’ve infected everyone, or you’ve infected your target. Then you’re done. That’s how breadth-first-search works.

The BFS search algorithm explores vertices layer by layer starting at the very first vertex and only moving on to the next layer once all vertices on the current layer have been processed.

Here is a sample pseudo-code for BFS.

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)

For a deeper understanding of BFS, look into this article.

Time Complexity: O(V + E)

Shortest Paths

Let’s move forward and solve our original problem: finding the shortest path between two given vertices in an undirected graph.

Looking at the time complexities of the two algorithms, we can’t really make out the difference between the two for this problem. Both the algorithms will find a path (or rather the shortest path) to our destination from the given source.

Let’s look at the following example.

Suppose we want to find out the shortest path from the node 8 to 10. Let’s look at the nodes that DFS and BFS explore before reaching the destination.

DFS

  • Process 8 → Process 3 → Process 1.
  • Backtrack to 3.
  • Process 6 → Process 4.
  • Backtrack to 6.
  • Process 7.
  • Backtrack to 6 → Backtrack to 3 → Backtrack to 8.
  • Process 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.

Prøv å løse dette problemet på egenhånd før du ser på løsningen nedenfor.

Hvis du prøver å løse det ved hjelp av DFS, vil du helt sikkert komme med en løsning, men det er en testsak (er) som vil overskride den tildelte tidsgrensen på LeetCode-plattformen. Det er på grunn av problemet som er beskrevet tidligere på hvorfor DFS tar så lang tid (prosess 7 noder i motsetning til 3 i BFS) for å nå destinasjonspunktet.

Håper du har hovedideen bak de to hovedgraver, og forskjellen mellom dem når applikasjonen er korteste stier i en ikke-rettet uvektet graf.

Vennligst anbefalt (❤) dette innlegget hvis du tror dette kan være nyttig for noen!