这篇文章上次修改于 1071 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

加权图

数据类型

因为继承体系，我们将图分为有权图和无权图，又各自分为有向和无向。

有权图

依旧使用邻接表来实现。

基类头文件

class BaseGraph
{
public:
    BaseGraph(int v) : vertex_num(v){};
    int V() const { return vertex_num; };
    int E() const { return edge_num; };

protected:
    int vertex_num;
    int edge_num = 0;
};

class BaseWeightedGraph : public BaseGraph
{
public:
    BaseWeightedGraph(int v) : BaseGraph(v) {}
    virtual void addEdge(int v, int w, double weight) = 0;
};

有权边

将原来的边变为一个新的类型。

基类头文件

class BaseEdge
{
public:
    BaseEdge() : v(-1), w(-1), weight_(0){};
    BaseEdge(int v, int w, double wei) : v(v), w(w), weight_(wei){};
    double weight() const { return weight_; };
    bool operator>(const BaseEdge &e) const { return e.weight() < this->weight_; }
    bool operator<(const BaseEdge &e) const { return e.weight() > this->weight_; }
    bool operator>=(const BaseEdge &e) const { return !(e > *this); }
    bool operator<=(const BaseEdge &e) const { return !(e < *this); }

protected:
    int v;
    int w;
    double weight_;
};

最小生成树（MST）

接口	操作	返回值
MST(WeightedGraph G)	找到图G的最小生成树	构造函数
edges()	返回最小生成树的所有边	Bag
weight()	返回最小生成树的边的权值和	double

输入：一幅加权无向图

输出：一颗最小生成树

前提：

只考虑连通图（如果一幅图非连通，则只能有最小生成森林）
边的权重不一定是距离
边的权重可能是0或者负数
所有边的权重各不相同（若相同，最小生成树的结果将不唯一，还要外加以证明）

树的特性：

删去任一一边都会使树变为两颗
加一边必出环

预备理论

切分定理

术语：

切分：将图的所有顶点分为两非空不重复集合

横切边：一条连接两个属于不同集合的两个点的边

内容：对一图的任一切分，横切边的最小权重必被最小生成树包含。

证明：反证法（略）

数据类型

这里用到的是有权无向图和有权无向边

有权无向图

头文件

class WeightedGraph : public BaseWeightedGraph
{
public:
    WeightedGraph(int v) : BaseWeightedGraph(v), _adj(new Bag<Edge>[v]){};
    WeightedGraph(const WeightedGraph &G);
    ~WeightedGraph() { delete[] _adj; }

    void addEdge(int v, int w, double weight);
    void addEdge(const Edge &e);
    Bag<Edge> adj(int v) const { return _adj[v]; };
    Bag<Edge> edges() const;

    WeightedGraph &operator=(const WeightedGraph &G);
    friend std::ostream &operator<<(std::ostream &os, const WeightedGraph &G);

private:
    Bag<Edge> *_adj;
};

有权边

将原来的边变为一个新的类型。

基类头文件

class Edge : public BaseEdge
{
public:
    Edge() : BaseEdge(){};
    Edge(int v, int w, double wei) : BaseEdge(v, w, wei){};
    int either() const { return v; }
    int other(int ver) const;

    bool operator==(const Edge &edge) const { return edge.weight() == this->weight(); }

    friend std::ostream &operator<<(std::ostream &os, const Edge &edge);
};

Prim算法

思路：

1.从树的第一个节点开始，将起点和其他点作为两类利用切分定理找到第一处连接

2.再将新连接的点加入原来起点的那一类。对新的两个类的横切边进行切分定理判断

3.以此类推

分析：由此我们可以发现算法的实现体现了对横切边容器的处理上。对此Prim算法就出现了两种版本，Prim延时算法和Prim即时算法。两者都利用优先队列。

Prim延时算法

此时的优先队列维护边和边的权值，以边的权值作为优先标准。

思路：

1.以一个起点开始，在优先队列中加入其相邻的边。

2.生长出其中权值最小的边，在优先队列中继续添加新增点的相邻边。

3.同上，以此类推。

实现：

class LazyPrimMST
{
public:
    LazyPrimMST(WeightedGraph G);
    ~LazyPrimMST() { delete[] marked; }
    Bag<Edge> edges() const { return mst; }
    double weight() const;

private:
    edge_pq pq;
    bool *marked;
    Bag<Edge> mst;

    void visit(WeightedGraph G, int v);
};

LazyPrimMST::LazyPrimMST(WeightedGraph G) : marked(new bool[G.V()])
{
    visit(G, 0);
    while (!pq.empty())
    {
        Edge e = pq.top();
        pq.pop();
        int v = e.either(), w = e.other(v);
        if (marked[v] && marked[w])
            continue;
        mst.add(e);
        if (!marked[v])
            visit(G, v);
        if (!marked[w])
            visit(G, w);
    }
}

void LazyPrimMST::visit(WeightedGraph G, int v)
{
    marked[v] = true;
    for (Edge e : G.adj(v))
        if (!marked[e.other(v)])
            pq.push(e);
}

分析：其中，按照思路进行时，我们会遇到一些问题。例如以下

graph TB
1((1));2((2));3((3));4((4));5((5));6((6));7((7));8((8));

5 --- 4;5 --- 1;5 --- 6;
6 --- 1;6 --- 2;6 --- 8;
8 --- 2;8 --- 3;8 --- 7;
7 --- 4;7 --- 3;
1 --- 3;1 --- 2 --- 3;

问题：对如上图，其中重复边的问题，当2-1-3为当前树的时候，由于加入2节点的时候，优先队列中已经有2-3的边直到依次加入1，3，2-3边依旧存在于优先队列，若此时2-3边出列，然后在树中2，3已经连接了，故会成环出错。

解决：仅需要维护一个布尔值数组marked即可，marked用于标记已经在树内的点，当我们要添加无效边2-3的时候，若23已在树内则不会添加。

分析：也因此特性，在部分边无效的时候，它还存在于队列中，只有在出队的时候才会被删除，故成为Prim延时算法。

Prim即时算法

此时的优先队列维护边和边的权值，以边的权值作为优先标准。

思路：

1.以一个起点开始，将这个点周边的点和它们到起点的边的权值加入队列

2.在增长新的节点后，将新点周边的点和它们到新点的边的权值“设置”入队列

“设置”是指若队列中已存在该点，比较新权值和旧权值，小的留下。若不存在则直接加入

3.以此类推

实现：

#include "MST.hpp"

class PrimMST
{
public:
    PrimMST(WeightedGraph G);
    ~PrimMST() { delete[] marked, distTo; }
    Bag<Edge> edges() const { return mst; }
    double weight() const;

private:
    point_pq pq;
    bool *marked;
    double *distTo;
    Edge *edgeTo;
    Bag<Edge> mst;

    void visit(WeightedGraph G, int v);
};

PrimMST::PrimMST(WeightedGraph G) : marked(new bool[G.V()]), distTo(new double[G.V()])
{
}

void PrimMST::visit(WeightedGraph G, int v)
{
    marked[v] = true;
    for (Edge e : G.adj(v))
    {
        int w = e.other(v);
        if (marked[w])
            continue;
        if (e.weight() < distTo[w])
        {
            edgeTo[w] = e;

            distTo[w] = e.weight();
            ele new_ele(w, distTo[w]);
            pq_update(pq,  new_ele);
        }
    }
}

void pq_update(point_pq &pq, const ele &new_data)
{
    point_pq temp;
    temp.swap(pq);
    while (!temp.empty())
    {
        ele top_edge = temp.top();
        temp.pop();
        if (new_data.first == top_edge.first)
        {
            pq.push(new_data);
            break;
        }
        else
            pq.push(top_edge);
    }
    while (!temp.empty())
    {
        ele top_edge = temp.top();
        temp.pop();
        pq.push(top_edge);
    }
}

分析：树增加节点的方式和延时版相同，从队列中取出最小权值的点，这个时候，我们仅获取了点，不知道是哪条边，故我们应额外维护一个数组edgeTo用来记录各个点的指向。

特点：

1.相比于延时版本，即时版本的特点就在“即时性”，指无效边会被即使删除。

2.需要额外维护数组edgeTo以及数组distTo；edgeTo表示了最小的生成树的边，distTo表示了对应点的边的权值默认全为INF（无穷大）。

3.可以不用marked数组判断是否被记录，因为它和判断distTo是否为INF同理。

4.空间上限变为原来的常数因子。

KrusKal算法

思路：

1.将所有的边加入优先队列

2.移出最小（权值）的边，加入最小生成树

3.加入生成树时判断边的两点是否已被连接（已在树内）

4.直至MST的数量达到V-1

实现：

class KurskaiMST
{
public:
    KurskaiMST(WeightedGraph G);
    Bag<Edge> edges() const { return mst; }
    double weight() const;

private:
    Bag<Edge> mst;
};

KurskaiMST::KurskaiMST(WeightedGraph G)
{
    edge_pq pq;
    for (Edge e : G.edges())
        pq.push(e);

    UF uf(G.V());
    while (!pq.empty() and mst.size() < G.V() - 1)
    {
        Edge e = pq.top();
        pq.pop();
        int v = e.either(), w = e.other(v);
        if (uf.connected(w, v))
            continue;
        uf.connect(w, v);
        mst.add(e);
    }
}

double KurskaiMST::weight() const
{
    double total = 0.0;
    for (Edge e : mst)
    {
        total += e.weight();
    }
    return total;
}

特点：

1.KrusKal算法是由森林最后结合成一棵树

2.会储存所有的边一同进行排序

分析：

需要耗费Edge优先队列，union-find结构

对于使用UF是为了检测w和v是否连通，Kruskal算法在一幅图开始时是分散的，产生多颗树，这对于UF对象来说，很有使用价值。

最短路径（SP）

接口	操作	返回类型
SP	创建一个含有V个点无边的无向图	构造函数
distTo(int v)	从s点到v的距离（权值和）	double
hasPathTo(int v)	查看是否存在s到v的路径	bool
pathTo(int v)	从s点到v的路径	bag

头文件

class SP
{
public:
    SP(WeightedDigraph G, int s);
    double distTo(int v) { return distTo_[v]; }
    bool hasPathTo(int v) { return distTo_[v] < INFINITY; }
    Bag<DirectedEdge> pathTo(int v);

private:
    int *distTo_;
    DirectedEdge *edgeTo_;
};

Bag<DirectedEdge> SP::pathTo(int v)
{
    Bag<DirectedEdge> res_bag;
    if (!hasPathTo(v))
        return res_bag;
    for (DirectedEdge e = edgeTo_[v]; e.from() != -1; e = edgeTo_[e.from()])
        res_bag.add(e);
    return res_bag;
}

前提：

松弛：一种基本操作

void relax(WeightedDigraph G, Edge e)
{
    int w = e.to();
    if (distTo_[w] > distTo_[v] + e.weight())
    {
        distTo_[w] = distTo_[v] + e.weight();
        edgeTo_[w] = e;
    }
}

点的松弛：和我们上面所描述的，是对于改点指出的所有边进行松弛

void relax(WeightedDigraph G, int v)
{
    for (DirectedEdge e : G.adj(v))
    {
        int w = e.to();
        if (distTo_[w] > distTo_[v] + e.weight())
        {
            distTo_[w] = distTo_[v] + e.weight();
            edgeTo_[w] = e;
        }
    }
}

理论补充：

最优性条件，对于松弛上例若为最小路径数时，则满足

distTo[w] <= distTo[v] + e.weight()

通用路径最短算法：

起点为s将distTo[s]初始化为0，其他为inf，edgeTo[s]为空，edgeTo[v]为指向v的最小路径树上的边。

Dijkstra算法

思路：类似于Prim，需要维护一个优先队列(同Prim即时算法)

不同点：

1.distTo数组存放值为点到起点的权值和，而并不是新点到邻树点的权值

原因：Prim只存放边的权值，因为无向图的切分定理。而在有向图中，切分定理虽然有效，但是我们难以得到所有的横切边，由于边的有向，我们仅能获取每个点的指出边。Dijkstra算法利用“放松”点的方法，以确保最短的路径。

对于下例：

当树为012，仅能获得1->3, 2->5，故无法使用切分定理

graph TB
0((0));1((1));2((2));3((3));4((4));5((5));

1-->0;1-->3-->4-->0;2-->0;2-->5-->4;

2.marked数组不被使用，因为relax操作的特点。例如上图，已经有1->3->4时，2->5->4仍需要被考虑，需要得到多种指向一点的多条路径，就要多次访问4顶点，这都是因为4不知道指向它的点。

实现：

class DijkstraSP
{
public:
    DijkstraSP(WeightedDigraph G, int s);
    ~DijkstraSP() { delete[] distTo_, edgeTo_; }

    double distTo(int v) const { return distTo_[v]; }
    bool hasPathTo(int v) const { return distTo_[v] < INFINITY; }
    Bag<DirectedEdge> pathTo(int v);

private:
    void relax(WeightedDigraph G, int v);
    double *distTo_;
    DirectedEdge *edgeTo_;
    edge_pq pq;
};

void DijkstraSP::relax(WeightedDigraph G, int v)
{
    for (DirectedEdge e : G.adj(v))
    {
        int w = e.to();
        if (distTo_[w] > distTo_[v] + e.weight())
        {
            distTo_[w] = distTo_[v] + e.weight();
            edgeTo_[w] = e;
            pq_update(pq, ele(w, distTo_[w]));
        }
    }
}

DijkstraSP::DijkstraSP(WeightedDigraph G, int s) : distTo_(new double[G.V()]), edgeTo_(new DirectedEdge[G.V()])
{
    for (int i = 0; i < G.V(); i++)
        distTo_[i] = INFINITY;
    distTo_[s] = 0;
    pq.push(ele(s, 0.0));
    while (!pq.empty())
    {
        relax(G, pq.top().first);
        pq.pop();
    }
}

Bag<DirectedEdge> DijkstraSP::pathTo(int v)
{
    Bag<DirectedEdge> res;
    if (!hasPathTo(v))
        return res;
    for (DirectedEdge e = edgeTo_[v]; e.from() != -1; e = edgeTo_[e.from()])
        res.add(e);
    return res;
}

void pq_update(edge_pq &pq, const ele &new_data)
{
    edge_pq temp;
    temp.swap(pq);
    bool has_new = false;
    while (!temp.empty())
    {
        ele top_ele = temp.top();
        temp.pop();
        if (top_ele.first == new_data.first)
        {
            pq.push(new_data);
            has_new = true;
        }
        else
            pq.push(top_ele);
    }
    if (has_new)
    {
        pq.push(new_data);
    }
}

分析：若是求解两点之间的最短路径，只需要在优先队列中取到t截止即可。

对于欧拉图来说，Dijkstra有优化的解法。

Dijkstra并不高效，但是可以解决问题，同样缺点还有不能解决负权重加权有向图问题

无环加权有向图中的最短路径算法

思路：

1.distTo[s]初始化为0其他初始化为INF

2.按照拓扑排序顺序对所有点进行relax操作

特点：

1.更快，更方便

2.能够处理负权重有权图的问题

3.还能解决额外的相关问题，比如最长路径

4.是拓扑排序的拓展

实现：

class AcyclicSP
{
public:
    AcyclicSP(WeightedDigraph G, int s);
    ~AcyclicSP() { delete[] distTo_, edgeTo_; }
    double distTo(int v) const { return distTo_[v]; }
    bool hasPathTo(int v) const { return distTo_[v] < INFINITY; }
    Bag<DirectedEdge> pathTo(int v);

private:
    void relax(WeightedDigraph G, int v);

    double *distTo_;
    DirectedEdge *edgeTo_;
};
void AcyclicSP::relax(WeightedDigraph G, int v)
{
    for (DirectedEdge e : G.adj(v))
    {
        int w = e.to();
        if (distTo_[w] > distTo_[v] + e.weight())
        {
            distTo_[w] = distTo_[v] + e.weight();
            edgeTo_[w] = e;
        }
    }
}

AcyclicSP::AcyclicSP(WeightedDigraph G, int s) : distTo_(new double[G.V()]), edgeTo_(new DirectedEdge[G.V()])
{
    for (int i = 0; i < G.V(); i++)
        distTo_[i] = INFINITY;
    distTo_[s] = 0.0;
    Topological top(remove_weight(G));
    for (int v : top.order())
    {
        relax(G, v);
    }
}

Digraph remove_weight(const WeightedDigraph &G)
{
    Digraph res(G.V());
    for (DirectedEdge e:G.edges())
        res.addEdge(e.from(), e.to());
    return res;
}

分析：

对于加权有向图，对点的松弛需要有一定的顺序。无顺序的松弛，不能达到真正效果。

graph TB
0((0));1((1));2((2));3((3));4((4));
0 -->1-->2-->4;0-->3-->4;2-->3;

例如上图，如果relax的顺序是03412，那么此时，放松34后，进行12，放松2的时候对2->3边进行松弛，若此时0->3变为0->1->2->3那么dist[3]的值会被修改，但4的distTo值也应该被修改，改为distTo[4] = distTo[3] + e.weight()。但在松弛中没有这样操作，会导致在对2->4边进行松弛出现问题。

总结以上就是，已经确定了4的距离，若3的距离减小，4应该同步更新。

为了避免这样的情况，我们得出的结论就是松弛边时的指向点不能有已经被记录的点，也就是按照顺序，后面的点不能指向前面的点，也就是拓扑排序的顺序。

总结以上就是，先松弛的点只能指向后松弛的点。

最长路径实现：将distTo都初始化为0，改变relax函数中不等式的方向。

平行任务调度

添加一条关于这个算法的应用

要求：

给定一组特定任务，以及任务各有不同的耗时，并且有先后要求，再加上在若干相同处理器上运行，安排任务在最短时间内完成。

思路：

1.创建无环加权有向图，包含起点和终点，任务和任务耗时用任务点以及它的指出边的权值来表示

2.一个任务指出的边的权值，是其任务的费时

3.一个任务必须在一个任务指向的任务之前完成

4.设置起点s和终止点t，st之间的最长路径即为总耗时

解决：使用最长路径的无环加权有向图中的最短路径算法实现即可。

Bellman-Ford算法（基于队列优化）

Bellman-Ford算法

在做出队列优化之前，先简单介绍一下Bellman-Ford算法的原版

其操作描述十分简单，即对图G的所有边进行V次松弛，时间复杂度高达O(VE)。使用基于队列优化的类似于BFS广度优先搜索，可以大大减少松弛次数，从而大大减少时间。

至于为什么要反复松弛点，正如无环加权有向图中的最短路径算法的解析所示。

思路：

1.利用队列放松点，将起点加入队列

2.取出队列里的点进行放松，并且将其指向的点加入队列，

3.每放松了V次，进行负有向环检测

实现：

#include "SP.hpp"

class BellmanFordSP
{
public:
    BellmanFordSP(WeightedDigraph G, int s);
    ~BellmanFordSP() { delete[] onQ, distTo_, edgeTo_; }

    double distTo(int v) const { return distTo_[v]; }
    bool hasPathTo(int v) const { return distTo_[v] < INFINITY; }
    Bag<DirectedEdge> pathTo(int v);

private:
    void relax(WeightedDigraph G, int v);
    bool hasNegativeCycle();
    void findNegativeCycle();
    Bag<DirectedEdge> negativeCycle() { return cycle;};

    int size;
    int cost = 0;
    bool *onQ;
    double *distTo_;
    DirectedEdge *edgeTo_;
    std::queue<int> que;
    Bag<DirectedEdge> cycle;
};

BellmanFordSP::BellmanFordSP(WeightedDigraph G, int s) : size(G.V()), onQ(new bool[G.V()]), distTo_(new double[G.V()]), edgeTo_(new DirectedEdge[G.V()])
{
    for (int i = 0; i < G.V(); i++)
        distTo_[i] = INFINITY;
    distTo_[s] = 0.0;
    que.push(s);
    onQ[s] = true;
    while (!que.empty() and !this->hasNegativeCycle())
    {
        int v = que.front();
        que.pop();
        onQ[v] = false;
        relax(G, v);
    }
}

void BellmanFordSP::relax(WeightedDigraph G, int v)
{
    for (DirectedEdge e : G.adj(v))
    {
        int w = e.to();
        if (distTo_[w] > distTo_[v] + e.weight())
        {
            distTo_[w] = distTo_[v] + e.weight();
            edgeTo_[w] = e;
            if (!onQ[w])
            {
                que.push(w);
                onQ[w] = true;
            }
        }
        if (cost++ % G.V() == 0)
        {
            findNegativeCycle();
        }
    }
}
void BellmanFordSP::findNegativeCycle()
{
    WeightedDigraph spt(size);
    for (int v = 0; v < size; v++)
        if (edgeTo_[v].from() != -1)
            spt.addEdge(edgeTo_[v]);
    // 寻找有向环判断是否负权重
}

bool BellmanFordSP::hasNegativeCycle()
{
    return !cycle.isEmpty();
}

关于Dijkstra的局限性：

Dijkstra无法处理负有向环，例如以下有权图所示，环1-2-3的值为-0.5。

graph TB
0((0));1((1));2((2));3((3));4((4));
0--0.1-->1--0.2-->2--0.3-->3;3--"-1"-->1;0--0.8-->4--0.1-->3;

根据Dijkstra的步骤以0为起点，当全正权值的时候，Dijkstra的一大特点就是已连接的边不会变化，又由于权值为正，故新点指向已在树中的点时，此边不可能优于已经在树中的边。对于两点，Dijkstra在处理负权值就无法解决：

1.0->1首先被连接，但0->4->3->1由于存在负权值而优先于0->1，但0->1已经被设置

2.当存在负权重环的时候，由0->1->2->3处理到3时，3指向1，此时dist[1]为0.1，dist[3] + e.weight()的值就为-0.4，此时便无法再连接到根节点也就是我们的起点。并变化了树中的0->1

Bellmen-Ford优化分析：

Bellmen-Ford队列优化类似于BFS，回到之前的问题

graph TB
0((0));1((1));2((2));3((3));4((4));0 -->1-->2-->4;0-->3-->4;2-->3;

根据BFS，先1后2再3，此时原本dist[4]的值为0->2->4的权值。在处理3后，若2变为dist[2]为0->1->3->2,那么dist[4]的值也应该被更新，故2又被加入队列，进行重复的放松。也正因为如此，将所有边放松一次并不能达成目标，最坏的情况下将时间复杂度高达O(VE)。

负权环的检测：

我们可以发现，当此算法遇到负权环的时候，将会进入无限的循环，此时，我们就需要定期检查该图是否有负权重环的存在。我们以relax的次数作为标准，每当进行了V次relax，就进行一次检测（当然，这个值也可以小于V，并且每次检测并不代表该图中有负权重环），当存在负权重环，算法应当结束。

Mai Icy

图算法笔记4 - 加权图

加权图

数据类型

有权图

有权边

最小生成树（MST）

前提：

树的特性：

预备理论

切分定理

数据类型

有权无向图

有权边

Prim算法

Prim延时算法

Prim即时算法

KrusKal算法

最短路径（SP）

前提：

Dijkstra算法

无环加权有向图中的最短路径算法

平行任务调度

Bellman-Ford算法（基于队列优化）

Bellman-Ford算法

Mai Icy