0

我正在研究在一个小世界（无向图）中，长距离连接如何缩短任何给定节点之间的路径长度。基本上我有一个链表数组。数组中的每个部分都链接到任一侧的第一个和第二个邻居，然后实现一些随机连接（制作邻接表）。

现在我必须对阵列中的每个点进行 BFS，以查看从阵列中的一个点到另一个点需要多少移动。

例如，这就是阵列的前 9 个点的样子

[1, 2]
[0, 2, 3]
[0, 1, 3, 4]
[1, 2, 4, 5]
[2, 3, 5, 6]
[3, 4, 6, 7]
[4, 5, 7, 8, 114]
[5, 6, 8, 9]
[6, 7, 9, 10]
[7, 8, 10, 11]

如您所见，数组中的点 0 与 1 和 2 相邻，因为另一侧没有任何东西。Spot 6 与 Spot 114 有远程连接之一。

这是我在 bfs amd 上的尝试，我遇到了一些错误。首先你觉得它看起来怎么样？但我得到一个空指针异常就行了

u = q.remove();

空指针异常。知道为什么吗？你现在应该等于1。但我知道为什么它不起作用。我做了一些打印输出以查看它是否正常工作，并且在 addAll 之后 q = [1, 2] 所以当我打印输出 q.remove = 1 时，但由于某种原因现在它停止了我的程序！

public static int bfs(List<Integer>[] smallWorld, int start){

    int distance = 0;
    int size = smallWorld.length;

    //for each location in smallWorld do a bfs to every other location      
    int u;
    int white = 0, grey = 1, black = 2;
    int [] color, d, pie;
    Queue <Integer> q = new <Integer> LinkedList();

    color = new int [size];
    d = new int [size];
    pie = new int [size];

    for( int x = 0; x < size; x++){
        color[x] = white;
        d[x] = -1;
        pie[x] = -1;
    }

    color[start] = grey;
    d[start] = 0;
    pie[start] = -1;
    q.addAll(smallWorld[start]);        //enqueue the adjacent items
    while(q != null){
        u = q.remove();
        for(int v = 0; v < smallWorld[u].size(); v++){      //for every vertex u is adjacent to
            if(color[v] == white){
                color[v] = grey;
                d[v] = d[u] + 1;
                pie[v] = u;
                q.addAll(smallWorld[v]);
            }
        }
        color[u] = black;
    }


    return distance;
}

多谢你们！

4

0 回答 0