Основные применения метода поиска в ширину:
- Поиск кратчайшего пути в невзвешенных графах
- Проверка связности графа
- Поиск в лабиринтах и задачах на графы
- Определение уровня узлов в деревьях и графах
- Поиск компонент связности
- Сериализация и десериализация деревьев и графов
Алгоритм:
1. Начнаем с определения начальной вершины.
2. Помещаем начальную вершину в очередь и отмечаем ее как посещенную.
3. Пока очередь не пуста, извлекаем вершину из очереди и проверяем все ее непосещенные соседние вершины.
4. Добавляем каждую непосещенную соседнюю вершину в очередь и отмечаем ее как посещенную.
5. Повторяем этот процесс до тех пор, пока не будут посещены все вершины графа или не будет найден целевой элемент.
По времени и памяти у нас O(V + E), где (для временной сложности):
- V — количество вершин (узлов) в графе.
- E — количество рёбер (или связей) в графе
Пример задачи: Найти кратчайший путь от начальной вершины до целевой вершины в графе.
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 BreadthFirstSearch(graph *Graph, start, target string) []string {
visited := make(map[string]bool)
queue := make([]string, 0)
parents := make(map[string]string)
queue = append(queue, start)
visited[start] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node == target {
path := []string{node}
for node != start {
node = parents[node]
path = append([]string{node}, path...)
}
return path
}
for _, neighbor := range graph.Nodes[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
parents[neighbor] = node
}
}
}
return nil // Целевая вершина не достижима
}