data-structures
Графические обходы

Вступление

Глубина первого поиска

Глубина Первый обход (или поиск) для графика похож на глубину первого обхода дерева. Единственный улов здесь, в отличие от деревьев, графики могут содержать циклы, поэтому мы снова можем вернуться к одному и тому же узлу. Чтобы избежать обработки узла более одного раза, мы используем булевский массив.

Ниже алгоритм представляет шаги для обхода графика с использованием DFS:

Алгоритм DFS (v);

Вход : вершина v в графе

Вывод : маркировка краев как «открытий» ребер и «опор»,

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

Поиск в ширину

Алгоритм BFS (G)

Входной граф G

Выводная маркировка ребер и разбиение вершин G

    for all u ∈ G.vertices()
        setLabel(u, UNEXPLORED)
    for all e ∈ G.edges()
    setLabel
    (e, UNEXPLORED)
    for all v ∈ G.vertices()
        if getLabel(v) = UNEXPLORED
            BFS(G, v)