2

我有一个包含 4 个节点的图，其中邻接矩阵如下： 里面的数字表示权重。

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

我正在使用斐波那契堆来存储边缘权重。在每次迭代中，我将合并具有最低边权重的节点对，并更新受此过程影响的所有节点的边权重。我正在努力解决如何保留指向所有受影响节点的指针。我知道处理程序，但是..我真的很挣扎。我希望有人能给我一些关于如何实现这一点的指示，请不要对这篇文章投反对票。我已经完成了作业，安装了 boost，设法让一个简单的堆工作。我只是迷失了如何在给定索引的情况下找到堆。

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));

合并后，边权重将更新，合并节点的 id 将更改为 total_number_of_nodes++。

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

我将每个节点的邻居存储在邻接图中，因此我可以轻松确定哪些节点，因此边缘会受到影响。我现在的主要问题是访问斐波那契堆中的所述节点。

每次执行合并时，我都可以遍历整个堆，但我正在寻找一种更有效的方法

4

0 回答 0