在 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;
    }

想法是遍历邻接矩阵，确定每个未访问的 child，每次找到 child 时，将当前 dist_int 分配给距离中的相应索引大批。每次分配当前节点的所有 children 时，随着距离的增加，当前移动到第一个 child 并重复。

Answer 1

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

距离[j] = 距离[当前] + 1;

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

Creating an array of distances from a starting vertex in a graph in java

java

tree

graph

breadth-first-search

data-structures