Kursinhalt
Überblick Über Algorithmen und Datenstrukturen
Überblick Über Algorithmen und Datenstrukturen
Herausforderung: Graphendurchlaufalgorithmen
Graphendurchlauf-Algorithmen werden verwendet, um systematisch alle Knoten in einem Graphen zu besuchen. Zwei häufig verwendete Algorithmen für den Graphendurchlauf sind Tiefensuche (DFS) und Breitensuche (BFS).
DFS-Algorithmus
DFS erkundet so weit wie möglich entlang jedes Zweigs, bevor es zurückverfolgt. Es verwendet einen Stapel, um die Knoten zu verfolgen, die als nächstes besucht werden sollen. Dies liegt daran, dass DFS so weit wie möglich entlang jedes Zweigs erkundet, bevor es zurückverfolgt, und der Stapel ermöglicht es, den Pfad vom Startknoten zum aktuellen Knoten zu merken, um sicherzustellen, dass es zum vorherigen Knoten zurückverfolgen und andere Zweige erkunden kann, wenn nötig.
- Beginnen Sie bei einem Scheitelpunkt und markieren Sie ihn als besucht;
- Erkunden Sie alle angrenzenden, unbesuchten Scheitelpunkte rekursiv oder unter Verwendung eines Stapels;
- Wiederholen Sie den Vorgang, bis alle Scheitelpunkte besucht sind.
BFS-Algorithmus
Der Breadth-First Search (BFS) erkundet systematisch einen Graphen, indem er alle Knoten auf der aktuellen Tiefenebene besucht, bevor er zu den Knoten auf der nächsten Tiefenebene übergeht. Er verwendet eine Warteschlange, um die Erkundungsreihenfolge zu verwalten, stellt sicher, dass die Knoten in der Reihenfolge besucht werden, in der sie entdeckt wurden, und ermöglicht es, den Graphen Schicht für Schicht zu erkunden.
- Beginnen Sie bei einem Knoten und markieren Sie ihn als besucht;
- Fügen Sie den Knoten in eine Warteschlange ein;
- Entnehmen Sie einen Knoten aus der Warteschlange und erkunden Sie alle seine angrenzenden, unbesuchten Knoten;
- Fügen Sie diese Knoten in die Warteschlange ein;
- Wiederholen Sie die Schritte 3-4, bis die Warteschlange leer ist.
Swipe to start coding
Ihre Aufgabe ist es, die BFS- und DFS-Algorithmen zu implementieren, indem Sie die Lücken in den Funktionen bfs() und dfs() füllen.
In der Funktion bfs() müssen wir den Breadth-First Search (BFS)-Algorithmus implementieren, der eine Warteschlange verwendet, um den Graphen zu durchlaufen. Das bedeutet, dass wir das erste Element aus dem Array der Knoten entfernen sollten, während wir den Graphen erkunden.
Umgekehrt müssen wir in der Funktion dfs() den Depth-First Search (DFS)-Algorithmus implementieren, der einen Stapel verwendet, um den Graphen zu durchlaufen. Daher sollten wir das letzte Element aus dem Array der Knoten entfernen, während wir durch den Graphen navigieren.
Lösung
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwendenDanke für Ihr Feedback!
Herausforderung: Graphendurchlaufalgorithmen
Graphendurchlauf-Algorithmen werden verwendet, um systematisch alle Knoten in einem Graphen zu besuchen. Zwei häufig verwendete Algorithmen für den Graphendurchlauf sind Tiefensuche (DFS) und Breitensuche (BFS).
DFS-Algorithmus
DFS erkundet so weit wie möglich entlang jedes Zweigs, bevor es zurückverfolgt. Es verwendet einen Stapel, um die Knoten zu verfolgen, die als nächstes besucht werden sollen. Dies liegt daran, dass DFS so weit wie möglich entlang jedes Zweigs erkundet, bevor es zurückverfolgt, und der Stapel ermöglicht es, den Pfad vom Startknoten zum aktuellen Knoten zu merken, um sicherzustellen, dass es zum vorherigen Knoten zurückverfolgen und andere Zweige erkunden kann, wenn nötig.
- Beginnen Sie bei einem Scheitelpunkt und markieren Sie ihn als besucht;
- Erkunden Sie alle angrenzenden, unbesuchten Scheitelpunkte rekursiv oder unter Verwendung eines Stapels;
- Wiederholen Sie den Vorgang, bis alle Scheitelpunkte besucht sind.
BFS-Algorithmus
Der Breadth-First Search (BFS) erkundet systematisch einen Graphen, indem er alle Knoten auf der aktuellen Tiefenebene besucht, bevor er zu den Knoten auf der nächsten Tiefenebene übergeht. Er verwendet eine Warteschlange, um die Erkundungsreihenfolge zu verwalten, stellt sicher, dass die Knoten in der Reihenfolge besucht werden, in der sie entdeckt wurden, und ermöglicht es, den Graphen Schicht für Schicht zu erkunden.
- Beginnen Sie bei einem Knoten und markieren Sie ihn als besucht;
- Fügen Sie den Knoten in eine Warteschlange ein;
- Entnehmen Sie einen Knoten aus der Warteschlange und erkunden Sie alle seine angrenzenden, unbesuchten Knoten;
- Fügen Sie diese Knoten in die Warteschlange ein;
- Wiederholen Sie die Schritte 3-4, bis die Warteschlange leer ist.
Swipe to start coding
Ihre Aufgabe ist es, die BFS- und DFS-Algorithmen zu implementieren, indem Sie die Lücken in den Funktionen bfs() und dfs() füllen.
In der Funktion bfs() müssen wir den Breadth-First Search (BFS)-Algorithmus implementieren, der eine Warteschlange verwendet, um den Graphen zu durchlaufen. Das bedeutet, dass wir das erste Element aus dem Array der Knoten entfernen sollten, während wir den Graphen erkunden.
Umgekehrt müssen wir in der Funktion dfs() den Depth-First Search (DFS)-Algorithmus implementieren, der einen Stapel verwendet, um den Graphen zu durchlaufen. Daher sollten wir das letzte Element aus dem Array der Knoten entfernen, während wir durch den Graphen navigieren.
Lösung
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwendenDanke für Ihr Feedback!
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwenden