Как реализовать BFS в Java с помощью очереди (введение в алгоритмы HW)?

Question

Я пытаюсь реализовать алгоритм BFS в Java, используя следующий псевдокод:

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. БЕЛЫЙ = 2 не обнаружен

2. СЕРЫЙ = 3 обнаружен, но соседние соседи не все обнаружены

3. ЧЕРНЫЙ = 4 обнаружено, обнаружены все соседние соседи, нет необходимости возвращаться сюда

u.distance представляет расстояние от узла до узла-источника, а u.parent - родитель, который ведет обратно к узлу-источнику

Мой профессор сказал, что вместо создания объекта для каждого узла (u.color, u.d, u.pi) мы должны вместо этого использовать массив для каждого, чтобы хранить значения для каждого узла.

Он также предоставил нам скелетный код, который включает в себя матрицу смежности для тестирования.

-

В настоящее время я борюсь со строками 11 и 12 (я думаю). Я могу создать и инициализировать все массивы, а также очередь, но у меня возникают проблемы с реализацией функции queue.poll () или queue.remove () в строка 11 действовать так, как я ожидаю. Я также не знаю, правильно ли я создаю цикл for.

Я пытался использовать функции .poll () и .remove (), импортированные из LinkedList и Queue. Что СЛЕДУЕТ сделать, это удалить заголовок очереди и присвоить его значение переменной u, нет?

Когда я запускаю свой код, строка 17 добавляет к очереди, но заголовок очереди никогда не удаляется на следующей итерации, а строка 18 выполняется только на первой итерации (исходный узел).

Я не уверен, правильно ли я реализую строку 12 псевдокода, поскольку я использую обычный цикл for (int v; v

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: []

Answer 1

Неправильный цикл for внутри цикла while. Поскольку вам дано представление матрицы смежности, пусть 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]), являются представлением графа в списке смежности.