一、图的基础知识

1.连通图与非连通图

　　连通图（Connected Graphs）指图内任意两个节点间，总能找到一条路径连接它们，否则，为非连通图（Disconnected Graphs）。也就是说，如果图中包含岛（Island）,则是非连通图。如果岛内的节点都是连通的，这些岛就被成为一个部件（Component，有时也叫 Cluster）。

　　有些图算法在非连通图上可能产生无法预见的错误。如果我们发现了未预见的结果，可以首先检查图的结构是否连通。

二、图算法

• 路径搜索算法
  • DFS & BFS
  • 最短路径
  • 最小生成树
  • 随机游走
• 中心性算法
  • Degree Centrality
  • Closeness Centrality
  • Betweenness Centrality
  • PageRank
• 社群发现算法
  • Measuring Algorithm
  • Components Algorithm
  • Label Propagation Algorithm
  • Louvain Modularity Algorithm

1.路径搜索算法

（1）BFS和DFS

（2）path

（3）随机游走

参考文献：

【1】图算法：数据科学一线DSFrontier

【2】https://www.oreilly.com/library/view/graph-algorithms/9781492047674/