现在的位置: 首页 > 综合 > 正文

判断有向图回路

2014年09月05日 ⁄ 综合 ⁄ 共 382字 ⁄ 字号 评论关闭

    First way:

       (1) 删除所有入度为零的顶点及其相发出的边。并将被删除边所指向的顶点的入度减1。

                     重复(1)直到

      case1: 所有顶点被删除(则没有回路)

      case2: 还有顶顶点但没有入度为零的顶点可删除(则存在回路)。
 
 
Second way:
                               深度遍历图,记录已遍历过的结点到数组,如vi是图结点,visited[vi]==1表示,vi这个结点已经遍历过了 
                               如果 visited[vi] == 0 表示未遍历过,。
                               如果图中存在一个环或多个,某个结点必然会遍历二次(在遍历的时候判断一下是不是是否遍历过就行了)

 

抱歉!评论已关闭.