Как BFS находится в списке матриц смежности O (m + n)? - PullRequest
Новая
       42

Как BFS находится в списке матриц смежности O (m + n)?

2 голосов
/ 22 декабря 2011

Я пытаюсь выяснить, как BFS - это O (m + n), где n - количество вершин, а m - количество ребер.

Алгоритм: 

public void bfs()
{
    //BFS uses Queue data structure
    Queue q=new LinkedList();
    q.add(this.rootNode);
    printNode(this.rootNode);
    rootNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();
        Node child=null;
        while((child=getUnvisitedChildNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
//

В списке смежности мы сохраняем вершины в массиве / хэш-таблице и связанный список ребер, которые каждая вершина образует с другими вершинами.

Мой главный вопрос заключается в следующем: как мы реализуем получение не посещенного дочернего узла? Ясно, что вы помечаете узлы как посещенные, но при обходе вы проходите через все связанные списки, поэтому вы учитываете каждое ребро дважды, поэтому сложность составляет O (2m + n), верно? Это просто округляется до O (m + n)?

Кроме того, можем ли мы использовать аналогичную стратегию для матрицы смежности? Если мне дана матрица размером n x n, и я хочу знать, существует ли конкретный элемент, могу ли я сделать BFS, чтобы это выяснить?

Спасибо.

1 Ответ

3 голосов
/ 22 декабря 2011

O-нотация «уменьшает» мультипликативные константы до 1, поэтому O (2m + n) уменьшается до O (m + n).

...