Основные применения метода поиска в глубину:
- Обнаружение компонента связанности в графе (связи в неориентированных графах)
- Проверка наличия циклов
- Топологическая сортировка
- Поиск путей
- Решение задач на генерацию лабиринтов, перестановок и комбинаций
- Решение задач на поиск оптимальной стратегии
Алгоритм:
1. Начинаем с определения начальной вершины.
2. Помещаем начальную вершину в стек и отмечфем ее как посещенную.
3. Пока стек не пуст, извлекаем вершину из стека.
4. Проверяем всех соседей текущей вершины. Если сосед еще не был посещен, помещаем его в стек и отмечаем как посещенный.
5. Повторяйте этот процесс, пока не будет достигнута конечная вершина или пока не будут исследованы все доступные ветви.
Временная сложность: O(V + E)
- V — количество вершин (узлов) в графе.
- E — количество рёбер (или связей) в графе.
Пространственная сложность: O(V)
Пример: Найти путь от начальной вершины до целевой вершины в графе.
package main
import (
"fmt"
)
type Graph struct {
Nodes map[string][]string
}
func NewGraph() *Graph {
return &Graph{
Nodes: make(map[string][]string),
}
}
func (g *Graph) AddEdge(src, dest string) {
g.Nodes[src] = append(g.Nodes[src], dest)
g.Nodes[dest] = append(g.Nodes[dest], src) // для ненаправленного графа
}
func DepthFirstSearch(graph *Graph, start, target string) []string {
visited := make(map[string]bool)
stack := []string{start}
visited[start] = true
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if node == target {
return stack // Возвращаем стек, содержащий путь от начальной до целевой вершины
}
for _, neighbor := range graph.Nodes[node] {
if !visited[neighbor] {
stack = append(stack, neighbor)
visited[neighbor] = true
}
}
}
return nil // Целевая вершина не достижима
}