Считать и сбрасывать глубину цепочки в DFS Python

Рейтинг: 0Ответов: 1Опубликовано: 27.04.2023

Есть граф следующего формата:

graph = {
    '1': ['2', '34', '4'],
    '2': ['4', '9', '3', '65', 14],
    '3': ['18', '7', '1'],
    '4': ['3', '11'],
    '5': ['11', '3', '4'],
    ...
}

Вводная: Все числа это id пользователей. Сам граф показыват связь учитель-ученик. То есть, например, у юзера 4 есть ученики 3 и 11. В графе также могут присутствовать "двойные" связи, когда оба юзера приходятся друг другу и учителем и учеником.

Задача: Нужно пройтись по графу и за каждого ученика, внученика, правнученика (и так до последнего "пра") посчитать для учителя определенные очки. Для каждое вну/пра даются свои очки.

Что я делаю: Я прохожусь по графу DFSом, считаю глубину цепочки и в зависимости от текущей грубины назначаю очки за ученика/внученика/правнученика и т.д. Однако, подсчет глубины цепочки нужно сбрасывать, каждый раз, когда я возвращаюсь обратно к корню графа, чтобы правильно назначать очки за учеников. И вот на этом моменте я сдулся, не помнию, как сбросить счетчик глубины, и точно ли я вообще иду в том направлении. Подскажите/направьте пожалуйста.

Код:

def dfs(visited, graph, node, chain):
    points = 0
    if node not in visited:
        visited.add(node)
        for neighbour in graph[node]:
            if chain == 0:
                points += 2
                chain += 1
            elif chain == 1:
                points += 1
                chain += 1
            elif chain > 1:
                points += 0.1 / chain
                chain += 1
            points += dfs(visited, graph, neighbour, chain)
    return points 


def run():
    users = list(users_collection.find({}))
    graph = get_graph(users)
    for user in users:
        visited = set()
        total_points = dfs(visited, graph, str(user['_id']), 0)
        print(user['name'], total_points, user['_id'])


if __name__ == "__main__":
    run()

Ответы

▲ 0Принят

Уберите все chain += 1, а вот в рекурсивном вызове

points += dfs(visited, graph, neighbour, chain+1)