C++假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法
答案:1 悬赏:80 手机版
解决时间 2021-04-05 13:39
- 提问者网友：咪咪
- 2021-04-04 23:36
C++假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法
最佳答案
- 五星知识达人网友：躲不过心动
- 2021-04-05 00:33
我可以给你一个思路，先dfs判断这个图有没有环，如果是DAG就直接拓扑排序，如果不是DAG的话可以考虑将有向图删去一些边，变成一棵树，考虑边A指向B，可以理解为A是B的父亲节点，然后dfs一下就能得到一棵树，接下来逐一枚举每条边C指向D，如果树上C与D间没有边，就输出树上从C到D路径上所有边和C指向D的这条边
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯
| 正方形一边上任一点到这个正方形两条对角线的 |
| 阴历怎么看 ？ |