Алгоритмы на графах

Введение в анализ сетей на Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Поиск путей

Поиск путей важен для
- Оптимизации: например, кратчайшие маршруты
- Моделирования: например, распространение болезней, передача информации
Алгоритм: поиск в ширину

Граф с дюжиной узлов. Два узла, соединённых косвенно, выделены.

Тот же граф, но соседний узел одного из выделенных узлов также выделен.

Тот же граф, но соседние узлы всех выделенных узлов также выделены.

Тот же граф, но ещё один набор соседних узлов также выделен — целевой узел достигнут.

<networkx.classes.graph.Graph at 0x10cc08828>

len(G.edges())

len(G.nodes())

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]

Введение в анализ сетей на Python