進步主義 2023-01-13 14:21 采纳率: 33.3%
浏览 19
已结题

DFS算法是怎么实现逆拓扑排序的?

有向图DFS算法是怎么实现逆拓扑排序的? 不是很懂其中的实现过程 麻烦讲的通俗易懂一点

  • 写回答

1条回答 默认 最新

  • 谛凌 2023-01-13 14:36
    关注

    深度优先遍历图

    1. 将出度为0的结点设置为已访问
    2. 并且,若一个结点的所有下一结点均已访问,则将其设为已访问

    如 a->b, a->c, b->c, b->e:

    1. 深度优先a-b-c,c出度为0,输出c
    2. 退回一个结点到b,访问e,e出度为0,输出e
    3. 退回上一结点b,b的两个下一结点(c、e)均已访问,则将b输出,b设置为已访问
    4. 退回上一结点a,a的两个下一结点(b、c)均已访问,则将a输出,a设置为已访问
      至此遍历完毕,逆拓扑排序:c-e-b-a
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
    進步主義 2023-01-13 15:05

    谢谢 能解释一下原理吗

    回复
    谛凌 回复 進步主義 2023-01-13 15:10

    原理就是每个点后面的所有点都访问了以后才输出该点,就是把出度为0的逐渐从图中输出,也就是逆拓扑排序

    回复
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 1月21日
  • 已采纳回答 1月13日
  • 创建了问题 1月13日

悬赏问题

  • ¥15 Android系统裁剪
  • ¥15 雄安新区高光谱数据集的下载网址打不开
  • ¥66 android运行时native和graphics内存详细信息获取
  • ¥100 求一个c#通过CH341读取数据的Demo,能够读取指定地址值的功能
  • ¥15 rk3566 Android11 USB摄像头 微信
  • ¥15 torch框架下的强化学习DQN训练奖励值浮动过低,希望指导如何调整
  • ¥35 西门子博图v16安装密钥提示CryptAcquireContext MS_DEF_PROV Error of containger opening
  • ¥15 mes系统扫码追溯功能
  • ¥40 selenium访问信用中国
  • ¥20 在搭建fabric网络过程中遇到“无法使用新的生命周期”的报错
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部