Dyb dybt ned i grafgennemgange

Der er over 2,07 milliarder aktive Facebook-brugere månedligt over hele verden fra 3. kvartal 2017. Det vigtigste aspekt af Facebook-netværket er det sociale engagement mellem brugerne. Jo flere venner en bruger har, desto mere engagerende bliver samtalerne via kommentarer til indlæg, messaging osv. Hvis du har brugt Facebook temmelig regelmæssigt, skal du vide noget om funktionen Friends Anbefaling.

Facebook anbefaler et sæt mennesker, som vi kan tilføje som venner. De fleste gange er det mennesker, vi aldrig har hørt om før. Men stadig mener Facebook, at vi skal tilføje dem. Spørgsmålet er: hvordan kommer Facebook med et sæt anbefalinger til en bestemt person ?

En måde at gøre dette på er baseret på fælles venner. fx: - Hvis en bruger A og C ikke kender hinanden, men de har en fælles ven B, så skulle sandsynligvis også A og C være venner. Hvad hvis A og C har to fælles venner og A og D har 3 fælles venner? Hvordan vil bestillingen være for forslag?

I dette tilfælde synes det ret oplagt at foreslå D over C til A, fordi de har flere fælles venner og er mere tilbøjelige til at blive forbundet.

Imidlertid har to personer måske ikke altid fælles venner, men de kan have fælles 2.-graders eller 3.-graders forbindelser.

N-graders forbindelser

  • A og B er venner. (0 grader)
  • A og B er 1.-graders venner betyder, at de har en fælles ven.
  • A og B er 2.-graders venner, hvis de har en ven, som er en 1.-graders ven med den anden person. f.eks: - A - C - D - B, så er A og B 2. graders venner.
  • Tilsvarende er A og B N- graders venner, hvis de har N-forbindelser imellem. f.eks: - A - X1 - X2 - X3 ... .. - XN - B.

Når vi ser på denne tilgang til anbefalingen, skal vi være i stand til at finde den grad af venskab, som to givne brugere deler på Facebook.

Indtast Graph Traversals

Nu hvor vi ved, hvordan venneanbefalinger kan laves, lad os gentage dette problem, så vi kan se på det fra et algoritmisk perspektiv.

Lad os forestille os en ikke-rettet graf over alle brugerne på Facebook , hvor hjørner V repræsenterer brugerne og kanter E repræsenterer venskaber. Med andre ord: hvis brugerne A og B er venner på Facebook, er der en kant mellem hjørnerne A og B. Udfordringen er at finde ud af graden af ​​forbindelse mellem to brugere.

Mere formelt er vi nødt til at se den korteste afstand mellem to noder i en ikke-rettet, ikke-vægtet graf.

Overvej to hjørner i denne ikke-rettet graf A og C. Der er to forskellige veje til at nå C:

1. A → B → C og

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

Det er klart, at vi vil tage den mindste vej, når vi prøver at se graden af ​​forbindelse mellem to personer på det sociale netværk.

Så langt så godt.

Lad os se på kompleksiteten af ​​dette problem, inden du fortsætter. Som tidligere nævnt har Facebook omkring 2,07 milliarder brugere pr. 3. kvartal 2017. Det betyder, at vores graf vil have omkring 2,07 milliarder noder og mindst (2,07 milliarder - 1) kanter (hvis hver person har mindst en ven) .

Dette er en enorm skala at løse dette problem på. Derudover så vi også, at der muligvis er flere stier at nå fra en given kildepunkt til et destinationspunkt i grafen, og vi vil have den korteste til at løse vores problem.

Vi vil se på to klassiske grafgennemgangsalgoritmer for at løse vores problem:

1. Dybde første søgning og

2. Bredde første søgning.

Dybde første søgning

Forestil dig, at du sidder fast i en labyrint som denne.

Du er nødt til at komme ud på en eller anden måde. Der kan være flere ruter fra din startposition til afgangen. Den naturlige tilgang til at komme ud af labyrinten er at prøve alle stier.

Lad os sige, at du har to valg på det punkt, hvor du i øjeblikket står. Du ved selvfølgelig ikke, hvilken der fører ud af labyrinten. Så du beslutter dig for at træffe det første valg og gå videre i labyrinten.

Du fortsætter med at bevæge dig, og du fortsætter med at komme fremad, og du rammer en blindgyde. Nu vil du ideelt set prøve en anden sti, og så gå tilbage til et tidligere kontrolpunkt, hvor du har foretaget et af valgene, og derefter prøver du en ny, dvs. en anden sti denne gang.

Du fortsætter med at gøre dette, indtil du finder udgangen.

Rekursivt at afprøve en bestemt sti og backtracking er de to komponenter, der danner Depth First Search algoritmen (DFS).

Hvis vi modellerer labyrintproblemet som en graf, vil hjørnerne repræsentere individets position på labyrinten, og de rettede kanter mellem to noder repræsenterer et enkelt træk fra en position til en anden position. Ved hjælp af DFS vil personen prøve alle mulige ruter, indtil udgangen er fundet.

Her er en prøve 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 et dybere dykke ned i denne algoritme, tjek: -

Dybdyk gennem en graf: DFS Traversal

På godt og ondt er der altid mere end én måde at gøre noget på. Heldigvis for os i verden af ​​software og ... medium.com

Tidskompleksitet: O (V + E)

Bredde første søgning

Forestil dig en smitsom sygdom, der gradvist spredes over en region. Hver dag inficerer de mennesker, der har sygdommen, nye mennesker, de kommer i fysisk kontakt med. På denne måde udfører sygdommen en slags bred-første-søgning (BFS) over befolkningen. "Køen" er det sæt mennesker, der lige er blevet inficeret. Grafen er regionens fysiske kontaktnetværk.

Forestil dig, at du har brug for at simulere sygdommens spredning gennem dette netværk. Rødknudepunktet for søgningen er patient nul, den første kendte syge. Du starter med bare dem med sygdommen og ingen andre.

Nu gentager du de mennesker, de er i kontakt med. Nogle vil få sygdommen. Nu gentages over dem alle. Giv også de mennesker, de er i kontakt med sygdommen, medmindre de allerede har haft den. Fortsæt, indtil du har inficeret alle, eller du har inficeret dit mål. Så er du færdig. Sådan fungerer bredde-første-søgning.

BFS-søgealgoritmen udforsker hjørner lag for lag, der starter ved det allerførste toppunkt og kun går videre til det næste lag, når alle hjørner på det aktuelle lag er blevet behandlet.

Her er en prøve pseudokode til 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 at få en dybere forståelse af BFS, se på denne artikel.

Tidskompleksitet: O (V + E)

Korteste stier

Lad os gå videre og løse vores oprindelige problem: at finde den korteste sti mellem to givne hjørner i en ikke-rettet graf.

Når man ser på tidskompleksiteten af ​​de to algoritmer, kan vi ikke rigtig finde ud af forskellen mellem de to for dette problem. Begge algoritmer finder en sti (eller rettere den korteste sti) til vores destination fra den givne kilde.

Lad os se på følgende eksempel.

Antag, at vi vil finde ud af den korteste sti fra knudepunktet 8 til 10 . Lad os se på de noder, som DFS og BFS udforsker, inden vi når destinationen.

DFS

  • Process 8 → Process 3 → Process 1.
  • Backtrack til 3.
  • Process 6 → Process 4.
  • Backtrack til 6.
  • Fremgangsmåde 7.
  • Backtrack til 6 → Backtrack til 3 → Backtrack til 8.
  • Fremgangsmåde 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 at løse dette problem alene, før du ser på løsningen nedenfor.

Hvis du prøver at løse det ved hjælp af DFS, vil du helt sikkert komme med en løsning, men der er en eller flere testtilfælde, der overskrider den tildelte tidsgrænse på LeetCode-platformen. Det er på grund af det tidligere beskrevne problem med, at DFS tager så lang tid (proces 7 noder i modsætning til 3 i BFS) for at nå destinationspunktet.

Håber, du har hovedideen bag de to hovedgraver, og forskellen mellem dem, når applikationen er korteste stier i en ikke-rettet ikke-vægtet graf.

Anbefal (❤) dette indlæg, hvis du tror, ​​det kan være nyttigt for nogen!