需要帮助将 Kruskal 算法应用于使用 2D 结构存储数据的现有邻接矩阵程序
Need help applying Kruskal's Algorithm to an existing adjacency matrix program that uses a 2D struct to store the data
Link 到可运行程序和程序 requirements/specs:
https://github.com/edgr-sanchez/CSCE2110-Graph
到目前为止,我已经实施了该计划的 95%。一切正常运行,并已使用提供的测试文件进行测试。
我在实施时遇到的唯一困难是 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
一开始我们将所有的顶点分割成单独的树。每棵树都由一个索引标识。我们创建一个查找 table 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
容器。
Link 到可运行程序和程序 requirements/specs:
https://github.com/edgr-sanchez/CSCE2110-Graph
到目前为止,我已经实施了该计划的 95%。一切正常运行,并已使用提供的测试文件进行测试。
我在实施时遇到的唯一困难是 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
一开始我们将所有的顶点分割成单独的树。每棵树都由一个索引标识。我们创建一个查找 table 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
容器。