oj-广度优先遍历图-java

Description

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

Input

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

Output

输出遍历顺序，用空格隔开

Sample Input 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

Sample Output 1

a b c d

Code

package org.alphacat.second;

import java.util.*;

public class BFS {

    private static int EDGE_FLAG = 1;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int t = scanner.nextInt();
            for (int i = 0; i < t; i++) {
                int n = scanner.nextInt();
                String beginPoint = scanner.next();
                HashMap<String, Integer> nameToIndexMap = new HashMap<>(n);
                HashMap<Integer, String> indexToNameMap = new HashMap<>(n);
                for (int j = 0; j < n; j++) {
                    String edgeName = scanner.next();
                    nameToIndexMap.put(edgeName, j);
                    indexToNameMap.put(j, edgeName);
                }
                int[][] edges = new int[n][n];

                for (int j = 0; j < n; j++) {
                    String crrEdge = scanner.next();
                    int crrIndex = nameToIndexMap.get(crrEdge);
                    for (int k = 0; k < n; k++) {
                        edges[crrIndex][k] = scanner.nextInt();
                    }
                }
                List<String> res = problem(beginPoint, edges, nameToIndexMap, indexToNameMap);
                print(res);
            }
        }
    }

    private static void print(List<String> res) {
        StringBuilder sb = new StringBuilder();
        int lastIndex = res.size() - 1;
        for (int i = 0; i < lastIndex; i++) {
            sb.append(res.get(i));
            sb.append(" ");
        }
        sb.append(res.get(lastIndex));
        String output = sb.toString();
        System.out.println(output);
    }

    private static List<String> problem(String beginPoint, int[][] edges
            , HashMap<String, Integer> NameToIndexMap, HashMap<Integer, String> IndexToNameMap) {
        int beginIndex = NameToIndexMap.get(beginPoint);
        HashSet<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(beginIndex);

        List<String> res = new ArrayList<>(edges.length);
        while (!queue.isEmpty()) {
            int crrIndex = queue.poll();
            if (visited.contains(crrIndex)) {
                continue;
            }
            visited.add(crrIndex);
            String crrEdgeName = IndexToNameMap.get(crrIndex);
            res.add(crrEdgeName);

            for (int i = 0; i < edges.length; i++) {
                if (edges[crrIndex][i] == EDGE_FLAG) {
                    queue.offer(i);
                }
            }
        }

        return res;
    }
}