图算法

Python 网络分析入门

Eric Ma

Data Carpentry instructor and author of nxviz package

寻找路径

  • 路径搜索的重要性：
    • 优化：如最短运输路径
    • 建模：如疾病传播、信息传递
  • 算法：广度优先搜索（BFS）
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 网络分析入门

Passons à la pratique !

Python 网络分析入门

Preparing Video For Download...