gpt4 book ai didi

algorithm - 将无向图转换为带约束的有向图

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:31:37 25 4
gpt4 key购买 nike

给定一个无向图和一个节点,你如何将图修改为有向图,使得任何路径都通向一个特定节点。这个问题在 SE 面试中成为一个流行的算法问题

最佳答案

这只是创建一个以给定节点为根(并定向到)的树,然后将其完成为 DAG,任何搜索算法(例如 BFS 或 DFS)都可以为您提供解决方案:从给定的节点开始,使用搜索算法——每当遇到一个节点,将它连接到一个已经连接的节点(通常是你到达它的那个节点),然后你可以根据顺序设置剩余边缘的方向您遇到节点的位置(从后者到较早)

关于algorithm - 将无向图转换为带约束的有向图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14676280/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com