Глибоке занурення в обхід графіків

Станом на 3 квартал 2017 р. У світі щомісяця активних користувачів Facebook понад 2,07 млрд. Найважливішим аспектом мережі Facebook є соціальна взаємодія між користувачами. Чим більше друзів у користувача, тим цікавішими стають розмови через коментарі до публікацій, обмін повідомленнями тощо. Якщо ви користуєтесь Facebook досить регулярно, ви повинні знати про функцію Рекомендації друзів.

Facebook рекомендує людей, яких ми можемо додати в друзі. Найчастіше це люди, про яких ми ніколи раніше не чули. Але все-таки Facebook вважає, що ми повинні їх додати. Питання в тому, як Facebook розробляє набір рекомендацій для конкретної людини ?

Один із способів зробити це заснований на спільних друзях. наприклад: - Якщо користувач A і C не знає один одного, але у них є спільний друг B, то, ймовірно, A і C також повинні бути друзями. Що робити, якщо А і С мають двох спільних друзів, а А і Д - 3 спільних друзі? Яким буде замовлення пропозицій?

У цьому випадку представляється цілком очевидним пропонувати D замість C до A, оскільки вони мають більше спільних друзів і, швидше за все, зв’яжуться.

Однак у двох людей не завжди можуть бути спільні друзі, але вони можуть мати спільні зв’язки 2-го чи 3-го ступенів.

Зв’язки N-го ступеня

  • А і В - друзі. (0 градусів)
  • А і В є друзями 1-го ступеня означає, що у них є спільний друг.
  • А і В є друзями 2-го ступеня, якщо у них є друг, який є другом 1-го ступеня з іншою людиною. наприклад: - A - C - D - B, тоді A і B - друзі 2-го ступеня.
  • Точно так само А і В є друзями N-го ступеня, якщо між ними є N зв’язків. наприклад: - A - X1 - X2 - X3… .. - XN - B.

Дивлячись на цей підхід для рекомендації, ми повинні мати можливість виявити ступінь дружби, яку двом даним користувачам ділиться у Facebook.

Введіть обхід графіків

Тепер, коли ми знаємо, як можна робити рекомендації щодо друзів, давайте повторимо цю проблему, щоб ми могли розглянути її з алгоритмічної точки зору.

Уявімо собі ненаправлений графік усіх користувачів у Facebook , де вершини V представляють користувачів, а ребра E - дружбу. Іншими словами: якщо користувачі A і B є друзями у Facebook, між вершинами A і B. існує перешкода. Завдання полягає у з'ясуванні ступеня зв'язку між будь-якими двома користувачами.

Більш формально, нам потрібно бачити найкоротшу відстань між двома вузлами на неорієнтованому, незваженому графіку.

Розглянемо дві вершини цього неорієнтованого графіка A і C. Існує два різні шляхи досягнення C:

1. A → B → C і

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

Очевидно, що ми хочемо піти найменшим шляхом, намагаючись побачити ступінь зв’язку між двома людьми в соціальній мережі.

Все йде нормально.

Перш ніж продовжувати, давайте розглянемо складність цієї проблеми. Як зазначалося раніше, станом на 3 квартал 2017 року Facebook має близько 2,07 мільярда користувачів. Це означає, що наш графік матиме близько 2,07 мільярда вузлів і щонайменше (2,07 мільярда - 1) ребер (якщо кожна людина має хоча б одного друга) .

Це величезний масштаб для вирішення цієї проблеми. Крім того, ми також побачили, що може бути декілька шляхів, щоб дістатися від даної вихідної вершини до вершини призначення в графіку, і ми хочемо, щоб найкоротший вирішив нашу проблему.

Ми розглянемо два класичні алгоритми обходу графіків, щоб вирішити нашу проблему:

1. Глибина Перший пошук і

2. Ширина першого пошуку.

Глибина Перший пошук

Уявіть, що ви застрягли в такому лабіринті.

Треба якось вибратися. Від вашої вихідної позиції до виходу може бути кілька маршрутів. Природний підхід до виходу з лабіринту - випробувати всі шляхи.

Скажімо, у вас є два варіанти, коли ви зараз стоїте. Очевидно, ви не знаєте, хто виводить з лабіринту. Тож ви вирішили зробити перший вибір і рухатися далі в лабіринті.

Ви продовжуєте робити рухи і рухаєтеся вперед, і ви потрапляєте в глухий кут. Тепер ви в ідеалі хочете спробувати інший шлях, і тому ви повернетесь до попереднього пункту пропуску, де ви зробили один із варіантів, а потім спробуєте новий, тобто інший шлях цього разу.

Ви продовжуєте це робити, поки не знайдете виходу.

Рекурсивне випробування певного шляху та зворотне відстеження - це два компоненти, що формують алгоритм пошуку глибини (DFS).

Якщо ми змоделюємо проблему лабіринту як графік, вершини будуть представляти положення людини в лабіринті, а спрямовані ребра між двома вузлами представлятимуть один перехід з однієї позиції в іншу. Використовуючи DFS, особа буде пробувати всі можливі маршрути, поки не буде знайдений вихід.

Ось зразок псевдокоду для того самого.

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)

Для глибшого занурення в цей алгоритм перевірте: -

Глибоке занурення через графік: DFS Traversal

В кращу чи гіршу сторону завжди є кілька способів щось зробити. На наше щастя, у світі програмного забезпечення та… medium.com

Складність часу: O (V + E)

Ширина - перший пошук

Уявіть, яка заразна хвороба поступово поширюється по регіону. Щодня хворі на хворобу заражають нових людей, з якими вони контактують фізично. Таким чином, хвороба здійснює своєрідний широкий пошук серед населення. "Черга" - це група людей, які щойно заразилися. Графік - це фізична контактна мережа регіону.

Уявіть, що вам потрібно імітувати поширення хвороби за допомогою цієї мережі. Кореневий вузол пошуку - пацієнт нуль, перший відомий страждаючий хворобою. Ви починаєте лише з них із хворобою, і ні з кого іншого.

Тепер ви переглядаєте людей, з якими вони контактують. Хтось підхопить хворобу. Тепер повторіть усі. Дайте людям, з якими вони контактують, із хворобою, якщо у них це вже не було. Продовжуйте рухатись, поки не заразите всіх або не заразите свою ціль. Тоді все готово. Ось як працює широта-перший пошук.

Алгоритм пошуку BFS досліджує вершини шар за шаром, починаючи з самої першої вершини і переходячи до наступного шару лише після обробки всіх вершин поточного шару.

Ось зразок псевдокоду для 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)

Для глибшого розуміння BFS загляньте в цю статтю.

Складність часу: O (V + E)

Найкоротші шляхи

Давайте рухатимемося вперед і вирішимо нашу початкову задачу: знайти найкоротший шлях між двома заданими вершинами в неорієнтованому графіку.

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!