Wyszukiwanie wierzchołka grafu za pomocą BFS
W tym ćwiczeniu zmodyfikujesz algorytm BFS, aby wyszukiwał zadany wierzchołek w grafie.
Aby ułatwić testowanie kodu, poniższy graf został wczytany za pomocą słownika.
graph = {
'4' : ['6','7'],
'6' : ['4', '7', '8'],
'7' : ['4', '6', '9'],
'8' : ['6', '9'],
'9' : ['7', '8']
}
To ćwiczenie jest częścią kursu
Struktury danych i algorytmy w Pythonie
Instrukcje do ćwiczenia
- Sprawdź, czy znaleziono szukaną wartość.
- Zwróć
True, jeśli szukana wartość została znaleziona. - Wewnątrz pętli
forsprawdź, czy sąsiedni wierzchołek był już odwiedzony. - Zwróć
False, jeśli szukana wartość nie została znaleziona.
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
import queue
def bfs(graph, initial_vertex, search_value):
visited_vertices = []
bfs_queue = queue.SimpleQueue()
visited_vertices.append(initial_vertex)
bfs_queue.put(initial_vertex)
while not bfs_queue.empty():
current_vertex = bfs_queue.get()
# Check if you found the search value
if ____:
# Return True if you find the search value
____
for adjacent_vertex in graph[current_vertex]:
# Check if the adjacent vertex has been visited
if adjacent_vertex not in ____:
visited_vertices.append(adjacent_vertex)
bfs_queue.put(adjacent_vertex)
# Return False if you didn't find the search value
____
print(bfs(graph, '4', '8'))