深度优先遍历

问题描述

       按照给定的起始顶点深度优先遍历给定的无向图，尝试所有可能的遍历方式，打印遍历过程中出现的最大深度。

输入

       输入第一行是用例个数，后面每个用例使用多行表示，用例的第一行是图中节点的个数n和起始点，用空格隔开，后面n+1行为图的邻接矩阵，其中第一行为节点名称。值之间使用空格隔开。

输出

       输出深度优先遍历中遇到的最大深度。

示例输入

1
4 a
a b c d
a 0 1 1 0
b 1 0 1 0
c 1 1 0 1
d 0 0 1 0

示例输出

4

思路

       回溯+递归。找到开始节点，依次访问其邻接矩阵，若对应行中值为1，且对应结点没有被访问过（使用布尔数组visited来记录），则记录这次深度搜索的结果为：1+递归（修改visited与开始节点），循环结束后返回深度搜索中的最大值。

代码

import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int casesnum = sc.nextInt();
        sc.nextLine();
        while(casesnum>0){
            String[] temp = sc.nextLine().split(" ");
            String[] nodes = sc.nextLine().split(" ");
            int nums = Integer.parseInt(temp[0]);
            int[][] graph = new int[nums][nums];
            String[][] temp2 = new String[nums][nums+1];
            boolean[] visited = new boolean[nums];
            String startString = temp[1];
            int start = -1;
            for (int i=0;i<nums;i++)
                visited[i] = false;
            for (int i=0;i<nodes.length;i++) {
                if (nodes[i].equals(startString)){
                    start = i;
                    break;
                }
            }
            for (int i=0;i<nums;i++)
                for (int j=0;j<nums+1;j++)
                    temp2[i][j] = sc.next();
            for (int i=0;i<nums;i++)
                for (int j=1;j<nums+1;j++)
                    graph[i][j-1] = Integer.parseInt(temp2[i][j]);
            System.out.println(countDeepth(graph,visited,start));
            casesnum --;
            }
        }

    public static int countDeepth(int[][] graph,boolean[] visited,int start){
        if (start == -1)
            return 0;
        visited[start] = true;
        int max = 1;
        for (int i=0;i<graph.length;i++){
            if (graph[start][i]==1&&visited[i]==false){
                visited[i] = true;
                int temp = 1 + countDeepth(graph,visited,i);
                if (temp>max)
                    max = temp;
                visited[i] = false;
            }
        }
        return max;
    }
}