Дубоко зароните у обилазак графова

Месечно је преко 2,07 милијарди активних корисника Фацебоока широм света од трећег квартала 2017. године. Најважнији аспект Фацебоок мреже је друштвени ангажман између корисника. Што више корисника има пријатеља, разговори постају занимљивији путем коментара на постове, размене порука итд. Ако сте Фацебоок користили прилично редовно, морате знати о функцији Препоруке пријатеља.

Фацебоок препоручује скуп људи које можемо додати као пријатеље. У већини случајева то су људи за које никада раније нисмо чули. Али ипак, Фацебоок мисли да бисмо их требали додати. Питање је: како Фацебоок доноси сет препорука за одређену особу ?

Један од начина за то је заснован на заједничким пријатељима. нпр: - Ако се корисник А и Ц не познају, али имају заједничког пријатеља Б, онда би вероватно и А и Ц требали бити пријатељи. Шта ако А и Ц имају 2 заједничка пријатеља, а А и Д 3 заједничка пријатеља? Како ће бити наручивање за предлоге?

У овом случају изгледа прилично очигледно да се предложи Д преко Ц до А, јер имају више заједничких пријатеља и већа је вероватноћа да ће се повезати.

Међутим, двоје људи можда неће увек имати заједничке пријатеље, али могу имати заједничке везе 2. или 3. степена.

Нтх Дегрее Цоннецтионс

  • А и Б су пријатељи. (0 степен)
  • А и Б су пријатељи првог степена, што значи да имају заједничког пријатеља.
  • А и Б су пријатељи другог степена ако имају пријатеља, који је пријатељ првог степена са другом особом. нпр: - А - Ц - Д - Б, тада су А и Б пријатељи 2. степена.
  • Слично томе, А и Б су пријатељи Н степена ако између њих имају Н веза. нпр: - А - Кс1 - Кс2 - Кс3… .. - КСН - Б.

Гледајући овај приступ за препоруку, морамо бити у могућности да пронађемо степен пријатељства који двоје корисника деле на Фацебоок-у.

Унесите графичке прелазе

Сад кад знамо како се могу дати препоруке пријатеља, поновимо овај проблем како бисмо га могли сагледати из алгоритамске перспективе.

Замислимо неусмерени графикон свих корисника на Фацебоок-у , где врхови В представљају кориснике, а ивице Е представљају пријатељства. Другим речима: ако су корисници А и Б пријатељи на Фацебоок-у, постоји ивица између врхова А и Б. Изазов је открити степен повезаности било која два корисника.

Формалније, морамо да видимо најкраћу удаљеност између два чвора у неусмереном, непондерисаном графикону.

Размотримо два темена у овом усмереном графу А и Ц. Постоје два различита путања за постизање Ц:

1. А → Б → Ц и

2. А → Г → Ф → Е → Д → Ц.

Јасно је да желимо да кренемо најмањим путем када покушавамо да видимо степен повезаности двоје људи на друштвеној мрежи.

Засада је добро.

Пре него што наставимо, погледајмо сложеност овог проблема. Као што је раније речено, Фацебоок има око 2,07 милијарди корисника од трећег квартала 2017. То значи да ће наш графикон имати око 2,07 милијарди чворова и најмање (2,07 милијарди - 1) ивица (ако свака особа има бар једног пријатеља) .

Ово је огромна скала за решавање овог проблема. Поред тога, такође смо видели да може постојати више путања које треба доћи од датог изворног врха до одредишног темена на графикону и желимо да најкраћи реши наш проблем.

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

1. Дубина Прво претраживање и

2. Ширина прва претрага.

Дубина прва претрага

Замислите да се заглавите у оваквом лавиринту.

Морате некако изаћи. Од ваше почетне позиције до излаза може бити више рута. Природан приступ изласку из лавиринта је испробавање свих стаза.

Рецимо да имате два избора на месту где тренутно стојите. Очигледно је да не знате који води из лавиринта. Дакле, одлучили сте да направите први избор и кренете даље у лавиринту.

Настављате да се крећете и настављате да идете напред и забијате се у слепу улицу. Сада сте идеално би хтео да покушам другачији пут, и тако да одустане на претходну контролни пункт где сте дали једну од избора, а онда испроба нову један односно други пут овај пут.

Наставите тако док не нађете излаз.

Рекурзивно испробавање одређене путање и враћање уназад су две компоненте које чине алгоритам дубинске претраге (ДФС).

Ако проблем лавиринта моделирамо као граф, врхови би представљали положај појединца у лавиринту, а усмерене ивице између два чвора представљале би један помак из једног у други положај. Користећи ДФС, појединац би покушавао све могуће руте док се не пронађе излаз.

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

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)

Да бисте дубље заробили у овај алгоритам, погледајте: -

Дубинско роњење кроз графикон: ДФС прелазак

У добру и злу, увек постоји више начина да се нешто учини. Срећом по нас, у свету софтвера и ... медиум.цом

Сложеност времена: О (В + Е)

Претрага у ширину

Замислите да се заразна болест постепено шири регионом. Сваког дана људи који имају болест заразе нове људе са којима долазе у физички контакт. На овај начин болест врши неку врсту ширег претраживања (БФС) над популацијом. „Ред“ је скуп људи који су управо заражени. Графикон је физичка контактна мрежа региона.

Замислите да треба да симулирате ширење болести кроз ову мрежу. Корен чвора претраге је нулти пацијент, први познати оболели од болести. Започете само са њима са болешћу, и нико други.

Сада понављате људе са којима су у контакту. Неки ће се ухватити болести. Сада поновите све. Дајте и људима који су у контакту са болешћу, осим ако је већ нису имали. Наставите док не заразите све или заразите своју мету. Онда сте готови. Тако функционише претрага у ширину.

БФС алгоритам претраживања истражује врхове слој по слој почевши од првог врха и прелазећи на следећи слој тек када су обрађени сви врхови на тренутном слоју.

Ево примера псеудо-кода за БФС.

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)

За дубље разумевање БФС-а, погледајте овај чланак.

Сложеност времена: О (В + Е)

Најкраће стазе

Кренимо напред и решимо свој изворни проблем: проналажење најкраћег пута између два задата темена у неусмереном графу.

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.

Покушајте сами да решите овај проблем пре него што погледате решење у наставку.

Ако покушате да га решите помоћу ДФС-а, сигурно ћете доћи до решења, али постоје тест случајеви који ће премашити одређено време на платформи ЛеетЦоде. То је због претходно описаног проблема зашто ДФС-у треба толико времена (процес 7 чворова за разлику од 3 у БФС-у) да би стигао до одредишног темена.

Надам се да сте главну идеју ставили иза два главна прелаза графова и разлику између њих када је апликација најкраћи пут у неусмереном непондерисаном графу.

Молимо препоручите (❤) овај пост ако мислите да би ово некоме могло бити корисно!