图的最短路径问题(BFS)

HackerRank上面简单总结下Graph中用BFS解决最短路径问题, 做BFS的时候需要用一个queue来记录nextToVist的所有点。

public class Graph {
    private Node[] nodes;
    private static EDGE_DISTANCE = 6;

    public Graph(int size){}
    public class Node{}
    public Node getNode(int id){}
    public void addEdge(int first, int second){}
    public int[] shortestReach(int startId) {
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(startId); // 加入起始点

        int[] distances = new int[nodes.length];
        Arrays.fill(distance, -1); //如果没找到,默认距离为-1
        distances[startId] = 0 // 初始距离,start=> start自己的距离为0
        // BFS
        while(!queue.isEmpty()) {
            int nodeIndex = queue.poll();
            for (int neighbor: nodes[nodeIndex].neighbors) {
                if (distance[neighbor] == -1){ // 没有被visit
                    distances[neighbor] = distances[nodeIndex] + EDGE_DISTANCE;
                    queue.add(neighbor);
                } 

            }
        }
        return distances;
    }
}
Advertisements