Wx::

Prim,Kruscal,Dijkstra,Floyd

召唤图论四大神龙

Prim

在求解最小生成树中,Prim 更适合于稀疏图

const int INF = 0x3f3f3f;
const int maxn = 105;
int n; // 点数
bool vis[maxn];
int cost[maxn][maxn]; // 路径权值(花费)矩阵
int lowcost[maxn];    // prim 的辅助矩阵
int prim() {
    // 暂以点 0 为起点
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = true;
    for (int i = 1; i < n; i++)
        lowcost[i] = cost[0][i];
    for (int i = 1; i < n; i++) {
        // 循环 n-1 次
        // 首先找出当前最短路径,及其端点:
        int mincost = INF;
        int p = -1;
        for (int j = 1; j < n; j++) {
            if (lowcost[j] < mincost && !vis[j]) {
                mincost = lowcost[j];
                p = j;
            }
        }
        if (mincost == INF)
            return -1; // 原图不连通
        ans += mincost;
        vis[p] = true;
        // 更新 lowcost:
        for (int j = 1; j < n; j++) {
            if (cost[p][j] < lowcost[j] && !vis[j]) {
                lowcost[j] = cost[p][j];
            }
        }
    }
    return ans;
}

Kruscal

最小生成树

  • 对边权值排序(采用间接排序)
  • 每次挑选权值 w 最小的边 e
  • 用并查集判断 e 的两端点是否在同一连通分量,若不在,则该边为最终生成树的边,且将该边两端点并入同一连通分量(并查集)
  • 时间复杂度:n2
// Minimal Spanning Tree - Kruscal
const int maxn = 100, maxm = maxn * maxn; // 最大点、边数
int n = 0, m = 0; // 点数、边数

int w[maxm]; // 每个边的权值
int u[maxm]; // 每个边的起点
int v[maxm]; // 每个边的终点
vector<int> ansEdge;

int r[maxm]; // 用来对“边”间接排序的数组
int p[maxn]; // i 的父结点(基于并查集,用来查找其根结点)

bool cmp(const int i, const int j) {
    // 间接查找中的比较函数
    // 排的是 i,j 的序,但依据是 w[i],w[j]
    return w[i] < w[j];
}

int findRoot(int i) {
    // 并查集中查找点 i 的根
    if (p[i] == i)
        return i;
    else
        return p[i] = findRoot(p[i]);
    // 顺便直接将 i 的父结点更新为集合的根,以提高之后的找根效率
}

int kruscal() {
    // 返回最小生成树的权值
    // 最小生成树的边存在 ansEdge 中

    for (int i = 0; i < n; i++) {
        p[i] = i; // 初始化并查集,p[i] == i 时它自己就是根
    }
    for (int i = 0; i < m; i++) {
        r[i] = i; // 初始化边序号
    }

    int ans = 0; // 最终权值和
    int e, x, y;
    sort(r, r + m, cmp);
    for (int i = 0; i < m; i++) {
        e = r[i];
        x = findRoot(u[e]);
        y = findRoot(v[e]);
        if (x != y) {
            ansEdge.push_back(e); // 纳入最小生成树的边
            ans += w[e];
            p[x] = y; // 把根 y 作为根 x 的父结点,即把 x 集合并入 y
        }
    }
    return ans;
}

int main() {
    // 使用示例:
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
    }
    cout << kruscal() << endl;
    // 如多组测试数据,需要初始化 p[]:memset(p, 0, sizeof(p));
    return 0;
}



Dijkstra

单源最短路径,即从固定一点出发到其他各点的最短路径

Dijkstra 的思想为:
  1. 从起点开始,找到当前与起点距离 dis[u] 最短的点 u(第一次找到的便是起点本身),并标记 u 为“已完成的点”;
  2. 从 u 出发,对以 u 为起点的每条边的终点 v 进行“松弛操作”,即:当 dis[u]+weight[u][v] < dis[v] 时,更新 dis[v];
  3. 返回步骤 1,在所有“未完成的点”中继续寻找 dis[u] 最短的点 u
n2 复杂度版:

基于上述思想,另设数组 fa[],当当前点的距离更新时,记录其上一节点(父结点),即 fa[v] = u,以方便最终输出路径。

const int maxn; // 点上限个数,用于设数组
int n; // 点个数

int w[maxn][maxn]; // 初始各边权值(长度)
int dis[maxn]; // 从 0 出发到各点的最短距离
int fa[maxn]; // 每个结点的父结点(从 0 点到这点的路程上改点之前一个结点,便于输出路径)

void dij() {
    bool vis[maxn];
    memset(vis, 0, sizeof(bool)*n); // 初始化 vis 数组前 n 元素
    dis[0] = 0;
    for (int i = 0; i < n; i++) {
        dis[i] = INF;
    }

    int minDis, minV; // 当前循环中最短边,最短边的终点
    for (int i = 0; i < n; i++) { // 紫书这里有错?循环 n-1 次不就行了?
        minDis = INF;
        for (int j = 0; j < n; i++) {
            if (!vis[j] && dis[j] < minDis) {
                minDis = dis[j];
                minV = j;
            }
        }
        vis[minV] = true;
        for (int j = 0; j < n; i++) {
            if (dis[minV] + w[minV][j] < dis[j]) {
                dis[j] = dis[minV] + w[minV][j];
                fa[j] = minV;
            }
        }
    }
}

mlogn 复杂度版

基于主体思想,优化两方面:

  • 用优先队列优化每次弹出当前到起点最短且还未确定最短路的点的过程(以数组 done[] 记录该点是否已完成)

  • 存图的数组采用 vector<int> G[maxn]G[i][j] 表示第 i 点的第 j 条边在存边的数组 edges 中的序号,方便从 i 点直接遍历其出发的各边

  • 除此以外,形式上封装为一个结构体(也就是类)

// 为与之后网络流风格一致,定义边:
struct Edge {
    int from, to, w; // 紫书这里用了 dist 表示 w
    Edge(int u, int v, int w) :from(u), to(v), w(w) {}
};

struct Dij {
    int n, m; // 点数,边数
    vector<Edge> edges;
    vector<int> G[maxn]; // 以 G 存点,以 vector 存该点的边,以便 Dij 中的遍历更新
    bool done[maxn]; // 是否已找到最短路
    int d[maxn]; // s(起点)到各点距离
    int p[maxn]; // 最短路中结点 j 的以其为终点的弧编号

    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++) {
            G[i].clear();
        }
        edges.clear();
    }

    void addEdge(int from, int to, int w) {
        edges.push_back(Edge(from, to, w));
        m = edges.size();
        G[from].push_back(m - 1);
    }

    struct HeapNode {
        int d, u; // 距离,终点(我觉得紫书这里应该用 v,与前面保持一致)
        bool operator < (const HeapNode &rhs) const {
            return d > rhs.d; // 距离越远优先级越低(越晚弹出)
        }
    };

    void dij(int s) {
        // 以 s 为起点

        // typedef pair<int, int> pii // 定义二元组 (d[i],i) 来每次选 d 最小的边和终点
        // priority_queue<pii, vector<pii>, greater<pii> >q
        // 但不太直观,所以之后还是用结构体 HeapNode

        priority_queue<HeapNode> Q;
        memset(done, 0, sizeof(bool)*n);
        for (int i = 0; i < n; i++) {
            d[i] = INF;
        }
        d[s] = 0;
        Q.push(HeapNode{ 0, s }); // 这个定义涨姿势
        while (!Q.empty()) {
            HeapNode x = Q.top();
            Q.pop();
            int u = x.u;
            if (done[u]) continue;
            done[u] = true;
            for (int i = 0; i < G[u].size(); i++) {
                Edge& e = edges[G[u][i]];
                if (e.w + d[u] < d[e.to]) {
                    d[e.to] = e.w + d[u];
                    p[e.to] = G[u][i];
                    Q.push(HeapNode{ d[e.to], e.to });
                    // 第一次遍历因为初始化为 INF,所以所有点都会入队
                }
            }
        }
    }
};

int main() {
    // 测试:

    // 只需要录入边数和边的 u v w:
    Dij dij;
    int n, u, v, w;
    cin >> n;
    dij.init(n);
    for (int i = 0; i < dij.n; i++) {
        cin >> u >> v >> w;
        dij.addEdge(u, v, w);
        dij.addEdge(v, u, w); // 无向图每条边都是双向通行的
    }
    dij.dij(0);
    for (int i = 0; i < dij.n; i++) {
        cout << dij.d[i] << ends;
    }
    cout << endl;

    return 0;
}

Floyd

任意两点间的最短路径,任意两点间的连通与否

代码理解起来相对来说最“暴力”,因为 Floyd 求的是任意两点间的最短路,所以势必要有 n3 的复杂度,所以直接三重循环(i:起点,j:终点,k:起点终点之间任一点)即可

任意两点间最短路
// 感觉有点动态规划的意思...
void floyd() {
    // 初始化距离数组,应在读入数据时初始化吧...
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         d[i][j] = INF;
    //     }
    //     d[i][i] = 0;
    // }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][k] < INF && d[k][j] < INF) {
                    // 避免两个初始 INF 相加后的和超过 INF,所以判断一下
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
}

有向图的闭包传递(Transitive Closure)

即:判断任意两点间是否直接或间接连通,Floyd 的三重循环稍加更改即可实现

void tc() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = false;
        }
        d[i][i] = true;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
            }
        }
    }
}
  • d[i][j]==true 时从 i 到 j 直接或间接连通

  • d[i][j]==d[j][i]==true 时两点相互连通



More

虽然其中一些代码还不能手写出来,不过加油吧!


3

评论(0

评论 取消
验证码:
搜索