Tiefes Eintauchen in Graph Traversals

Ab dem dritten Quartal 2017 gibt es weltweit über 2,07 Milliarden aktive Facebook-Nutzer pro Monat. Der wichtigste Aspekt des Facebook-Netzwerks ist das soziale Engagement der Nutzer. Je mehr Freunde ein Benutzer hat, desto ansprechender werden die Konversationen durch Kommentare zu Posts, Nachrichten usw. Wenn Sie Facebook ziemlich regelmäßig verwendet haben, müssen Sie über die Funktion zur Empfehlung von Freunden Bescheid wissen.

Facebook empfiehlt eine Reihe von Personen, die wir als Freunde hinzufügen können. Meistens sind dies Leute, von denen wir noch nie gehört haben. Facebook ist jedoch der Meinung, dass wir sie hinzufügen sollten. Die Frage ist: Wie kommt Facebook auf eine Reihe von Empfehlungen für eine bestimmte Person ?

Ein Weg, dies zu tun, basiert auf gemeinsamen Freunden. Beispiel: - Wenn sich Benutzer A und C nicht kennen, aber einen gemeinsamen Freund B haben, sollten wahrscheinlich auch A und C Freunde sein. Was ist, wenn A und C 2 gemeinsame Freunde haben und A und D 3 gemeinsame Freunde haben? Wie wird die Bestellung für Vorschläge sein?

In diesem Fall scheint es ziemlich offensichtlich, D über C bis A vorzuschlagen, da sie mehr gemeinsame Freunde haben und mit größerer Wahrscheinlichkeit eine Verbindung herstellen.

Zwei Personen haben jedoch möglicherweise nicht immer gemeinsame Freunde, aber sie haben möglicherweise gemeinsame Verbindungen 2. oder 3. Grades.

Verbindungen n-ten Grades

  • A und B sind Freunde. (0 Grad)
  • A und B sind Freunde 1. Grades, dh sie haben einen gemeinsamen Freund.
  • A und B sind Freunde 2. Grades, wenn sie einen Freund haben, der mit der anderen Person ein Freund 1. Grades ist. zB: - A - C - D - B, dann sind A und B Freunde 2. Grades.
  • In ähnlicher Weise sind A und B Freunde N- ten Grades, wenn sie N Verbindungen dazwischen haben. zB: - A - X1 - X2 - X3… .. - XN - B.

Wenn wir diesen Ansatz für die Empfehlung betrachten, müssen wir in der Lage sein, den Grad der Freundschaft zu finden, den zwei bestimmte Benutzer auf Facebook teilen.

Geben Sie Graph Traversals ein

Nachdem wir nun wissen, wie Freundempfehlungen abgegeben werden können, wiederholen wir dieses Problem, damit wir es aus einer algorithmischen Perspektive betrachten können.

Stellen wir uns ein ungerichtetes Diagramm aller Benutzer auf Facebook vor , wobei Eckpunkte V die Benutzer und Kanten E Freundschaften darstellen. Mit anderen Worten: Wenn Benutzer A und B Freunde auf Facebook sind, gibt es einen Rand zwischen den Eckpunkten A und B. Die Herausforderung besteht darin, den Grad der Verbindung zwischen zwei beliebigen Benutzern herauszufinden.

Formal müssen wir den kürzesten Abstand zwischen zwei Knoten in einem ungerichteten, ungewichteten Diagramm sehen.

Betrachten Sie zwei Eckpunkte in diesem ungerichteten Diagramm A und C. Es gibt zwei verschiedene Wege, um C zu erreichen:

1. A → B → C und

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

Natürlich möchten wir den kleinsten Weg einschlagen, wenn wir versuchen, den Grad der Verbindung zwischen zwei Personen im sozialen Netzwerk zu ermitteln.

So weit, ist es gut.

Bevor wir fortfahren, schauen wir uns die Komplexität dieses Problems an. Wie bereits erwähnt, hat Facebook ab dem dritten Quartal 2017 rund 2,07 Milliarden Nutzer. Das bedeutet, dass unser Diagramm rund 2,07 Milliarden Knoten und mindestens (2,07 Milliarden - 1) Kanten haben wird (wenn jede Person mindestens einen Freund hat) .

Dies ist eine riesige Skala, um dieses Problem zu lösen. Darüber hinaus haben wir festgestellt, dass möglicherweise mehrere Pfade von einem bestimmten Quellscheitelpunkt zu einem Zielscheitelpunkt im Diagramm zu erreichen sind, und wir möchten, dass der kürzeste unser Problem löst.

Wir werden uns zwei klassische Graph-Traversal-Algorithmen ansehen, um unser Problem zu lösen:

1. Tiefe erste Suche und

2. Breite erste Suche.

Tiefe Erste Suche

Stellen Sie sich vor, Sie stecken in einem solchen Labyrinth fest.

Du musst irgendwie raus. Es kann mehrere Routen von Ihrer Startposition bis zum Ausgang geben. Der natürliche Ansatz, um aus dem Labyrinth herauszukommen, besteht darin, alle Wege auszuprobieren.

Angenommen, Sie haben an dem Punkt, an dem Sie gerade stehen, zwei Möglichkeiten. Offensichtlich wissen Sie nicht, welcher aus dem Labyrinth führt. Sie entscheiden sich also, die erste Wahl zu treffen und im Labyrinth weiterzumachen.

Sie machen immer wieder Bewegungen und Sie bewegen sich weiter vorwärts und Sie stoßen auf eine Sackgasse. Jetzt möchten Sie idealerweise einen anderen Pfad ausprobieren und kehren zu einem vorherigen Kontrollpunkt zurück, an dem Sie eine der Auswahlmöglichkeiten getroffen haben, und versuchen dann einen neuen, dh diesmal einen anderen Pfad.

Sie tun dies so lange, bis Sie den Ausgang finden.

Das rekursive Ausprobieren eines bestimmten Pfads und das Zurückverfolgen sind die beiden Komponenten, die den Depth First Search-Algorithmus (DFS) bilden.

Wenn wir das Labyrinthproblem als Diagramm modellieren, würden die Eckpunkte die Position des Individuums auf dem Labyrinth darstellen und gerichtete Kanten zwischen zwei Knoten würden eine einzelne Bewegung von einer Position zu einer anderen Position darstellen. Mit DFS würde die Person alle möglichen Routen ausprobieren, bis der Ausgang gefunden wird.

Hier ist ein Beispiel-Pseudocode dafür.

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)

Weitere Informationen zu diesem Algorithmus finden Sie unter: -

Deep Dive durch eine Grafik: DFS Traversal

Zum Guten oder zum Schlechten gibt es immer mehr als einen Weg, etwas zu tun. Zum Glück für uns in der Welt der Software und… medium.com

Zeitkomplexität: O (V + E)

Breite erste Suche

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.

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!