考研题:有向图中根节点算法

来源:百度知道 编辑:UC知道 时间:2024/05/22 02:20:25
在有向图G中,如果r到G中每个节点都有路径可以到达,则称节点r为G的根节点。编写算法,判断有向图G是否有根。若有,则打印所有根接点的值(要求先用文字写出实现的基本思想,在用C语言写出算法)

基本思想是使用深度优先搜索

以每个顶点作为深度优先搜索的起始结点,如果一次深度优先搜索即可访问到图中所有结点,则该结点即为根。如此每个结点作为起点执行一次深度优先搜索即可找出所有的根。

算法:
深度优先搜索是一种很简单的算法,在外面套一层循环就可以了。