如何使用队列在Java中实现BFS(算法硬件简介)?

问题描述 投票:1回答:1

我正在尝试使用以下伪代码在Java中实现BFS算法:

1.   for each vertex u ∈ G.V - {s}  // for each vertex except for the source
2.       u.color = WHITE            // (line 1 cont) in the graph
3.       u.distance = ∞
4.       u.parent = NIL
5.   source.color = GRAY
6.   source.distance = 0
7.   source.parent = NIL
8.   Q = Ø
9.   Enqueue (Q, source)
10.  while Q != Ø
11.      u = Dequeue(Q)
12.      for each v ∈ G.Adj[u]              // for each adjacent vertext
13.            if v.color == WHITE
14.                  v.color = GRAY         
15.                  v.distance = u.distance + 1
16.                  v.parent = u
17.                  Enqueue(Q, v)
18.      u.color = BLACK

颜色代表每次访问该节点时:

  1. WHITE = 2未被发现
  2. 发现了灰色= 3,但其相邻的邻居并未全部被发现
  3. 发现BLACK = 4,发现所有邻近邻居,无需返回此处

u.distance表示从节点到源节点的距离,u.parent是返回源节点的父节点

我的教授说,不是为每个节点(u.color,u.d,u.pi)创建一个对象,我们应该为每个节点使用一个数组来存储每个节点的值。

他还向我们提供了骨架代码,其中包含一个邻接矩阵来测试它。

--

我目前正在努力使用第11和第12行(我认为)。我能够创建和初始化所有数组以及队列,但是我在第11行中实现queue.poll()或queue.remove()函数时遇到了问题。我也不知道我是否正确创建了for循环。

我尝试使用从LinkedList和Queue导入的.poll()和.remove()函数。我们应该做的是删除队列的头部并将其值赋给变量u,不是吗?

当我运行我的代码时,第17行添加到队列中,但是队列的头部在下一次迭代中永远不会被删除,而第18行只在第一次迭代(源节点)上执行。

我不确定我是否正在实现伪代码的第12行,因为我正在使用正常的for-loop(int v; v <n; v ++)但是我看到其他示例做类似于:for(Integer v: graph.adj [u]),但我不知道如何正确实现它或找到.adj()方法的包。

while (!q.isEmpty())
        {
            u = q.poll();                           // sets value of u... to most recent item removed from queue??
            for (v = 0; v < colors.length; v++)                 
            {
                if (colors[v] == WHITE)
                {
                    colors[v] = GRAY;               // Sets color of VISITED Node to 

                    dist[v] = dist[u] + 1;      // sets distance at index v to value of the index most recently removed from queue + 1                  
                    parent[v] = u;                  // sets  parent of index v to most recently removed item from queue                 
                    q.add(v);                       // adds node V to the queue
                }
            }
            colors[u] = BLACK;                  // sets color of node to black (node visited + adjacent nodes visited)

        }

        return dist;                                // returns distance array

    }

我尝试打印出阵列,看看for循环是如何运作的。使用此代码,我可以看到头部没有从队列中删除并在第一次迭代后分配给值u。

这是它正在测试的矩阵:

        int n = 8;
        int[][] A = 
            {{0, 1, 0, 0, 1, 0, 0, 0},
            {1, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 0, 1, 0, 1, 1, 0},
            {0, 0, 1, 0, 0, 0, 1, 1},
            {1, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 0, 0, 0, 1, 0},
            {0, 0, 1, 1, 0, 1, 0, 1},
            {0, 0, 0, 1, 0, 0, 1, 0}};

我的结果:

COLORS: [2, 3, 2, 2, 2, 2, 2, 2]
DISTANCE: [2147483647, 0, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
PARENT: [0, 0, 0, 0, 0, 0, 0, 0]

COLORS: [3, 3, 2, 2, 2, 2, 2, 2]
dist[u] = 0
DISTANCE: [1, 0, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
PARENT: [1, 0, 0, 0, 0, 0, 0, 0]
QUEUE: []

COLORS: [3, 3, 3, 2, 2, 2, 2, 2]
dist[u] = 0
DISTANCE: [1, 0, 1, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
PARENT: [1, 0, 1, 0, 0, 0, 0, 0]
QUEUE: [0]

COLORS: [3, 3, 3, 3, 2, 2, 2, 2]
dist[u] = 0
DISTANCE: [1, 0, 1, 1, 2147483647, 2147483647, 2147483647, 2147483647]
PARENT: [1, 0, 1, 1, 0, 0, 0, 0]
QUEUE: [0, 2]

COLORS: [3, 3, 3, 3, 3, 2, 2, 2]
dist[u] = 0
DISTANCE: [1, 0, 1, 1, 1, 2147483647, 2147483647, 2147483647]
PARENT: [1, 0, 1, 1, 1, 0, 0, 0]
QUEUE: [0, 2, 3]

COLORS: [3, 3, 3, 3, 3, 3, 2, 2]
dist[u] = 0
DISTANCE: [1, 0, 1, 1, 1, 1, 2147483647, 2147483647]
PARENT: [1, 0, 1, 1, 1, 1, 0, 0]
QUEUE: [0, 2, 3, 4]

COLORS: [3, 3, 3, 3, 3, 3, 3, 2]
dist[u] = 0
DISTANCE: [1, 0, 1, 1, 1, 1, 1, 2147483647]
PARENT: [1, 0, 1, 1, 1, 1, 1, 0]
QUEUE: [0, 2, 3, 4, 5]

COLORS: [3, 3, 3, 3, 3, 3, 3, 3]
dist[u] = 0
DISTANCE: [1, 0, 1, 1, 1, 1, 1, 1]
PARENT: [1, 0, 1, 1, 1, 1, 1, 1]
QUEUE: [0, 2, 3, 4, 5, 6]

我希望它最终会像下面这样:

COLORS: [4, 4, 4, 4, 4, 4, 4, 4]
dist[u] = most recently removed from queue (not 0)
DISTANCE: [1, 0, 2, 3, 2, 1, 2, 3]
QUEUE: []
java eclipse algorithm data-structures breadth-first-search
1个回答
0
投票

while循环中的for循环不正确。由于给出了邻接矩阵表示,让Graph [] []为矩阵,您具有以下属性。

Graph [i] [j] == 0,顶点i和j之间没有边缘; Graph [i] [j] == 1,顶点i和j之间有一条边;

假设你有n个顶点,for循环应该是:

for(int i = 0; i < n; i++) {
    if(Graph[u][i] == 1) {
        //put in the color/distance updates here
    }
}

您提到的其他示例(Integer v:graph.adj [u])是图的邻接列表表示。

© www.soinside.com 2019 - 2024. All rights reserved.