Статьи

Алгоритм недели: поиск по глубине графика

Январь 4, 2019

Вступление

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

DFS против BFS

Поиск в глубину и в ширину — это два основных способа исследования графа!

Оба метода могут быть полезны при решении разных задач.

обзор

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

ДФС объяснил

Алгоритм сначала идет вглубь, а затем возвращается ко всем непосещенным преемникам!

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

Итак, в основном у нас есть 3 шага:

  1. Подберите вершину, которая еще не посещена, и отметьте ее как посещенную;
  2. Перейти к первому не посещенному преемнику и отметить его как посещенное;
  3. Если все наследники вершины уже посещены или у нее нет наследников — вернитесь к ее родителю;

Код

Следующий код PHP реализует поиск в глубину. Ключевым моментом является рекурсия в методе deepFirst.

class Graph 
{
    protected $_len = 0;
    protected $_g = array();
    protected $_visited = array();
 
    public function __construct()
    {
        $this->_g = array(
            array(0, 1, 1, 0, 0, 0),
            array(1, 0, 0, 1, 0, 0),
            array(1, 0, 0, 1, 1, 1),
            array(0, 1, 1, 0, 1, 0),
            array(0, 0, 1, 1, 0, 1),
            array(0, 0, 1, 0, 1, 0),
        );
 
        $this->_len = count($this->_g);
 
        $this->_initVisited();
    }
 
    protected function _initVisited()
    {
        for ($i = 0; $i < $this->_len; $i++) {
            $this->_visited[$i] = 0;
        }
    }
 
    public function depthFirst($vertex)
    {
        $this->_visited[$vertex] = 1;
 
        echo $vertex . "\n";
 
        for ($i = 0; $i < $this->_len; $i++) {
            if ($this->_g[$vertex][$i] == 1 && !$this->_visited[$i]) {
                $this->depthFirst($i);
            }
        }
    }
}
 
$g = new Graph();
// 2 0 1 3 4 5
$g->depthFirst(2);

сложность

Используя матрицу смежности, нам нужно пространство n 2 для графа с n вершинами. Мы также используем дополнительный массив для отметки посещенных вершин, который требует дополнительного пространства n ! Таким образом, сложность пространства равна O (n 2 ).

Когда дело доходит до сложности времени, поскольку у нас есть рекурсия, и мы пытаемся посетить все вершины на каждом шаге, время наихудшего случая еще раз O (n 2 )!

заявка

Этот алгоритм обхода графа может быть очень полезен при решении некоторых конкретных задач, таких как поиск самых коротких / самых длинных путей в графе. Хотя BFS и DFS не являются единственными методами обхода графа, они считаются двумя основными алгоритмами такого рода. Это важно для решения задач на основе графов.

39
Share: