Что такое обход графов?
Обход графа — это процесс посещения всех вершин графа. Существует два основных метода: BFS (поиск в ширину) и DFS (поиск в глубину).
BFS (Breadth-First Search) — поиск в ширину
BFS исследует все вершины на текущем уровне, прежде чем перейти к следующему. Использует очередь (queue).
Пример кода BFS на C++
#include <iostream>
#include <vector>
#include <queue>
void bfs(const std::vector<std::vector<int>>& adj, int start) {
std::vector<bool> visited(adj.size(), false);
std::queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
std::cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}DFS (Depth-First Search) — поиск в глубину
DFS исследует путь до конца, прежде чем вернуться и выбрать другой. Использует стек (или рекурсию).
Пример кода DFS на C++
#include <iostream>
#include <vector>
void dfs(const std::vector<std::vector<int>>& adj, int v, std::vector<bool>& visited) {
visited[v] = true;
std::cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
dfs(adj, neighbor, visited);
}
}
}Когда что использовать?
- BFS — поиск кратчайшего пути в невзвешенном графе
- DFS — поиск компонент связности, топологическая сортировка, поиск циклов
Добавить комментарий