图论应用
最小生成树（MST）问题
克鲁斯卡尔算法（Kruskal Algorithm）
- 初始化：开始时，MST 边集为空。
- 排序：将图中所有边按权重从小到大排序。
- 选择边：按排序后的顺序选择边，如果加入该边不会与已选择的边形成环，则将其加入最小生成树的边集。
- 重复步骤 3，直到 MST 的边集中包含了所有顶点减一条边为止。
普利姆算法（Prim Algorithm）
- 初始化：选择一个起点，并将其加入 MST 的顶点集合中。
- 重复以下步骤直到所有顶点都被加入 MST： 从所有连接 MST 顶点集合和非 MST 顶点集合的边中选择一条权值最小的边。 将这条边以及它的非 MST 端点加入到 MST 中。
最短路径问题
迪杰斯特拉算法（Dijkstra Algorithm）
- 初始化两个集合 A 和 B，A 存放已经求出最短路径的点，B 存放还未计算出最短路径的点。
- 从源点开始，更新与源点邻接的所有点的距离。
- 从 B 集合中选择一个距离源点最短的点加入 A 集合。
- 更新刚加入 A 集合的点的所有邻接点的距离。
- 重复步骤 3 和 4，直到 B 集合为空，此时从源点到其他所有点的最短路径已经计算出来。