求最短路径
深度优先遍历
广度优先遍历
拓扑排序
如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。
算法:
第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。
第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点,则存在环,否则没有环。
其实你画个图比划一下就很清楚了。通常处理图结构的时候是转换成树结构,通常也就是按照深度遍历的方式转换, 转换的时候是从起始节点开始,找节点的孩子,找到了就保存下来,然后找孩子的孩子,每次找到之后都保存下来, 这就是深度遍历,如果有向图中存在圈圈,那么就必然会出现这种情况“某个节点的孩子已经存在于你保存的节点里了”, 一旦出现就表示有圈圈。 广度遍历就不行了,因为有向图与树最大的区别之一是两个图的节点可能会有公共的孩子,所以用广度遍历的方式,即使出现了重复, 也不能证明有圈圈。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题