Кучи Фибоначчи — как сохранить указатель на значение узла?

У меня есть график с 4 узлами, где матрица смежности выглядит следующим образом: Числа внутри указывают веса.

____1___2___3___4__
1 |   | 10| 5 | 1
___________________
2 |10 |   |   |
___________________
3 | 5 |   |   |
___________________
4 | 1 |   |   |
___________________

Я использую кучу Фибоначчи для хранения веса ребер. На каждой итерации я буду объединять пару узлов с наименьшим весом ребра и обновлять веса ребер всех узлов, на которые влияет этот процесс. Я борюсь за то, как я могу сохранить указатель на все затронутые узлы. Я знаю о обработчиках, но .. ну, я просто очень борюсь. Я надеюсь, что кто-то может дать мне несколько советов о том, как я могу реализовать это, и, пожалуйста, не понижайте этот пост. Я сделал свою домашнюю работу, установил повышение, сумел заставить работать простую кучу. Я просто заблудился от того, как я могу найти кучу данных индексов.

struct radig_distance
{
float distance;
int id1, id2;

radig_distance(int i, int j, float dist) : id1(i), id2(j), distance(dist) { }
};

struct compare_dist
{
//for min heap implementation
bool operator()(const radig_distance& n1, const radig_distance& n2) const
{
return n1.distance > n2.distance;
}
};

//fibonacci heap test
boost::heap::fibonacci_heap<radig_distance, boost::heap::compare<compare_dist>> test_heap;
vector<boost::heap::fibonacci_heap<radig_distance, boost::heap::compare<compare_dist>>::handle_type> test_handle;

test_handle.push_back(test_heap.push(radig_distance(1, 2, 10)));
test_handle.push_back(test_heap.push(radig_distance(1, 3, 5)));
test_handle.push_back(test_heap.push(radig_distance(1, 4, 1)));

// nodes that will be affected after merge of 1 and 4
// 2 and 3
int n[2] = { 2, 3 };

//remove edge with min element
test_heap.pop();

//update affected nodes. merged nodes will be given id of max + 1
//obviously wrong. how can i immediately access nodes whose id2 are 2 and 3
test_heap.update(test_handle[n[0]], radig_distance(5, n[0], 9.5));
test_heap.update(test_handle[n[1]], radig_distance(5, n[1], 4.5));

После слияния веса ребер будут обновлены, а у объединенного узла его идентификатор будет изменен на total_number_of_nodes ++.

  __5___2___3___
5 |   | 9.5| 4.5
______________
2 |9.5|   |
______________
3 | 4.5|   |
______________

У меня есть соседи каждого узла, хранящиеся в карте смежности, чтобы я мог легко определить, какие узлы и, следовательно, ребра будут затронуты. Моя главная проблема сейчас — доступ к указанным узлам в куче Фибоначчи.

Я мог бы просто перебирать всю кучу каждый раз, когда выполняется слияние, но я искал более эффективный способ

2

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]