我无法想象这个问题。
所以我有一个有向加权图。我需要使用 Dijskra 算法扫描此图并打印出最短路径。我必须使用堆/优先级队列,根据我目前的知识,我知道它们是同一回事。
但是,一个图可以有2个以上的子节点,而一个堆只能有2个子节点。当我将其放入堆格式时,其他 child (边缘)会发生什么?
最佳答案
堆的表示本身与图的结构无关。
您正在处理图表。您需要找到具有最小距离的顶点,然后使用它来确定与它的最小距离。堆正在帮助你得到那个东西。仅此而已。
在堆中,层并不代表图的层次结构,它只是将堆的层与任何节点的值都将小于其子节点的值的属性相关联。就是这样。图中的同胞可能在堆中处于父子关系。
您不必认为要使堆工作或使 Dijkstra 也需要模仿堆中的图形结构。这不是做这件事的方法。(你也做不到)。
当我将其放入堆格式时,其他子节点(边)会怎样?
- 什么都不会发生。只要您使用适当的 key 插入堆中,它就会正常工作。就是这样。
关于c - 使用堆/优先级队列表示有向加权图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47245458/