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

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

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

Основные принципы обхода в глубину

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

1. Обход в глубину с пометкой (DFS с пометкой): в этом подходе каждая вершина графа помечается как "посещенная", чтобы избежать повторного посещения.
2. Обход в глубину без пометки (DFS без пометки): в этом подходе каждая вершина графа не помечается, что позволяет повторно посещать вершины.

Реализация обхода в глубину на C++

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

#include <iostream>
#include <vector>

using namespace std;

class Graph {
public:
 int V;
 vector<vector<int>> adj;

 Graph(int vertices) {
 V = vertices;
 adj.resize(V);
 }

 void addEdge(int u, int v) {
 adj[u].push_back(v);
 }

 void DFSUtil(int v, bool visited[]) {
 visited[v] = true;
 cout << v << " ";

 for (int i : adj[v]) {
 if (!visited[i])
 DFSUtil(i, visited);
 }
 }

 void DFS(int v) {
 bool* visited = new bool[V];
 for (int i = 0; i < V; i++)
 visited[i] = false;

 DFSUtil(v, visited);
 delete[] visited;
 }

 void printGraph() {
 for (int i = 0; i < V; i++) {
 cout << i << " -> ";
 for (int j : adj[i])
 cout << j << " ";
 cout << endl;
 }
 }
};

int main() {
 Graph g(6);
 g.addEdge(0, 1);
 g.addEdge(0, 2);
 g.addEdge(1, 3);
 g.addEdge(1, 4);
 g.addEdge(2, 5);

 g.printGraph();
 g.DFS(0);

 return 0;
}

В этом примере мы реализовали класс Graph, который представляет собой граф в виде матрицы смежности. Мы также реализовали функцию DFSUtil для рекурсивного обхода в глубину и функцию DFS для вызова DFSUtil и очистки памяти. В main функции мы создали экземпляр графа и добавили ребра, а затем вызвали функцию DFS для обхода в глубину графа.

Заключение

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