ПочатиПочніть безкоштовно

Реалізація DFS для графів

У цій вправі ви реалізуєте алгоритм пошуку в глибину для обходу графа.

Згадайте кроки:

  1. Почніть з будь-якої вершини
  2. Додайте вершину до списку відвіданих вершин
  3. Для кожної суміжної вершини поточного вузла
    • Якщо її вже відвідано → пропустіть
    • Якщо її не відвідано → виконайте DFS рекурсивно

Щоб допомогти вам протестувати код, наведений нижче граф завантажено у вигляді словника.

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

Ця вправа є частиною курсу

Структури даних і алгоритми в Python

Переглянути курс

Інструкції до вправи

  • Перевірте, чи current_vertex ще не відвідано.
  • Додайте current_vertex до visited_vertices.
  • Викличте dfs() рекурсивно, передавши їй відповідні значення.

Інтерактивна практична вправа

Спробуйте виконати цю вправу, доповнивши цей зразок коду.

def dfs(visited_vertices, graph, current_vertex):
    # Check if current_vertex hasn't been visited yet
    if current_vertex not in ____:
        print(current_vertex)
        # Add current_vertex to visited_vertices
        ____.add(____)
        for adjacent_vertex in graph[current_vertex]:
            # Call recursively with the appropriate values
            ____(____, ____, ____)
            
dfs(set(), graph, '0')
Редагувати та запускати код