#python #networking #breadth-first-search
#python #создание сетей #поиск по ширине
Вопрос:
В настоящее время я работаю с BFS, чтобы помочь аналитикам и следователям исследовать террористические или преступные сети для университетской статьи (с использованием Python). Основная тема моей программы не ориентирована на кодирование, поэтому для меня это совершенно ново.
я активно ищу кого-то, кто мог бы помочь / направить меня в разработке моего кода для решения такой проблемы. Заранее большое вам спасибо за вашу помощь.
Комментарии:
1. Рекомендуется сначала создать несколько примеров приложений, прежде чем помогать другим.
Ответ №1:
Я бы посоветовал вам прочитать пятую главу «Обход графа» книги Стивена С. Скиенны «Руководство по разработке алгоритмов», в которой подробно объясняется обход графа с примерами и упражнениями.
Более того, если вам нужна некоторая интуиция для описания того, что такое BFS, вот краткое объяснение:
BFS — это порядок обхода графика, при котором мы отдаем приоритет изучению графика с придыханием, а не глубоко. Предположим, у нас было бы такое дерево, как это:
(N)
|
(A) (B)
| |
(C)(D)(E) (F)
если мы установим N в качестве узла, с которого начинается наш поиск в BFS, то порядок обхода будет следующим:
(1)
|
(2) (3)
| |
(4)(5)(6) (7)
Это связано с тем, что алгоритм поддерживает очередь FIFO (First-In-First-Out) узлов, которые должны быть исследованы, и продолжает добавлять соседей фактического исследуемого узла до тех пор, пока не останется узлов для исследования.
Чтобы немного проиллюстрировать ситуацию, давайте опишем BFS на этом простом примере. У нас будет очередь Q и список исследованных узлов explored на каждом шаге алгоритма. Сначала очередь Q заполняется начальным узлом , который есть Q = [N] , и в списке которого ничего explored = [] нет . Мы добавляем соседей N в очередь и помечаем N как исследованные , поэтому на втором шаге алгоритма у нас будет Q = [A, B] и explored = [N] . Теперь очередь за первым из элементов Q , который является A , поэтому мы добавляем к Q неисследованных соседей и помечаем его как исследованный , то есть Q = [B, C, D] and explored = [N, A] . В третьем мы добавим неисследованные соседи B к Q и пометим B как исследованные , то есть Q = [C, D, E, F] and explored = [N, A, B] . Это продолжается до Q тех пор, пока не станет пустым