1

假设您有一个加权图。从一个随机节点开始，如何使用深度优先搜索（修改使用显式堆栈的迭代算法）来检查在某个权重半径内存在哪些节点？（可以从这个节点以特定的权重到达。）

4

1 回答 1

3

假设我们使用类型Node来表示图中的一个节点。在最简单的情况下，Node可能只是一个整数 ( int)。

通常，我们使用显式类型的堆栈Node。在您的情况下，我们可以使用类型堆栈，pair<Node,int>其中pair<A,B>是对的类型，而int表示从您的起点到 this 的距离Node。

假设我们现在处于Node u距离d。对于相邻的Node v，让w是边缘的权重uv。然后只需推入pair(v, d+w)堆栈。最初，推送深度优先搜索的起点pair(v0, 0)在哪里。v0

于 2012-12-26T11:09:36.967 回答