算法概论实验十

算法概论实验

实验十
实验目的与要求：
（1） 掌握使用图的深度优先搜索算法实现对有向图中是否包含环的判断；
（2） 掌握使用图的深度优先搜索算法实现对有向图的强连通分量的划分。
1．有向图中环的判断问题
【问题描述】
给定一个有向图，要求使用深度优先搜索策略，判断图中是否存在环。
2．有向图的强连通分量问题
【问题描述】
给定一个有向图，设计一个算法，求解并输出该图的各个强连通分量。

import java.util.ArrayList;
public class exam10 {
    //1.有向图判环
    public static String havecycle(int[][] a)
    {   
        if(DFS(a))  //如果没环      
            return "no cycle";
        else
            return "have cycle";
    }
    public static boolean DFS(int[][] a)
    //有环返回false
    {
        boolean test = true;
        int length = a.length;
        String[] color = new String[length];
        for(int i=0;i<length;i++)
            color[i] = "white";
        //int clock = 1;
        for(int i=0;i<length;i++)
            if(color[i] == "white")
            {
                test = explore(a,i,color);
                if(test == false)
                    return false;
            }
        return true;
    }
    public static boolean explore
    (int[][] a,int u,String[] color)    
    //以u为顶点进行探索
    {
        color[u] = "gray";
        for(int v=0;v<a.length;v++)
        {
            if(a[u][v]!=0 && color[v]=="white")
                explore(a,v,color);
            if(a[u][v]!=0 && color[v]=="gray")  
            //如果有一条回边，表示有一个环
                return false;
        }
        color[u] = "black";
        return true;
    }
    //2.找强连通分量
    public static void findSC(int[][] a1)
    {   
        int length = a1.length;
        int[][] a = new int[length][length];
        int[][] b = new int[length][length];
        getGR(a1,b);
        //b是反向图
        getGR(b,a);
        //防止修改原图a=a1
        Set[] set = new Set[length];
        int count = 0;  
        int sum = 0;
        //要在反向图中找一个Post值最大的点,以这个点为起点，在原图上进行DFS，则找到一个强连通部件
        do
        {
            System.out.print("第"+(count+1)+"个连通分量为：");
            getGR(a,b);
            int maxpost = findmaxpost(b);
            set[count]  = DFS2(a,maxpost);      //第一个强连通部件set[0]
            //去掉这个连通部件中的点
            for(int i=0;i<set[count].value.size();i++)
            {
                int p = set[count].value.indexOf(i);
                delete(a,p);    
            }
            sum = sum + set[count].value.size();        //sum计算去掉的点数
            count++;
            System.out.println();
        }while(sum<length);
    }
    //在一个图中找出post值最大的节点点
    public static int findmaxpost(int[][] a)
    {
        int max = 0;
        int maxindex = 0;
        int[] post = new int[a.length];
        DFS1(a,post);
        for(int i=0;i<a.length;i++)
        {
            int temp = max;
            max = Math.max(max, post[i]);
            if(max != temp)
                maxindex = i;
        }
        return maxindex; 
    }
    public static void DFS1(int[][] a,int[] post)   
    {
        int length = a.length;
        String[] color = new String[length];
        for(int i=0;i<length;i++)
            color[i] = "white";
        int[] clock = new int[1];
        clock[0] = 1;
        for(int i=0;i<length;i++)
            if(color[i] == "white")
            {
                explore1(a,i,color,post,clock);
            }
    }
    public static void explore1
    (int[][] a,int u,String[] color,int[] post,int[] clock)//以u为顶点进行探索
    {
        color[u] = "gray";
        clock[0]++;
        for(int v=0;v<a.length;v++)
        {
            if(a[u][v]!=0 && color[v]=="white")
                explore1(a,v,color,post,clock);
        }
        color[u] = "black";
        post[u] = clock[0];
        //System.out.print("post["+u+"]="+post[u]+" ");
        clock[0]++;
    }
    //获得一个图的反向图
    public static void getGR(int[][] a,int[][] b)
    {
        for(int i=0;i<a.length;i++)
            for(int j=0;j<a.length;j++)
                b[i][j] = a[j][i];
    }
    //返回u能访问到的点集
    public static Set DFS2(int[][] a,int u) 
    {
        Set s = new Set();
        int length = a.length;
        String[] color = new String[length];
        for(int i=0;i<length;i++)
            color[i] = "white";
        //初始化完成
        explore2(a,u,color,s);
        return s;
    }
    public static void explore2(int[][] a,int u,String[] color,Set s)//以u为顶点进行探索
    {
        s.value.add(u);
        System.out.print(u+" ");
        color[u] = "gray";
        for(int v=0;v<a.length;v++)
        {
            if(a[u][v]!=0 && color[v]=="white")
                explore2(a,v,color,s);
        }
        color[u] = "black";
    }   
    //删除a中所有与p相连的边
    public static void delete(int[][] a,int p)
    {
        for(int i=0;i<a.length;i++)
        {
            a[i][p] = 0;
            a[p][i] = 0;
        }       
    }
    public static void main(String[] args) {
        //测环
        int[][] a = new int[6][6];
        for(int i=0;i<a.length;i++)
            for(int j=0;j<a.length;j++)
                a[i][j] = 0;    
        a[1][0] = 1;a[1][3] = 1;a[2][1] = 1;a[3][4] = 1;
        a[4][5] = 1;a[5][2] = 1;a[5][3] = 1;
        System.out.println(havecycle(a));
        //强连通分量
        findSC(a);
    }
}