广度优先遍历图

问题描述

       按照给定的起始顶点广度优先遍历图，每一次通过字母顺序选择顶点查找下一层邻接点，打印遍历顺序。

输入

       输入第一行为测试用例个数，后面每一个用例用多行表示，用例第一行是节点个数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

示例输出

a b c d

思路

       与[深度优先遍历]https://www.jianshu.com/p/5349bdf8c146相似

代码

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]);
            findPath(graph,nodes,visited,start,0);
            casesnum --;
        }

    }

    public static void findPath(int[][] graph,String[] nodes,boolean[] visited,int start,int k){
        visited[start] = true;
        System.out.print(nodes[start]);
        if (++k<graph.length)
            System.out.print(" ");
        else
            System.out.println();
        for (int i=0;i<graph.length;i++){
            if (graph[start][i]==1&&visited[i]==false){
                findPath(graph,nodes,visited,i,k);
            }
        }
    }
}