全部标签

#图论

• 算法

  二分图与匈牙利算法

  二分图又称作二部图，是图论中的一种特殊模型。

• 算法

  图的连通性：DFS 树、割点与桥、双连通分量

  DFS 树即深度优先生成树。从一个点开始对有向图做 DFS 后可以得到一棵 DFS 树，树上的边就称为树边。

• 算法

  最近公共祖先 LCA：倍增、ST 与 Tarjan

  最近公共祖先（Least Common Ancestor）对于有根树 T 的两个结点 u 、 v ，最近公共祖先 LCA(u,v) 表示一个结点 x ，满足 x 是 u 和 v 的祖先且 x 的深度尽可能大。

• 算法

  最小生成树 MST：Kruskal 与 Prim

  一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边，称作最小生成树 (Minimum Spanning Tree, MST) 。

• 算法

  最短路问题：从 Dijkstra 到 Johnson

  最短路问题 (short-path problem) 是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

• 算法

  强连通分量：Kosaraju 与 Tarjan

  在有向图 G 中，如果两个顶点 v_i,v_j 间有一条从 v_i 到 v_j 的有向路径，同时还有一条从 v_j 到 v_i 的有向路径，则称两个顶点强连通 (strongly connected) 。