Нужна помощь в применении алгоритма Крускала к существующей матричной программе смежности, которая использует 2D-структуру для хранения данных
Ссылка на работающую программу и требования / спецификации программы:
https://github.com/edgr-sanchez/CSCE2110-Graph
До сих пор я реализовал 95% программы. Все работает правильно и было протестировано с использованием предоставленного тестового файла.
Единственное, что у меня возникают проблемы с реализацией — это алгоритм Крускала, потому что я не совсем уверен, как мне нужно использовать существующую структуру данных, чтобы передавать ее через Крускал.
Чтобы уточнить несколько вещей: Запуск алгоритма Крускала в этой программе не должен вносить изменения в существующие данные, он должен только вычислить минимальное связующее дерево и распечатать его.
Запуск 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 Контейнер здесь вообще.
Другие решения
Других решений пока нет …