各种图算法

文章目录

1. 1. 算法描述

Kruscal算法（克鲁斯卡尔）

1. 1. 定义
2. 2. 算法描述

Floyd算法（弗洛伊德）

1. 1. 定义
2. 2. 算法描述

Dijkstra算法（迪杰斯特拉）

1. 1. 定义
2. 2. 算法描述

以下这几个算法，是当时学习算法的时候总结的。今天整理过去纸质资料的时候发现的。这里面的内容，很多都已经看不懂了。

现在整理了一下，不为别的，只为了告诉自己：你曾经搞过怎么变态的一些算法分析，还有什么比这个更难的么？

特别说明的是，这里面的算法我没有具体用代码实现过，当时是为了分析时间复杂度和空间复杂度而整理的伪代码。特别是Dijkstra算法，可能都不是完整的，遗憾归遗憾，现在实在是没有心思整理完整的算法描述了……

#Prim算法（普利姆）
##定义
从图的顶点集合V中任意选择一个单顶点，作为序列中的初始子树，每次迭代时，选择不在树中的最近的顶点加入到树中。

算法描述

Prim(G)
输入：加权连通图 G=<V,E>
输出：Et, 组成G的MST边的集合
BEGIN
    Vt = {Vo};// 可以用热议低昂点来初始化树的顶点集合
    Et = {∅};
    for i in [1..|V|-1)
        在所有的边(v,u)中，求权重最小的边 e' = (v', u')，使v在Vt中，而u在V-Vt中;
        Vt = Vt ∪ {u'};
        Et = Et ∪ {e'}l
    end for
    return Et;
END

Kruscal算法（克鲁斯卡尔）

定义

算法开始时，按照权重的非递减顺序对图中的边进行排序，然后从一个空子图开始扫描这个有序列表，并试图把列表中的下一条边加到当前的子图中，如果产生回路，则跳过。

算法描述

Kruscal(G)
输入：加权连通图 G=<V, E>
输出：Et，组成G的MST的边的集合
BEGIN
    按照边的权重 w(ei1 ≤ ... ≤ ei|E|)的非递减顺序对E排序；
    Et={∅}; // 初始化边的集合
    ec = 0; // 集合的规模
    k = 0; // 初始化已经处理边的数量
    while ec < |v| - 1
        k++;
        if Et ∪ {ejk} 无回路
            Et = Et ∪ {ejk};
            ec++;
        end if
    end while
    return Et;
END

Floyd算法（弗洛伊德）

定义

• k=0, dij[0] = wij
• k≥1, dij[k] = min{dij[k-1], dik[k-1]+dkj[k-1]}

把当前距离矩阵D[k-1]中的第i行第j列元素替换为第i行第k列元素和第k行第j列元素的和，当且仅当后者的和小于它的当前值

算法描述

    Floyd(w[1..n, 1..n])
    输入：图的权重矩阵w
    输出：包含最短路径长度的距离矩阵D
    BEGIN
        D=w;
        for k in [1..n]
            for i in [1..n]
                for j in [1..n]
                    D[i,j]=min{D[i,j], D[i,k]+D[k,j]}
                end for
            end for
        end for
        return D;
    END
```language

Dijkstra算法（迪杰斯特拉）

定义

顶点标记 v(f, d)：

• d：目前求出从起点到该顶点键间最短路径长度
• f：这条路径上倒数第二个顶点的名字

算法只需找到具有最小的d值得边缘顶点就可以，确定加入u’后：把u’从边缘集合移到树集合，对于余下的每一个边缘u，如果通过w(u’, u)的边与u’相连，当du’ + w(u’, u) < du时，更新u的标记为(u’, du+w(u’, u))。

算法描述

Dijkstra(G, S)
输入：加权连通图G=<V, E>，以及出发点S
输出：对于V中的每个顶点v来说，从S到V的最短路径长度dv，以及路径上倒数第二个顶点Pv
BEGIN
    Initialize(Q);// 将顶点优先队列初始化为空
    for V中的每一个顶点 v
        dv = ∞; pv = null;
        Insert(Q, V, dv);// 初始化优先队列中顶点的优先度
    end for

    ds = 0;
    Decrease(Q, S, ds);// 将s的优先级更新为ds
    Vt = ∅;
    for i in [0..|v|-1)
        u' = DeleteMin(Q);// 删除优先级最小的元素
        Vt = Vt ∪ {u'};
        for V-Vt中每一个与u'相邻的顶点u
            if du' + w(u', u) < du
                du = du' + w(u', u);
                Pu = u';
                Decrease(Q, u, du);// 将u的优先级更新为du
            end if
        end for
    end for
END