Мы пытаемся смоделировать распространение вируса
Мы предполагаем, что человечество состоит из N человек У каждого человека i есть m_i друзей, и каждый человек встречает всех своих друзей каждый день Как только зараженный человек встречается с другим человеком, они передают ему вирус
Мы пытаемся выяснить, какие люди будут передавать вирус быстрее всего, чтобы их сдержать
Люди представлены числами.
Пример 1: популяция N = 3. P_1 дружит с P_2 и P_3. Если P_1 - первый инфицированный человек, то через 1 день будут инфицированы P_2 и P_3. Если P_2 является первым зараженным, значит, на следующий день будет заражен P_1. во второй день заразится и P_3. Так что на заражение всего населения уходит 2 дня. Таким образом, алгоритм должен вернуть P_1.
Exemple 2
Person0 | <-> | Person1 | <-> | Person2 | <-> | Person3 | <-> | Person4
Для этого примера он должен вернуть Person2, потому что это займет всего 2 дня. Первый день P_3 и P_1 будут инфицированы, а второй день - P_4 и P_0. Граф не обязательно линейный, он может принимать любую форму. Отношения дружбы всегда двусторонние.