Дълбоко гмуркане в графични траверси

Има над 2,07 милиарда активни потребители на Facebook по целия свят към третото тримесечие на 2017 г. Най-важният аспект на Facebook мрежата е социалната ангажираност между потребителите. Колкото повече приятели има един потребител, толкова по-ангажиращи разговорите стават чрез коментари за публикации, съобщения и т.н. Ако сте използвали Facebook доста редовно, трябва да знаете за функцията за препоръка на приятели.

Facebook препоръчва набор от хора, които можем да добавим като приятели. В повечето случаи това са хора, за които никога не сме чували. Но все пак Facebook смята, че трябва да ги добавим. Въпросът е: как Facebook измисля набор от препоръки за конкретен човек?

Един от начините за това се основава на взаимни приятели. напр .: - Ако потребител A и C не се познават, но имат общ приятел B, тогава вероятно A и C трябва да са и приятели. Ами ако A и C имат 2 взаимни приятели, а A и D имат 3 взаимни приятели? Как ще бъде поръчката за предложения?

В този случай изглежда доста очевидно да се предложи D над C на A, тъй като те имат повече общи приятели и е по-вероятно да се свържат.

Двама души обаче невинаги имат общи приятели, но може да имат общи връзки от 2-ра или 3-та степен.

Връзки от N-та степен

  • А и Б са приятели. (0 степен)
  • А и Б са приятели от 1-ва степен означава, че имат общ приятел.
  • A и B са приятели от 2-ра степен, ако имат приятел, който е приятел от 1-ва степен с другия човек. напр .: - A - C - D - B, тогава A и B са приятели от 2-ра степен.
  • По същия начин, A и B са приятели от 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

Ясно е, че искаме да извървим най-малкия път, когато се опитваме да видим степента на връзка между двама души в социалната мрежа.

Дотук добре.

Преди да продължим, нека разгледаме сложността на този проблем. Както беше посочено преди, Facebook има около 2,07 милиарда потребители към третото тримесечие на 2017 г. Това означава, че нашата графика ще има около 2,07 милиарда възли и най-малко (2,07 милиарда - 1) ръбове (ако всеки човек има поне един приятел).

Това е огромен мащаб за решаване на този проблем. Освен това видяхме също, че може да има множество пътища, които да достигнат от даден източник на върха до върха на местоназначение в графиката и искаме най-краткият да реши проблема ни.

Ще разгледаме два класически алгоритъма за преминаване на графиката, за да решим проблема си:

1. Дълбоко първо търсене и
2. Първо търсене на ширина.

Дълбоко първо търсене

Представете си, че се забивате в такъв лабиринт.

Трябва да излезеш някак. Възможно е да има няколко маршрута от началната ви позиция до изхода. Естественият подход за излизане от лабиринта е да опитате всички пътеки.

Да речем, че имате два варианта в момента, в който се намирате в момента. Очевидно не знаеш кой води от лабиринта. Затова решавате да направите първия избор и да продължите напред в лабиринта.

Продължавате да правите ходове и продължавате да се движите напред и да се ударите в задънена улица. Сега в идеалния случай бихте искали да опитате различен път и така да се върнете към предишна контролна точка, където сте направили един от изборите и след това този път опитате нов, т.е. различен път.

Продължавате да правите това, докато не намерите изхода.

Рекурсивно изпробване на конкретен път и обратното проследяване са двата компонента, формиращи алгоритъма за първо търсене на дълбочина (DFS).

Ако моделираме проблема с лабиринта като графика, върховете ще представляват позицията на индивида в лабиринта, а насочените ръбове между два възла биха представлявали едно движение от една позиция в друга позиция. Използвайки DFS, индивидът ще изпробва всички възможни маршрути, докато не бъде намерен изходът.

Ето примерен псевдо-код за същото.

1 процедура DFS (G, v):
2 етикета v, както са открити
3 за всички ръбове от v до w в G.adjacentEdges (v)
4, ако връх w не е етикетиран както е открит тогава
5 рекурсивно извикайте DFS (G, w)

За по-дълбоко гмуркане в този алгоритъм, проверете: -

Време сложност: O (V + E)

Първо търсене на ширина

Представете си заразна болест, която постепенно се разпространява в регион. Всеки ден хората, които имат заболяването, заразяват нови хора, с които влизат във физически контакт. По този начин болестта прави своеобразна широта на първо търсене (BFS) над населението. „Опашката“ е набор от хора, които току-що са били заразени. Графиката е физическата контактна мрежа на региона.

Представете си, че трябва да симулирате разпространението на болестта през тази мрежа. Коренният възел на търсенето е пациент нула, първият известен страдащ от болестта. Започвате само с тях с болестта и никой друг.

Сега повтаряте хората, с които контактуват. Някои ще хванат болестта. Сега повторете всички тях. Дайте и на хората, които контактуват с болестта, освен ако вече не са я имали. Продължавайте, докато не заразите всички или не заразите своята цел. Тогава сте готови. Ето как работи първо търсене.

Алгоритъмът за търсене на BFS изследва вершините слой по слой, започвайки от първата първа точка и преминавайки към следващия слой, след като всички вершини на текущия слой са обработени.

Ето примерен псевдо-код за BFS.

1 процедура BFS (G, v):
2 q = опашка ()
3 q.enqueue (v)
4 докато q не е празно:
5 v = q.dequeue ()
6, ако v не е посетен:
7 mark v като посетен (// Обработете възела)
8 за всички ръбове от v до w в G.adjacentEdges (v)
9 q.enqueue (w)

За по-задълбочено разбиране на BFS, погледнете в тази статия.

Време сложност: O (V + E)

Най-къси пътища

Нека да продължим напред и да разрешим първоначалния си проблем: да намерим най-краткия път между две дадени върхове в неориентирана графика.

Разглеждайки времевите сложности на двата алгоритъма, всъщност не можем да разберем разликата между двата за този проблем. И двата алгоритъма ще намерят път (или по-скоро най-краткият път) до нашата дестинация от дадения източник.

Нека разгледаме следния пример.

Да предположим, че искаме да намерим най-краткия път от възел 8 до 10. Нека разгледаме възлите, които DFS и BFS изследват, преди да стигнат до местоназначението.

DFS

  • Процес 8 → Процес 3 → Процес 1.
  • Обратно към 3.
  • Процес 6 → Процес 4.
  • Обратно към 6.
  • Процес 7.
  • Backtrack до 6 → Backtrack до 3 → Backtrack до 8.
  • Процес 10.

Общо 7 възли се обработват тук преди да се достигне дестинацията. Сега нека да разгледаме как BFS прави нещата.

BFS

  • Процес 8 → Enqueue 3, 10
  • Процес 3 → Enqueue 1,6
  • Процес 10.

Леле, това беше бързо! Само 3 възла трябваше да бъдат обработени и ние бяхме на нашата дестинация.

Обяснението за тази скорост, което можем да видим в BFS, а не в DFS, е, защото DFS предприема конкретен път и продължава до самия край, т.е.

Това е основният спад на алгоритъма DFS. Може да се наложи да разшири 1000 хиляди нива (в огромна мрежа като тази на Facebook, само защото избра лош път за обработка в самото начало), преди да достигне пътя, съдържащ нашата дестинация. BFS не е изправен пред този проблем и следователно е много по-бърз за нашия проблем.

Освен това, дори ако DFS установи дестинацията, не можем да сме сигурни, че пътят, извършен от DFS, е най-краткият. Може да има и други пътеки.

Това означава, че във всеки случай за проблема с най-кратки пътища DFS ще трябва да обхване цялата графика, за да получи най-краткия път.

В случай на BFS обаче, първото появяване на възела на местоназначението гарантира, че той е този на най-краткото разстояние от източника.

заключение

Досега обсъждахме проблема с Facebook препоръка от Facebook и го сведохме до проблема с намирането на степента на връзки между двама потребители в мрежовата графика.

След това обсъдихме два интересни алгоритъма на Graph Traversal, които се използват много често. Накрая разгледахме кой алгоритъм изпълнява най-доброто за решаване на проблема ни.

Първо търсене на широчината е алгоритъмът, който искате да използвате, ако трябва да намерите най-краткото разстояние между два възела в непосочена, непретеглена графика.

Нека разгледаме този забавен проблем, за да изобразим разликата между двата алгоритъма.

Ако приемем, че сте прочели внимателно декларацията за проблема, нека опитаме и моделираме това като проблем с графиката.

Нека всички възможни низове да станат възли в графиката и ние имаме ръб между два върха, ако имат една мутация между тях.

Лесно, нали?

Даваме ни начален низ (прочетете версията на източника), напр .: - „AACCGGTT“ и трябва да достигнем низа на дестинация (прочетете върхова дестинация) „AACCGGTA“ в минимален брой мутации (прочетете минимален брой стъпки), така че всички междинни низове (възлите) трябва да принадлежат към дадената банка с думи.

Опитайте и разрешете този проблем самостоятелно, преди да разгледате решението по-долу.

Ако се опитате да го разрешите с помощта на DFS, със сигурност ще излезете с решение, но има тестов случай (и), който ще надхвърли определеното време в платформата LeetCode. Това е поради описания по-горе проблем защо DFS отнема толкова време (обработва 7 възла за разлика от 3 в BFS), за да достигне върха на местоназначението.

Надявам се, че сте получили основната идея зад двата основни обиколки на графиката и разликата между тях, когато приложението е с най-къси пътища в непряко претеглена графика.

Моля, препоръчайте (❤) тази публикация, ако смятате, че това може да е полезно за някого!