Понятие обхода графа |
133 |
Граф, созданный этим кодом, выглядит следующим образом (рис. 5.10).
Рис. 5.10
На данный момент мы разобрали несколько показателей центральности. Давай те рассчитаем их для примера выше (рис. 5.11).
Обратите внимание, что показатели центральности должны дать оценку цент ральности конкретной вершины в графе или подграфе. Глядя на граф, кажется, что вершина 7 имеет наиболее центральное расположение (рис. 5.10). Вершина 7 имеет самые высокие значения по всем четырем показателям центральности, что отражает ее важность в данном контексте.
Теперь давайте разберемся, как мы можем извлекать из графов информацию. Графы — это сложные структуры данных‚ содержащие большое количество информации, хранящейся как в вершинах, так и в ребрах. Рассмотрим ряд стра тегий, которые можно использовать для эффективного передвижения по графам, чтобы получать из них информацию‚ отвечающую запросам.
ПОНЯТИЕ ОБХОДА ГРАФА
Чтобы использовать графы, необходимо уметь извлекать из них информацию. Обход графа (graph traversal) — стратегия, обеспечивающая упорядоченное по сещение каждой вершины и ребра. Необходимо добиться того, чтобы каждая
134 |
Глава 5. Графовые алгоритмы |
||
|
|
|
|
|
|
|
|
Рис. 5.11
вершина и ребро посещались ровно один раз, не больше и не меньше. В широком смысле имеются два различных способа перемещения по графу с целью поиска
внем данных. Если сначала учитывается ширина‚ то это называется поиском
вширину (breadth-first search, BFS), а если глубина‚ то поиском в глубину (depthfirst search, DFS). Рассмотрим их по очереди.
Понятие обхода графа |
135 |
BFS — поиск в ширину
BFS работает лучше всего, когда в aGraph, с которым мы имеем дело, поддержи вается концепция слоев или уровней окрестностей. Например, когда отношения человека в LinkedIn отражены в виде графа, в нем будут присутствовать связи первого уровня, затем второго уровня и т. д, которые легко преобразуются в слои.
Алгоритм BFS начинает с корневой вершины и исследует вершины в окрест ности. Затем он переходит на следующий уровень окрестности и повторяет процесс.
Давайте взглянем на алгоритм BFS поближе. Для этого сначала обратимся к следующему неориентированному графу (рис. 5.12).
Рис. 5.12
Начнем с вычисления непосредственной окрестности каждой вершины и со храним ее в списке, называемом списком смежных вершин (adjacency list). В Python для его хранения мы можем использовать структуру данных словаря:
graph={ 'Amin' |
: {'Wasim', |
'Nick', 'Mike'}, |
'Wasim' |
: {'Imran', 'Amin'}, |
|
'Imran' |
: {'Wasim','Faras'}, |
|
'Faras' |
: {'Imran'}, |
|
'Mike' |
: {'Amin'}, |
|
'Nick' : |
{'Amin'}} |
|
Подробно рассмотрим реализацию алгоритма BFS на Python.
Сначала мы объясним инициализацию, а затем основной цикл.
136 |
Глава 5. Графовые алгоритмы |
Инициализация
Мы будем использовать две структуры данных:
zz visited. Содержит все вершины, которые были посещены. Изначально она будет пустой;
zz queue. Здесь содержатся все вершины, которые мы хотим посетить на следу ющих итерациях.
Основной цикл
Реализуем основной цикл. Он будет выполняться до тех пор, пока в очереди не останется ни одного элемента. Для каждой вершины в очереди происходит следующее: если она уже была посещена, то посещается ее сосед.
Мы можем реализовать основной цикл в Python следующим образом:
1.Сначала извлечем первую вершину из очереди и выберем ее в качестве те кущей вершины данной итерации.
node = queue.pop(0)
2.Затем проверим, находится ли вершина в списке visited. Если это не так, мы добавляем ее в список посещенных вершин и используем neighbours для отображения непосредственно связанных с ней вершин.
visited.append(node) neighbours = graph[node]
3. Теперь добавим соседние вершины в очередь.
for neighbour in neighbours: queue.append(neighbour)
4.Как только основной цикл завершен, возвращается структура данных visited, которая содержит все пройденные вершины.
5.Полный код с инициализацией и основным циклом будет выглядеть следу ющим образом (рис. 5.13).
Давайте рассмотрим маршрут обхода исчерпывающего поиска для графа, кото рый мы описали с помощью BFS. Схема обхода‚ при которой будут посещены все вершины‚ показана на рис. 5.14. Можно заметить, что во время выполнения она всегда работает с двумя структурами данных:
zz visited. Содержит все вершины, которые были посещены; zzqueue. Содержит вершины, которые еще предстоит посетить.