C#和.Net框架

最小生成树

参考:最小生成树的两种方法（Kruskal算法和Prim算法）

Kruskal算法 — 加边法

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

• 此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

Kruskal算法怎么判断两个节点在不在同一个树里面

• 并查集

Prim算法

• 此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。类似dijkstra.

最短路径

DFS/BFS

djikstra

算法概述

• Dijikstra设置一个集合S记录已求得的最短路径的定点，初始时把源点$v_{0}$放入S.每次求出从集合S出发到S-V中定点的最短距离，选取距离最近的一个并入S，然后修改源点$v_{0}$到集合V-S中定点当前的最短路径长度值。

  算法步骤

• 使用邻接表或者邻接矩阵
  

伪代码

![]Dijkstra.svg)

代码

Bellman_ford

spfa

floyed

A*

JPS

拓扑排序

关键路径