Использование алгоритма обхода графа

Я читаю материалы, связанные с графом в Структурах данных и алгоритмах в С++ 4e (автор Адам Дроздек). В его реализации Graph Breadth First Search псевдокод выглядит так:

BFS():
    for all vertices u
        num(u) = 0
    edges = null
    i = 1
    while there is a vertex v such that num(v) is 0
        num(v)++
        enqueue(v)
        while queue is not empty
            v = dequeue()
            if num(u) is 0
                num(u) = i++
                enqueue(u)
                attach edge(v,u) to edges
    output edges

По сути, в реализации графа мы уже храним набор всех вершин и набор всех ребер. В BFS алгоритм сначала перечисляет каждую вершину, не посещенную в этом наборе, чтобы пройти весь граф.

Мой вопрос таков: поскольку мы уже храним все вершины в наборе, мы можем перебирать набор для работы с определенной вершиной без использования алгоритма BFS. Зачем нужен алгоритм обхода графа и в чем его основное применение?


graph algorithm graph-traversal breadth-first-search
person Vschon    schedule 27.03.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

BFS и DFS можно использовать по-разному...
Чтобы дать вам представление о BFS:

  1. У вас есть граф, представляющий социальную сеть, и вы хотите предложить друзья для определенного пользователя. Затем вы делаете BFS. Чем ближе вершины (люди), тем выше место в списке предложений друзей. (Если количество пользователей велико, есть смысл остановиться на расстоянии 3 и не делать БФС на всем графе).

  2. Поиск решения в пространстве. Чрезвычайно полезно, когда пространство решений бесконечно. (см. Игровые деревья )

  3. Кратчайшие пути (если ребра имеют одинаковый вес и нет петель). Дейкстра адаптировал его для работы с переменными весами (см. алгоритм Дейкстры).

person Radu    schedule 27.03.2014
comment
Таким образом, цель алгоритма обхода заключается не в посещении некоторых вершин, а в изучении взаимосвязей между различными вершинами, верно? - person Vschon; 27.03.2014
comment
Можно так сказать. Однако, когда вы посещаете вершины, вы также можете вызвать некоторую функцию. Может быть я хочу назначить приоритет всем вершинам, чем они ближе, тем больше приоритет. Таким образом, я делаю BFS и вызываю функцию при каждом посещении узла. Эта функция назначает приоритет. Когда вы доберетесь до деревьев, вы увидите, что существует множество приложений для различных обходов дерева (предварительный заказ, порядок и пост-порядок). - person Radu; 27.03.2014

arrow_upward
1
arrow_downward

Например, обычно DFS неявно используется при рекурсивном обходе дерева.

person Codor    schedule 27.03.2014
comment
Да, я понимаю, что обход дерева в порядке и в прямом порядке аналогичен DFS. Я просто запутался, потому что на самом деле при реализации графов вершины и ребра хранятся в массиве, а не как узлы дерева, использующие указатели для связи друг с другом. В дереве нам нужен обход буквально для посещения каждого узла. Однако в графе, если нам нужно посетить какой-либо узел, цикл по вектору, содержащему вершины, кажется более простым. Я предполагаю, что алгоритм обхода графа больше используется для обнаружения отношений между вершинами, а не просто для посещения узлов. (?) - person Vschon; 27.03.2014
comment
Ну, вы также можете сделать это в дереве (вы сохраняете все адреса узлов в массиве, а затем у вас есть доступ к любому из них в постоянное время). Однако посещение узла — это не то же самое, что доступ к нему. Это больше вопрос того, как вы доберетесь туда. Вы, как программист, можете иметь доступ ко всем вершинам, но может случиться так, что вы не сможете посетить вершину, потому что она изолирована. - person Radu; 27.03.2014
comment
Я попробовал игрушечную программу, чтобы найти пути лабиринта, используя алгоритмы обхода графа, и теперь лучше понимаю ее использование. Большое спасибо. Верно, посещение сильно отличается от получения физического доступа к... - person Vschon; 28.03.2014