我正在尝试使用以下伪代码在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
颜色代表每次访问该节点时:
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: []
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])是图的邻接列表表示。