图论 Graph

[shhider]

概念

• 度 (degree): 连接一个节点的个数之和；
  • 入度 indegree：有向图中，所有接入该点的边数之和；
  • 出度 outdegreee：有向图中，所有接出该点的边数之和；
• 有权图、无权图

图的构建

// todo

图的遍历

• 广度遍历
• 深度遍历

拓扑排序 Topo Sort

Topological sorting - Wikipedia

• 有向图的拓扑排序是对其顶点的一种线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv，u 在排序中都在 v 之前。
• 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。
• 算法
  • 卡恩算法 Kahn's algorithm
  • 深度优先搜索 Depth-first search
  • 平行算法

有向无环图 DAG

如何确定有向图内无环

相关算法

• 最短路径：Dijkstra 算法，Floyd 算法
• 最小生成树：Prim 算法、Kruskal 算法

// more...