假设你有一个加权图。从随机节点开始,如何使用深度优先搜索(修改使用显式堆栈的迭代算法)来检查哪些节点存在于某个权重半径内?(可以从该节点以特定权重访问。)
发布于 2012-12-26 19:09:37
假设我们使用类型Node来表示图中的一个节点。在最简单的情况下,Node可以只是一个整数(int)。
通常,我们使用Node类型的显式堆栈。在您的示例中,我们可以使用类型为pair<Node,int>的堆栈,其中pair<A,B>是一对类型,int表示从起点到此Node的距离。
假设我们现在在Node u使用distance d。对于相邻的Node v,让w为边缘uv的权重。然后只需将pair(v, d+w)推送到堆栈。最初,推送pair(v0, 0),其中v0是深度优先搜索的起点。
https://stackoverflow.com/questions/14039676
复制相似问题