在java中创建一个距离图中起始顶点的距离数组

Question

我在实现一种使用BFS从所选起始顶点创建距离数组的方法时遇到了问题，目前它在某些情况下似乎有效，但在较大的图中失败了。其思想是数组中的每个索引表示图中相应的顶点。

这是相关的代码

public int[] getDistances(Graph g, int startVertex) {
boolean[] visited = new boolean[g.getNumberOfVertices()];
int[] distance = new int[g.getNumberOfVertices()];
for (int i = 0; i < distance.length; i++)
{
distance[i] = -1;
}
ArrayList<Integer> q = new ArrayList<Integer>();
q.add(startVertex);
int dist_int = 0;
while (!q.isEmpty())
{
int current = q.get(0);
q.remove(0);
dist_int++;
visited[startVertex] = true;
for (int j = 0; j < g.getEdgeMatrix()[current].length; j++)
{
if (startVertex == j)
distance[j] = 0;
if (g.getEdgeMatrix()[current][j] == 1 && !visited[j])
{
q.add(j);
distance[j] = dist_int;
visited[j] = true;
}
}
}
return distance;
}

其思想是通过邻接矩阵迭代，确定每个未访问的子对象，每次找到子对象时，将当前distint分配给距离数组中的相应索引。每次指定当前节点的所有子节点时，随着距离的增加，当前节点移动到第一个子节点并重复。

Answer 1

不使用dist_int来保存距离值，只需调用

distance[j]=distance[current]+1；