挑战程序设计竞赛（算法和数据结构）——12.3深度优先搜索的JAVA实现

78 阅读 0 评论 52 点赞

我是靠谱客的博主苗条御姐，最近开发中收集的这篇文章主要介绍挑战程序设计竞赛（算法和数据结构）——12.3深度优先搜索的JAVA实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：
在这里插入图片描述

讲解：

我的思路（写的很乱哈哈哈）：

/*
* 心得：如果以后涉及到多步相同的操作，直接写成一个函数，否则很容易遗漏其中的条件，从而出现问题。在本例中，压栈、color数组的赋值、时间增加、时间记录数组的更新就发生过多次的遗漏导致的bug。
*/

import java.util.Scanner;
import java.util.Stack;

public class DepthFirstSearch {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        //建立图的邻接矩阵
        int M[][] = new int[n][n];
        for(int i=0;i<n;i++){
            int id = cin.nextInt();
            int degree = cin.nextInt();
            for (int j=0;j<degree;j++){
                int neighbour = cin.nextInt();
                setMap(M, id, neighbour);
            }
        }

        String[] color = new String[n];
        Stack<Integer> S = new Stack<Integer>();
        int[] f = new int[1000];//入栈处理
        int[] d = new int[1000];//出栈处理
        int time = 0;

        dfs_init(S, M, 0, color, d, f, time);

        for (int i=0;i<n;i++){
            System.out.print((i+1) + " " + f[i] + " " + d[i] + "n");
        }
    }

    public static void setMap(int[][] M, int id, int neighbour){
        M[id-1][neighbour-1] = 1;
    }

    public static void dfs_init(Stack<Integer> S, int[][] M, int u, String[] color, int[] d, int[] f, int time){
        int n = color.length;
        for (int i=0;i<n;i++){//初始化color字符串数组
            color[i] = "white";
        }

        //给第一个节点进行初始化操作
        S.add(0);
        f[0] = ++time;
        color[0] = "grey";
        dfs(S, M, 0, color, d, f, time);
    }

    public static void dfs(Stack<Integer> S, int[][] M, int u, String[] color, int[] d, int[] f, int time){
        boolean flag = true;//用于判断color数组是否全都是black，如果是true，说明全都是black，否则就存在white/grey。、
        int n = color.length;
        for (int i=0;i<n;i++){
            if (color[i].equals("grey") || color[i].equals("white")){
                flag = false;
                break;
            }
        }//经过这个循环后，flag具备判断color数组是否全都是black的功能

        if(flag == true){return;}//如果所有节点都处理过了，那么直接结束了
        else {
            int v1 = findNextElement(M, u);
            if(v1 == -1){//如果不存在下一个节点，那么这个节点处理完毕
                color[u] = "black";
                S.pop();
                d[u] = ++time;
                u = S.peek();
            }
            else{//如果存在下一个节点
                int v2 = isAllSolved(color, M, u);
                if(v2 != -1){//存在至少一个邻接点为“white”
                    u = v2;
                    S.push(u);
                    f[u] = ++time;
                    color[u] = "grey";
                }
                else{//所有的节点都是“grey”或者“black”
                    color[u] = "black";
                    S.pop();
                    d[u] = ++time;
                    if(S.size()!=0){
                        u = S.peek();
                    }
                }
            }
            dfs(S, M, u, color, d, f, time);
        }
    }

    //用于判断节点是否存在其他邻接节点
    public static int findNextElement(int[][] M, int u){
        int n = M.length;
        for (int i=0;i<n;i++){
            if(M[u][i]==1){return i;}
        }
        return -1;
    }

    //用于判断节点的邻接节点有没有还未被处理的节点（color[i]=="white"）
    public static int isAllSolved(String[] color, int[][] M, int u){
        int n = M.length;
        for (int i=0;i<n;i++){
            if(M[u][i]==1 && color[i]=="white"){//只要存在还没有被处理的节点
                return i;
            }
        }
        return -1;
    }
}