Hlboké ponory do grafov

K 3. štvrťroku 2017 je na svete viac ako 2,07 miliárd aktívnych používateľov Facebooku. Najdôležitejším aspektom siete Facebook je sociálna angažovanosť medzi používateľmi. Čím viac priateľov má používateľ, tým pútavejšie sú konverzácie prostredníctvom komentárov k príspevkom, správ atď. Ak ste Facebook používali pomerne pravidelne, musíte vedieť o funkcii Odporúčanie priateľov.

Facebook odporúča skupinu ľudí, ktorých si môžeme pridať ako priateľov. Väčšinou sú to ľudia, o ktorých sme nikdy predtým nepočuli. Napriek tomu si Facebook myslí, že by sme ich mali pridať. Otázka znie: ako Facebook prichádza so súborom odporúčaní pre konkrétnu osobu ?

Jeden spôsob, ako to dosiahnuť, je založený na spoločných priateľoch. napr .: - Ak sa používatelia A a C navzájom nepoznajú, ale majú spoločného priateľa B, potom by pravdepodobne aj A a C mali byť priateľmi. Čo ak majú A a C 2 spoločné kamarátky a A a D 3 spoločné kamarátky? Aké bude poradie návrhov?

V tomto prípade sa zdá celkom zrejmé, navrhnúť D cez C až A, pretože majú viac spoločných priateľov a je pravdepodobnejšie, že sa spoja.

Dvaja ľudia však nemusia mať vždy spoločných priateľov, ale môžu mať spoločné kontakty 2. alebo 3. stupňa.

Pripojenia n-tého stupňa

  • A a B sú priatelia. (0 stupňov)
  • A a B sú priatelia prvého stupňa znamená, že majú spoločného priateľa.
  • A a B sú kamaráti druhého stupňa, ak majú priateľa, ktorý je s druhou osobou priateľom prvého stupňa. napr .: - A - C - D - B, potom A a B sú priatelia druhého stupňa.
  • Podobne sú A a B priatelia N-tého stupňa, ak majú medzi sebou N spojenia. napr .: - A - X1 - X2 - X3 ... .. - XN - B.

Pri pohľade na tento prístup k odporúčaniu musíme byť schopní nájsť mieru priateľstva, ktorú dvaja uvedení používatelia zdieľajú na Facebooku.

Zadajte priechody grafov

Teraz, keď vieme, ako sa dajú robiť odporúčania priateľov, prepracujme tento problém, aby sme sa na neho mohli pozrieť z algoritmického hľadiska.

Poďme si predstaviť neusmernený graf všetkých používateľov na Facebooku , kde vrcholy V predstavujú používateľov a hrany E predstavujú priateľstvá. Inými slovami: ak sú používatelia A a B priateľmi na Facebooku, medzi vrcholmi A a B je hranica. Výzvou je zistiť mieru spojenia medzi ľubovoľnými dvoma používateľmi.

Formálnejšie musíme vidieť najkratšiu vzdialenosť medzi dvoma uzlami v neusmernenom neváženom grafe.

Zvážte dva vrcholy v tomto neorientovanom grafe A a C. Existujú dva rôzne spôsoby dosiahnutia C:

1. A → B → C a

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

Je zrejmé, že sa chceme uberať najmenšou cestou, keď sa snažíme zistiť mieru prepojenia medzi dvoma ľuďmi na sociálnej sieti.

Zatiaľ je všetko dobré.

Pred pokračovaním sa pozrime na zložitosť tohto problému. Ako už bolo uvedené, Facebook má k 3. štvrťroku 2017 približne 2,07 miliardy používateľov. To znamená, že náš graf bude mať približne 2,07 miliardy uzlov a najmenej (2,07 miliardy - 1) hrán (ak má každý človek aspoň jedného priateľa) .

Na vyriešenie tohto problému je to obrovský rozsah. Ďalej sme tiež videli, že v grafe môže byť viac ciest, ako sa dostať z daného zdrojového vrcholu do cieľového, a chceme, aby náš problém vyriešil ten najkratší.

Na vyriešenie nášho problému sa pozrieme na dva klasické algoritmy prechodu grafov:

1. Hĺbkové prvé vyhľadávanie a

2. Šírka prvého vyhľadávania.

Hĺbka prvého vyhľadávania

Predstavte si, že uviaznete v takom bludisku.

Musíte sa nejako dostať von. Z vašej východiskovej polohy k východu môže byť niekoľko trás. Prirodzeným prístupom k výstupu z bludiska je vyskúšať všetky cesty.

Povedzme, že máte dve možnosti v mieste, kde momentálne stojíte. Je zrejmé, že neviete, ktorý vedie z bludiska. Takže sa rozhodnete pre prvú voľbu a pokračujete ďalej v bludisku.

Stále robíte pohyby a idete ďalej a narazíte do slepej uličky. Teraz by ste v ideálnom prípade chceli vyskúšať inú cestu, a tak sa vrátite späť k predchádzajúcemu kontrolnému bodu, kde ste vykonali jednu z možností, a potom vyskúšate novú, tj. Tentokrát inú cestu.

Stále to robíte, kým nenájdete východ.

Recursively trying out a specific path and backtracking are the two components forming the Depth First Search algorithm (DFS).

If we model the maze problem as a graph, the vertices would represent the individual’s position on the maze and directed edges between two nodes would represent a single move from one position to another position. Using DFS, the individual would try all possible routes until the exit is found.

Here is a sample pseudo-code for the same.

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 a deeper dive into this algorithm, check out :-

Deep Dive Through A Graph: DFS Traversal

For better or for worse, there’s always more than one way to do something. Luckily for us, in the world of software and…medium.com

Time Complexity: O(V + E)

Breadth First Search

Imagine a contagious disease gradually spreading across a region. Every day, the people who have the illness infect new people they come into physical contact with. In this way, the disease is doing a sort of breadth-first-search(BFS) over the population. The “queue” is the set of people who have just been infected. The graph is the physical contact network of the region.

Imagine you need to simulate the spread of the disease through this network. The root node of the search is patient zero, the first known sufferer of the disease. You start off with just them with the disease, and no one else.

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.

Skúste tento problém vyriešiť sami, skôr ako sa pozriete na riešenie uvedené nižšie.

Ak sa to pokúsite vyriešiť pomocou DFS, určite prídete s riešením, ale existuje testovací prípad, ktorý prekročí stanovený časový limit na platforme LeetCode. Je to z dôvodu vyššie popísaného problému, prečo DFS trvá dosiahnutie cieľového vrcholu tak dlho (proces 7 uzlov na rozdiel od 3 v BFS).

Dúfam, že ste získali hlavnú myšlienku za dvoma hlavnými prechodmi grafu a rozdiel medzi nimi, keď je aplikácia najkratšími cestami v neorientovanom neváženom grafe.

Odporučte (this) tento príspevok, ak si myslíte, že by to mohlo byť pre niekoho užitočné!