Я новичок в C ++ и пытаюсь реализовать алгоритм Крускала для нахождения минимального остовного дерева взвешенного (связного) неориентированного графа.
Я начал с создания класса WeightedGraph.
class WeightedGraph
{
private:
int V;
map<pair<int, int>, int> w_map;
public:
// constructors and other member functions.
};
Изначально я определил личный элемент данных с именем w_map выше для хранения веса каждого ребра. То есть, если {u, v} является ребром графа, то w_map[{u, v}] дает ссылку на вес этого ребра.
Одним из шагов алгоритма Крускала является сортировка всех ребер графа по неубывающему порядку их весов.
Насколько я понимаю, map сортируется только по ключу (либо с оператором < по умолчанию, либо с двоичным предикатом, заданным пользователем). A map нельзя напрямую отсортировать по mapped_value. Пожалуйста, поправьте, если я ошибаюсь.
Один из вариантов - определить и использовать вместе с w_map, указанным выше, set<pair<pair<int, int>, int> (назовите его w_set), предоставив ему наш собственный предикат, так что каждый элемент a из w_map будет скопирован в w_set в соответствии со значением a.second (его вес).
Итак, если наш предикат такой:
bool Comparer(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b)
{
return a.second < b.second;
}
тогда мы можем определить w_set следующим образом:
set<pair<pair<int, int>, int>, decltype(Comparer)*> w_set(Comparer);
и использовать его в функции-члене для доступа к итераторам закрытого члена w_map.
Но
Я думал, что если вместо
- Использование
map для хранения краев и веса.
- Определение функции-члена для возврата только набора с отсортированными по весу ребрами.
мы непосредственно используем набор того же типа, что и w_set, в качестве элемента данных WeightedGraph. В этом случае при вставке каждого элемента набор будет отсортирован, как и ожидалось.
Итак, я сделал следующее:
class WeightedGraph
{
private:
int V;
set<pair<pair<int, int>, int>, decltype(Comparer)*>w_sorted(Comparer);
public:
// constructors and other member functions.
};
Но я получаю следующую ошибку:
Unknown type name 'SortByWeight'
не распознает SortByWeight, который был передан в качестве параметра comp конструктору set.
Честно говоря, я не знаю, что я делаю неправильно. Я думаю, что возиться с чем-то довольно очевидным (возможно, с областями видимости), но я не могу понять, что.