Блог

Предположим, что население составляет 500 человек, и каждый человек знает ровно 4 других человека в населении. Предположим, один человек заражается болезнью, и эта болезнь гарантированно заразит остальных 4 человек, которых этот человек знает, ровно через 1 день.

Напишите алгоритм, чтобы определить, сколько дней потребуется всем, чтобы заразиться, учитывая входную матрицу смежности.

Я не могу понять, как правильно следить за днями. Я попробовал следующее, но это просто дает мне число, близкое к общему числу узлов (оно должно быть намного меньше).:

 import random
random.seed(20)

nodes = 500
num_connections = 4

# generate random graph
graph = []
for node_num in range(nodes):
  myrow = [0 for node in range(nodes - num_connections)]   [1 for connection in range(num_connections)]
  random.shuffle(myrow)
  graph.append(myrow)


days = 0
visited = [0]
queue = [0]
while queue:
  ss = queue.pop(0)
  for neighbor, is_connected in enumerate(graph[ss]):
    if is_connected == 1 and neighbor not in visited:
      visited.append(neighbor)
      queue.append(neighbor)
      days  = 1

print(days)
 

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

1. найдите самый длинный и короткий путь от первого зараженного человека к любому другому человеку, используя алгоритм Дейкстры.
2. Длина этого пути-это количество дней.

ваша задача эквивалентна нахождению самого длинного кратчайшего маршрута на графике. но если вы хотите исправить свой текущий код, я исправил его для вас 🙂

 import random

random.seed(20)

nodes = 50
num_connections = 4

# generate random graph
graph = []
for node_num in range(nodes):
    myrow = [0 for node in range(nodes - num_connections)]   [1 for connection in range(num_connections)]
    random.shuffle(myrow)
    graph.append(myrow)

days = 0
visited = [0]
queue = [0]
while len(visited) < nodes:
    patients = queue.copy()
    queue.clear()
    days  = 1
    while len(patients) > 0:
        ss = patients.pop(0)
        for neighbor, is_connected in enumerate(graph[ss]):
            if is_connected == 1 and neighbor not in visited:
                visited.append(neighbor)
                queue.append(neighbor)
    if len(queue) == 0:
        print(f'The given directional graph is not connected, after {days} days, {len(visited)} persons has been infected')
        exit()

print(days)