Блог

Главная - Вопросы по программированию - Алгоритмы на графах после и до подсчета

Алгоритмы на графах после и до подсчета

#python #algorithm #graph #graph-theory #graph-algorithm

#python #алгоритм #График #теория графов #граф-алгоритм

Вопрос:

Я программирую алгоритм глубины сначала.

входные данные — это вершина и список смежности, вот мои данные:

 {'N': ['X'],
 'X': ['N', 'A'],
 'A': ['X', 'B', 'D', 'C'],
 'B': ['A', 'H', 'G'],
 'C': ['D', 'A'],
 'D': ['C', 'A', 'F', 'L'],
 'F': ['D', 'L'],
 'L': ['D', 'F'],
 'H': ['B', 'G'],
 'G': ['H', 'B'],
 'Q': ['W'],
 'W': ['Q']}

вот мой код:

 def explore (node):

    node[visited] = True
    clock  =1
    node[pre_time] = clock
    
    for neighbor of node:
        if not neighbor[visited]:
            explore(neighbor)
    clock =1
    node[post_time] = clock

теперь это работает нормально… за исключением того, что мои pre_time и post_time перепутались
Я хочу, чтобы мое время публикации было рассчитано после того, как я закончу исследовать всех соседей

но мой результат такой

 {'N': {'post': 2, 'pre': 1, 'visited': True}, 'X': {'post': 3, 'pre': 2, 'visited': True}, 'A': {'post': 4, 'pre': 3, 'visited': True}, 'B': {'post': 5, 'pre': 4, 'visited': True}, 'C': {'post': 6, 'pre': 5, 'visited': True}, 'D': {'post': 5, 'pre': 4, 'visited': True}, 'F': {'post': 6, 'pre': 5, 'visited': True}, 'L': {'post': 7, 'pre': 6, 'visited': True}, 'H': {'post': 6, 'pre': 5, 'visited': True}, 'G': {'post': 7, 'pre': 6, 'visited': True}, 'Q': {'post': None, 'pre': None, 'visited': False}, 'W': {'post': None, 'pre': None, 'visited': False}})

Что я делаю не так?

Вот воспроизводимый код в Colab

https://colab.research.google.com/drive/1CTxyDRcCeNuh8b68Jpb8IW-8oy56JSQg?usp=sharing

Комментарии:

1. в чем проблема?

2. Поделитесь большим количеством кода (где вы вызываете explore ())

3. Я поделился ссылкой

4. Похоже, вы ожидаете clock , что это будет глобальная переменная, но она ограничена вызовом функции. Инициализируйте его вне функции, а затем поместите строку global clock внутри функции, и ваша проблема должна исчезнуть.

5. Ты гений @btilly, это сработало как по волшебству. Спасибо