Сложность реализации BFS для обхода графа

У меня есть матрица смежности adj, которая определена ниже:

0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 
1 0 0 0 1 0 1 0 0 
0 0 0 1 0 1 0 0 0 
0 0 1 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0

Я ломаю голову над разработкой алгоритма BFS для обхода графа с учетом начальной и конечной позиции.

Моя лучшая попытка дает серию ходов, но не самую короткую.

boolean[] pass = new boolean[9]; //if a move has been done, don't redo it
int s = 0; //starting position
int e = 2; //ending position
int[][] matrix; //the adjacency matrix previous defined

public List<Integer> BFS(int[][] matrix, int s) {
    List<Integer> paths = new LinkedList();
    List<Integer> shortest = new LinkedList();
    pass[s] = true; //starting position has been indexed
    paths.add(0,s); //insert part of path to front of list
    while (paths.isEmpty() == false) {
        int element = paths.get(0); //peek at first element
        shortest.add(element); //add it to shortest path
        int node = paths.remove(0); //remove from path
        if (element == e) { //if we've reached the end
            return shortest; //hopefully found shortest path
        } else {
            for (int i = 0; i < 9; i++) {
                //if adjacent element hasn't been indexed
                if (pass[i] == false && matrix[node][i] == 1) {
                    pass[i] = true;
                    paths.add(0,i);
                }
            }
        }
    }
    return null;
}

Печать возвращенного списка дает:

[0, 3, 6, 4, 5, 8, 2]

Когда фактический результат должен быть:

[0, 3, 4, 5, 2]

Мне кажется, что путь, по которому он идет, выглядит примерно так:

[0, 3, 6, backtrack to 3, 4, 5, 8, backtrack to 5, 2]

Что не так с моим алгоритмом? Как найти кратчайший путь, зная начальную и конечную точки?

Вот пример IDEone для иллюстрации.


java search algorithm graph-theory adjacency-matrix
person gator    schedule 07.07.2015    source источник
comment
Ваш обход BFS в порядке, но вы неправильно извлекаете кратчайший путь. Вы добавляете каждый узел, который обрабатываете, к кратчайшему пути.   -  person mastov    schedule 07.07.2015

Ответы (2)


arrow_upward
1
arrow_downward

Вы неправильно извлекаете кратчайший путь. Вы добавляете каждый узел, который обрабатываете, к кратчайшему пути.

Если вы хотите использовать BFS для поиска кратчайшего пути, вы должны отслеживать кратчайший путь к каждому промежуточному узлу, сохраняя «обратные ребра», и только в конце вы можете собрать их вместе, чтобы найти кратчайший путь.

Для каждого узла, который вы добавляете в очередь, сохраните узел, который привел вас к этому узлу, как «задний край»:

if (pass[i] == false && matrix[node][i] == 1) {
    pass[i] = true;
    paths.add(0,i);

    // Add this:
    back[i] = node;
}

Затем, когда ваш обход завершен, вы можете использовать эти ссылки, чтобы найти полный путь, двигаясь по этим «задним краям» назад от конечного узла. Это приведет вас (назад) к начальному узлу по кратчайшему пути:

int node = e;
while (node != s) {
    shortest.add(0, node);
    node = back[node];
}
shortest.add(0, s);

Обновление:

Благодаря вашему комментарию я только что понял, что в вашем коде есть дополнительная проблема. Вы добавляете новые узлы в начало списка и также обрабатываете их спереди. Таким образом, у вас есть фактически стек, а не очередь. Это делает ваш алгоритм эффективным поиском в глубину (DFS) вместо поиска в ширину (BFS). DFS даст вам правильный путь от s до e, но не обязательно самый короткий.

Чтобы рассматривать ваш список paths (который лучше назвать queue, кстати) как очередь, а не стек, вы должны читать и писать с противоположных концов, например. добавить на задний план (вместо переднего) изменить строку добавления списка

paths.add(0, i);

to

paths.add(i);
person mastov    schedule 07.07.2015
comment
Я следую, но использование этого метода дает результат [3, 4, 5, 2, 3, 4, 5, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0]. - person gator; 07.07.2015
comment
@gator: Я думаю, вы смешали старый список shortest с новым. - person mastov; 07.07.2015
comment
@gator: см. goo.gl/IydTAe. Вы можете выполнить его онлайн и убедиться, что он возвращает правильный результат [0, 3, 4, 5, 2]. - person mastov; 07.07.2015
comment
это работает для данной матрицы смежности, но не для всех матриц смежности. См. ideone.com/fork/PTVtNj напечатанный список равен [0, 6, 7, 13, 19, 25, 26, 27, 28, 29, 23, 17, 11, 5] (14 элементов), если кратчайший путь [0, 6, 7, 13, 14, 15, 16, 17, 11, 5] (11 элементов). - person gator; 07.07.2015
comment
@gator: понятно. Только что нашел другую проблему с вашим кодом и обновил ответ. - person mastov; 07.07.2015
comment
Ура, вы очень помогли! Каждый ресурс, за которым я следил, использовал расчеты расстояний, цвета или что-то еще, чтобы определить самый мелкий путь, который мне трудно расшифровать, но вы направили меня в правильном направлении. - person gator; 07.07.2015

arrow_upward
2
arrow_downward

Массив shortest в вашей реализации — это не то, что вы думаете. Это просто список всех найденных вершин, а не кратчайший путь, поскольку (как вы заметили) BFS иногда приходится следовать путям, которые не ведут к целевой вершине.

Что вам нужно сделать, так это для каждой вершины v сохранить ее «родителя» — вершину, из которой вы попали в v:

       if (pass[i] == false && matrix[node][i] == 1) {
            pass[i] = true;
            parent[i] = node;
            paths.add(0,i);
       }

Затем, после основного цикла BFS, вы переходите от целевой вершины обратно к исходной, используя ссылки, хранящиеся в parent:

// pseudocode
cur = e;
while cur != s
    answer.add_at_end(cur)
    cur = parent[cur];
person Petr    schedule 07.07.2015