首页 > 其他 > 详细

有向图是否存在环

时间:2014-02-23 03:47:27      阅读:315      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
//根据深度优先搜索策略判断一个有向图是否存在环
public class FindCircle {

    private boolean[] visited;//访问标记数组
    private LinkStack S=new LinkStack();//按深度优先遍历访问的先后顺序记录在一个连通分支中的顶点元素
    private boolean find = false;
    
    public void findCircle(ALGraph G) throws Exception
    {
        visited = new boolean[G.getVexNum()];
        for(int v=0;v<G.getVexNum();v++)
            visited[v]=false;
        for(int v=0;v<G.getVexNum();v++)
        {
            if(!visited[v])
                find_DFS(G,v);
        }
        if(find)
            System.out.println("此有向图有环");
        else
            System.out.println("此有向图无环");
            
    }

    private void find_DFS(ALGraph G, int v) throws Exception {

        if(!find)
            visited[v]=true;
        S.push(v);
        for(int w=G.firstAdjVex(v);w>=0;w=G.nextAdjVex(v, w))
        {
            if(visited[w]&& isDuplicate(w))
                find=true;
            else
                find_DFS(G,w);
        }
        
    }

    //判断栈S内是否存在值为w的元素,同时不改变原来的栈中的元素顺序。
    private boolean isDuplicate(int w) {
        LinkStack S1=new LinkStack();//辅助栈
        while(!S.isEmpty() && !((Integer)S.peek()).equals(w))
        {
            S1.push(S.pop());
        }
        if(S.isEmpty())
        {
            //S为空的时候,说明在while循环中,S中的所有的元素都pop出来,放在S1栈内,即没有和w相同的元素
            S.push(S1.pop());
            return false;
        }
        else
            return true;
    }
}
bubuko.com,布布扣

有向图是否存在环

原文:http://www.cnblogs.com/happinessqi/p/3560948.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!