c++ - 需要帮助将 Kruskal 算法应用于使用 2D 结构存储数据的现有邻接矩阵程序

Question

可运行程序和程序要求/规范的链接:

https://github.com/edgr-sanchez/CSCE2110-Graph

到目前为止，我已经实现了该计划的 95%。一切正常运行，并已使用提供的测试文件进行了测试。

我唯一在实现时遇到困难的是 Kruskal 算法，这是因为我不太确定我需要如何使用我现有的数据结构将其传递给 Kruskal 算法。

澄清几件事:在此程序中运行 Kruskal 算法不应该对现有数据进行更改，它应该只计算最小生成树并将其打印出来。

在我的程序上运行 kruskal 命令应该以邻接列表格式输出最小生成树，包括街道名称 (S##) 和距离，如下所示:

NH    NK(S02,11)    NP(S03,13)
NK    NH(S02,11)    NL(S01,24)
NL    NK(S01,24)
NM    NW(S05,15)
NP    NH(S03,13)    NW(S07,12)
NW    NM(S05,15)    NP(S07,12)

我需要实现它的位置在 /src/SanE_10_P3_AdjacencyMatrix.cpp 208 行。

无论如何，我提供我的代码和所有这些信息来帮助您理解我的代码。我不希望它是为我而写的。我很想简单地获得一些关于如何使用我现有的结构来实现它的指导:

struct {
    bool exists = false;
    std::string name = "";
    int distance = empty;
} node[MAXNODES][MAXNODES];

这是当前输出以及剩余的预期输出:

http://i.imgur.com/fMXTaGn.png

提前致谢!

Answer 1

首先我想说明一下:实际上，您的node 数组描述的是边，而不是节点。这里的节点是索引。无论如何，我保留原样。我假设你的图是无向的。以下是如何使用您的结构实现 Kruskal 算法。

定义函数:

 std::vector<std::pair<int, int>> kruskal() 
 {
     std::vector<std::pair<int, int>> mst; //our result

一开始我们将所有顶点分割成单独的树。每棵树都由一个索引标识。我们创建一个查找表 treesByVertex 以按顶点查找树的索引。

    std::map<int, std::set<int>> trees;
    std::map<int, int> treeByVertex;
    for (int i = 0; i < MAXNODES; ++i)
    {
        std::set<int> tree; // a tree containing a single vertex
        tree.emplace(i); 
        trees.emplace(i, tree); //at startup, the index of a tree is equaled to the index of a vertex
        treeByVertex.emplace(i, i);
    }

然后我们创建一个辅助结构edges，它将包含一个距离递增的边列表:

    std::multimap<int, std::pair<int, int>> edges;
    for (int i = 1; i < MAXNODES; ++i)
        for (int j = 0; j < i; ++j)
            if (node[i][j].exists)
                edges.emplace(node[i][j].distance, std::make_pair(i, j));

按升序遍历所有边并测试它是否连接两棵不同的树。如果为真，我们将这条边添加到 mst 并合并这两棵树:

    for (const auto& e : edges)
    {
        int v1 = e.second.first;
        int v2 = e.second.second;
        if (treeByVertex[v1] != treeByVertex[v2]) //use our lookup table to find out if two vertexes belong to different trees
        {
            mst.emplace_back(v1, v2); //the edge is in mst
            trees[v1].insert(trees[v2].begin(), trees[v2].end()); //merge trees
            for (int v : trees[v2]) //modify lookup table after merging
                treeByVertex[v] = treeByVertex[v1];
        }
    }

    return mst;
}

事实上，你甚至根本不需要树容器。