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.

Aufgabe

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

import numpy as np

def dfs(graph, start):

# Initialize a set to keep track of visited vertices.

visited = set()

# Initialize a stack to store vertices to be visited.

stack = np.array([start])

# While there are vertices in the stack:

while stack.size > 0:

# Pop the last vertex from the stack.

vertex = stack[-1]

stack = stack[:-1]

# If the vertex has not been visited:

if vertex not in visited:

# Print the vertex.

print(vertex)

# Mark the vertex as visited.

visited.add(vertex)

# Add all unvisited neighbors of the vertex to the stack in reverse order.

stack = np.concatenate((stack, np.array(graph[vertex])[::-1]))

def bfs(graph, start):

# Initialize a set to keep track of visited vertices.

visited = set()

# Initialize a queue to store vertices to be visited.

queue = np.array([start])

# While there are vertices in the queue:

while queue.size > 0:

# Dequeue the first vertex from the queue.

vertex = queue[0]

queue = queue[1:]

# If the vertex has not been visited:

if vertex not in visited:

# Print the vertex.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 3

import numpy as np

def dfs(graph, start):

# Initialize a set to keep track of visited vertices.

visited = set()

# Initialize a stack to store vertices to be visited.

stack = np.array([start])

# While there are vertices in the stack:

while stack.size > 0:

# Pop the last vertex from the stack.

vertex = stack[___]

stack = stack[:___]

# If the vertex has not been visited:

if vertex not in visited:

# Print the vertex.

print(vertex)

# Mark the vertex as visited.

visited.add(vertex)

# Add all unvisited neighbors of the vertex to the stack in reverse order.

stack = np.concatenate((stack, np.array(graph[vertex])[::-1]))

def bfs(graph, start):

# Initialize a set to keep track of visited vertices.

visited = set()

# Initialize a queue to store vertices to be visited.

queue = np.array([start])

# While there are vertices in the queue:

while queue.size > 0:

# Dequeue the first vertex from the queue.

vertex = queue[___]

queue = queue[___:]

# If the vertex has not been visited:

if vertex not in visited:

# Print the vertex.

print(vertex)

# Mark the vertex as visited.

visited.add(vertex)

# Add all unvisited neighbors of the vertex to the queue.

queue = np.concatenate((queue, np.array(graph[vertex])))

# Example usage:

graph = {

'A': ['B', 'C', 'D'],

'B': ['D', 'E'],

'C': ['F', 'G'],

'D': ['H'],

'E': ['F'],

'F': ['G'],

'G': ['H'],

'H': []

}

print("Depth-First Search:")

dfs(graph, 'A')

print("\nBreadth-First Search:")

bfs(graph, 'A')

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen