2017 harmadik negyedévében világszerte több mint 2,07 milliárd aktív Facebook-felhasználó van világszerte. A Facebook-hálózat legfontosabb szempontja a felhasználók közötti társadalmi elkötelezettség. Minél több barátja van a felhasználónak, annál vonzóbbá válnak a beszélgetések a bejegyzések, az üzenetküldés stb. Megjegyzései révén. Ha a Facebookot elég rendszeresen használta, akkor ismernie kell a Barátok ajánlása funkciót.
A Facebook egy sor embert ajánl, akiket felvehetünk barátként. Legtöbbször olyan emberekről van szó, akikről még soha nem hallottunk. De a Facebook úgy gondolja, hogy hozzá kellene adnunk őket. A kérdés a következő: hogyan állít elő a Facebook egy ajánlást egy adott személy számára ?
Ennek egyik módja a közös barátok. pl .: - Ha egy A és C felhasználó nem ismerik egymást, de van közös B barátjuk, akkor valószínűleg A és C is barátok. Mi van, ha A-nak és C-nek 2 közös barátja van, A-nak és D-nek pedig 3 közös barátja van? Milyen lesz a rendelés a javaslatokhoz?
Ebben az esetben elég kézenfekvőnek tűnik D-t javasolni C helyett A-nak, mert több közös barátjuk van, és valószínűbb, hogy kapcsolatba kerülnek.
Két embernek azonban nem mindig vannak közös barátai, de lehetnek közös 2. vagy 3. fokú kapcsolatai.
N-edik fokú kapcsolatok
- A és B barátok. (0 fok)
- A és B 1. fokú barátok azt jelenti, hogy van közös barátjuk.
- A és B 2. fokú barátok, ha van barátjuk, aki 1. fokú barát a másik személlyel. pl .: - A - C - D - B, akkor A és B 2. fokú barátok.
- Hasonlóképpen, A és B N-edik fokú barátok, ha közöttük N kapcsolat van. pl .: - A - X1 - X2 - X3… .. - XN - B.
Az ajánlás ezen megközelítését tekintve meg kell tudnunk találni azt a barátsági fokot, amelyet két adott felhasználó megoszt a Facebookon.
Adja meg a grafikon bejárását
Most, hogy tudjuk, miként készíthetők a Baráti ajánlások, fogalmazzuk meg újra ezt a problémát, hogy algoritmikus szemszögből nézhessük meg.
Képzeljük el a Facebook összes felhasználójának irányítatlan grafikonját , ahol a V csúcsok a felhasználókat, az E élek pedig a barátságokat jelentik. Más szavakkal: ha A és B felhasználó barátok a Facebookon, akkor az A és B csúcs között él van. A kihívás az, hogy megtudjuk a két felhasználó közötti kapcsolat mértékét.
Formálisabban meg kell látnunk a legrövidebb távolságot két csomópont között egy irányítatlan, súlyozatlan gráfban.
Tekintsünk két csúcsot ebben az irányítatlan A és C grafikonban. A C eléréséhez két különböző út van:
1. A → B → C és
2. A → G → F → E → D → C
Nyilvánvaló, hogy a legkisebb utat akarjuk megtenni, amikor megpróbáljuk meglátni két ember kapcsolatának mértékét a közösségi hálózaton.
Eddig jó.
A folytatás előtt nézzük meg a probléma összetettségét. Amint azt korábban említettük, a Facebooknak 2017 harmadik negyedévében körülbelül 2,07 milliárd felhasználója van. Ez azt jelenti, hogy grafikonunknak körülbelül 2,07 milliárd csomópontja és legalább (2,07 milliárd - 1) éle lesz (ha minden embernek van legalább egy barátja) .
Ez óriási léptékű a probléma megoldására. Ezenkívül azt is láttuk, hogy egy adott forráscsúcstól egy célcsúcsig több út is elérhető lehet a grafikonon, és szeretnénk, ha a legrövidebb megoldaná a problémánkat.
Két klasszikus gráf-bejárási algoritmust vizsgálunk meg a problémánk megoldására:
1. Mélység Első keresés és
2. Szélesség első keresés.
Mélység Első keresés
Képzelje el, hogy elakadt egy ilyen labirintusban.
Valahogy ki kell jönni. Lehet, hogy több útvonal van a kiindulási pozíciótól a kijáratig. Az útvesztőből való kijutás természetes megközelítése az összes út kipróbálása.
Tegyük fel, hogy két lehetősége van abban a pillanatban, ahol jelenleg áll. Nyilván nem tudod, melyik vezet ki az útvesztőből. Tehát úgy dönt, hogy az első választást választja, és továbblép az útvesztőben.
Folyamatosan mozogsz, és haladsz előre, és zsákutcába kerülsz. Most ideális esetben egy másik utat szeretne kipróbálni, és így visszalép egy korábbi ellenőrző ponthoz, ahol az egyik lehetőséget választotta, majd ezúttal egy újat, azaz egy másik utat próbál meg.
Addig csinálod ezt, amíg meg nem találod a kijáratot.
Egy adott út rekurzív kipróbálása és visszalépés képezi a két komponenst, amelyek a Mélység Első Keresési algoritmust (DFS) alkotják .
Ha a labirintus problémát grafikonként modellezzük, akkor a csúcsok az egyén helyzetét mutatják az útvesztőben, a két csomópont közötti irányított élek pedig egyetlen lépésről az egyik pozícióra a másikra. A DFS használatával az egyén minden lehetséges útvonalat kipróbál, amíg a kijáratot meg nem találja.
Itt van egy pszeudo-kód mintája.
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)Ha mélyebbre kíván merülni ebben az algoritmusban, nézze meg: -
Mély merülés egy grafikonon: DFS Traversal
Jóban vagy rosszban, mindig többféleképpen lehet tenni valamit. Szerencsénkre, a szoftverek és a… medium.com világában
Időkomplexum: O (V + E)
Szélesség Első keresés
Képzelje el, hogy egy fertőző betegség fokozatosan terjed egy régióban. A betegségben szenvedő emberek minden nap új embereket fertőznek meg, akikkel fizikai kapcsolatban állnak. Ily módon a betegség egyfajta szélesség-első keresést végez (BFS) a lakosság felett. A „sor” az éppen fertőzött emberek összessége. A grafikon a régió fizikai kontakthálózata.
Képzelje el, hogy szimulálnia kell a betegség terjedését ezen a hálózaton keresztül. A keresés gyökérpontja a nulla, a betegség első ismert szenvedője. Csak a betegséggel kezdi őket, és senki mással.
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.
Try and solve this problem on your own before looking at the solution below.
If you try to solve it using DFS, you will surely come up with a solution, but there is a test case(s) that will exceed the allotted time limit on the LeetCode platform. That’s because of the problem described before as to why DFS takes so long (process 7 nodes as opposed to 3 in BFS) to reach the destination vertex.
Hope you got the main idea behind the two main graph traversals, and the difference between them when the application is shortest paths in an undirected unweighted graph.
Please recommend (❤) this post if you think this may be useful for someone!