обход в глубину поиска c++

Обход в глубину в C++: понимание алгоритмов и реализация

Обход в глубину (Depth-First Search, DFS) — этоpopular алгоритм graph theory, используемый для обхода графа или дерева в глубину, т. е. когда мы посещаем узел и затем переходим к его дочерним узлам. В этой статье мы рассмотрим понятие обхода в глубину в C++ и научимся реализовать его на практике.

Понятие обхода в глубину

Обход в глубину — это алгоритм graph traversal, который работает следующим образом:

1. Мы начнем с выбранного вершины графа или дерева.
2. Затем мы посетим все дочерние вершины выбранной вершины.
3. После того, как все дочерние вершины будут посещены, мы вернемся к предыдущей вершине и продолжим обход с другой дочерней вершиной.
4. Этот процесс повторяется, пока не будут посещены все вершины графа или дерева.

Алгоритм обхода в глубину в C++

Реализация обхода в глубину в C++ может быть выполнена с использованием рекурсии или итерации. В этой статье мы рассмотрим обе версии.

Рекурсивная версия

Рекурсивная версия обхода в глубину в C++ реализована с помощью функции dfs, которая принимает в качестве параметра текущую вершину и график.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// Структура вершины графа
struct Vertex {
 int value;
 vector<Vertex*> children;
};

// Функция обхода в глубину
void dfs(Vertex* vertex, vector<Vertex*>& visited) {
 // Маркируем посещенную вершину
 visited.push_back(vertex);

 // Посещаем дочерние вершины
 for (auto child : vertex->children) {
 if (find(visited.begin(), visited.end(), child) == visited.end()) {
 dfs(child, visited);
 }
 }
}

int main() {
 // Создаем граф
 Vertex* a = new Vertex{1};
 Vertex* b = new Vertex{2};
 Vertex* c = new Vertex{3};
 Vertex* d = new Vertex{4};
 Vertex* e = new Vertex{5};

 a->children.push_back(b);
 a->children.push_back(c);
 b->children.push_back(d);
 b->children.push_back(e);

 // Обходим граф в глубину
 vector<Vertex*> visited;
 dfs(a, visited);

 // Выводим посещенные вершины
 for (auto vertex : visited) {
 cout << vertex->value << " ";
 }

 return 0;
}

Итеративная версия

Итеративная версия обхода в глубину в C++ реализована с помощью цикла и стека.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// Структура вершины графа
struct Vertex {
 int value;
 vector<Vertex*> children;
};

// Функция обхода в глубину
void dfs(Vertex* vertex) {
 // Создаем стек для хранения вершин
 vector<Vertex*> stack;
 stack.push_back(vertex);

 // Обходим вершины в глубину
 while (!stack.empty()) {
 Vertex* current = stack.back();
 stack.pop_back();

 // Маркируем посещенную вершину
 cout << current->value << " ";

 // Посещаем дочерние вершины
 for (auto child : current->children) {
 stack.push_back(child);
 }
 }
}

int main() {
 // Создаем граф
 Vertex* a = new Vertex{1};
 Vertex* b = new Vertex{2};
 Vertex* c = new Vertex{3};
 Vertex* d = new Vertex{4};
 Vertex* e = new Vertex{5};

 a->children.push_back(b);
 a->children.push_back(c);
 b->children.push_back(d);
 b->children.push_back(e);

 // Обходим граф в глубину
 dfs(a);

 return 0;
}

Заключение

Обход в глубину — это важный алгоритм graph theory, используемый для обхода графа или дерева в глубину. В этой статье мы рассмотрели понятие обхода в глубину и научились реализовать его в C++ с помощью рекурсивной и итеративной версий. Мы также использовали структурные графики для демонстрации реализации алгоритма.