cf290-2015-2-3总结与反思（dfs判断无向图是否有环）

bool dfs(int i,int pre)

{

    visit[i]=true;

    for(int j=;j<=v;j++)

        if(g[i][j])

        {

            if(!visit[j])

                return dfs(j,i);

            else if(j!=pre)  //如果访问过，且不是其父节点，那么就构成环

                return false;

        }

}

方法：从一个顶点出发深度优先遍历可遍历所有结点，并且没有环或只有n-1条边。

若判断有环：可以在遍历时记住父结点，v的子结点w已被访问，且不是结点v的父结点，则存在环。

若判断只有n-1条边，循环一下很容易得到。用拓扑排序即可，因为无向图各顶点都有入度.

假设不存在自环与平行边

巴特西

cf290-2015-2-3总结与反思（dfs判断无向图是否有环）

最新文章

热门文章