时间戳

首页 > 解决方案 > 使用线性代数或 BFS 查找图的直径

c++ - 使用线性代数或 BFS 查找图的直径

问题描述

我从学校收到作业说我需要在 CPP 中找到图形的直径。问题是我需要为 5000 个图执行此操作，每个图有 1000 个顶点。为了保存我的图表，我使用了这样的向量向量：

std::vector<std::vector<int>> graph

我能够在每个顶点上使用 BFS 找到图的直径并返回“最长最短”路径，但由于复杂性太差，它真的很慢

所以我在网上读到我可以使用线性代数来找出直径是多少，但这值得吗？最后计算是否需要相同的时间？

另外，这是否意味着我必须从向量的向量变为这样的矩阵？

bool** graph

感谢您的热心帮助

标签： c++algorithmlinear-algebrabreadth-first-search

解决方案

我能想到的最快的算法是众所周知的 Floyd-Warshall算法，它具有复杂性O(N^3)（N 是顶点数）。它计算所有顶点对之间的最短路径长度。

对于您的 1000 个顶点图的情况，时间是相当实惠的 - 大约 10 亿步，对于现代 CPU 上的每个图来说，这个算法需要几秒钟，我希望你能负担得起这个时间。该算法将使用 10 亿个非常简单的步骤 - 3 次缓存读取 + 1 次添加 + 1 次比较 + 1 次缓存分配。

下一个 C++ 代码执行整个循环——从字符串流输入，初始化权重，运行 Floyd-Warshall 算法来计算所有顶点对之间的最短距离，找到最大最短距离，输出结果。

可以在 CPU 的不同内核上轻松同时计算多个图，这将使整个计算速度提高数倍。

我的算法支持任何整数权重的边，甚至是负权重。算法的输入应该有权重矩阵 NxN 大小（N 是顶点数），零权重表示没有边（即无限距离）。

在线尝试！

#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main() {
    std::string inps = R"(
        0 0 2 0
        4 0 3 0
        0 0 0 2
        0 1 0 0
    )";
    std::stringstream inp;
    inp.str(inps);

    size_t const inf = size_t(-1) >> 2; // Infinity
    std::vector<std::vector<size_t>> d; // Distance matrix
    // Input
    std::string line;
    while (std::getline(inp, line)) {
        if (line.find_last_not_of(" \r\n\t") == std::string::npos)
            continue;
        d.resize(d.size() + 1);
        std::stringstream ss;
        ss.str(line);
        size_t x = 0;
        while (ss >> x)
            d.back().push_back(x);
    }
    // Compute shortest distances. Algo https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
    for (size_t i = 0; i < d.size(); ++i)
        for (size_t j = 0; j < d[i].size(); ++j)
            if (d[i][j] == 0 && i != j)
                d[i][j] = inf;
    for (size_t k = 0; k < d.size(); ++k)
        for (size_t i = 0; i < d.size(); ++i)
            for (size_t j = 0; j < d.size(); ++j)
                d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
    // Find longest distance.
    size_t maxd = 0, maxi = 0, maxj = 0;
    for (size_t i = 0; i < d.size(); ++i)
        for (size_t j = 0; j < d.size(); ++j)
            if (maxd < d[i][j]) {
                maxd = d[i][j];
                maxi = i;
                maxj = j;
            }
    // Output
    std::cout << "diameter " << maxd << " from vertex " << maxi << " to " << maxj << std::endl;
}

输出：

diameter 7 from vertex 2 to 0

可以看到，从顶点 2 到顶点 0 的直径（最长最短路径长度）等于 7。

推荐阅读