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

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

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

提前致谢!

最佳答案

首先，我要说明一下:实际上，您的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;
}

实际上，您甚至根本不需要trees容器。

关于c++ - 需要帮助将Kruskal算法应用于现有的使用2D结构存储数据的邻接矩阵程序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33664289/