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

Вступ до аналізу мереж у Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Пошук шляхів

  • Пошук шляхів важливий для
    • Оптимізації: напр., найкоротші транспортні маршрути
    • Моделювання: напр., поширення хвороб, передавання інформації
  • Алгоритм: пошук у ширину
Вступ до аналізу мереж у Python

Пошук у ширину (BFS)

  • Приклад: найкоротший шлях між двома вузлами

Граф із десятком вузлів. Два вузли, що з'єднані опосередковано, підсвічені.

Вступ до аналізу мереж у Python

Пошук у ширину (BFS)

  • Приклад: найкоротший шлях між двома вузлами

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

Вступ до аналізу мереж у Python

Пошук у ширину (BFS)

  • Приклад: найкоротший шлях між двома вузлами

Той самий граф, але також підсвічено сусідні вузли для всіх підсвічених вузлів.

Вступ до аналізу мереж у Python

Пошук у ширину (BFS)

  • Приклад: найкоротший шлях між двома вузлами

Той самий граф, але додатково підсвічено чергові сусідні вузли до вже підсвічених, тож цільовий вузол досягнуто.

Вступ до аналізу мереж у Python

Згадуємо: сусіди

G

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

len(G.edges())

57

len(G.nodes())

20
Вступ до аналізу мереж у Python

Згадуємо: сусіди

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Вступ до аналізу мереж у Python

Давайте потренуємось!

Вступ до аналізу мереж у Python

Preparing Video For Download...