7.6.251 Обход в ширину - justjune/AiSD2026 GitHub Wiki
Главная идея: пометить каждую вершину при первом ее посещении и помнить о тех частях графа, которые не исследованы полностью.
* неоткрытая(undiscovered) — первоначальное состояние, вершину не тронули
* открытая(discovered) — вершина была обнаружена, но мы еще не проверили все ее ребра
* обработанная(processed) — все ребра данной вершины были посещены
- Если какие-либо ребра идут к неоткрытой вершине, то вершина помечается открытой и добавляется список для дальнейшей обработки.
- Ребра, идущие к обработанной вершине, игнорируются, так как уже не дадут новой информации о графе.
- Неориентированное ребро рассматривается дважды от каждой его вершины, ориентированное ребро — только от источника один раз.
При обходе в ширину неориентированного (это важно) графа каждому ребру присваивается направление от открывающей вершины к открываемой. Открывающая вершина считается родителем(предшественником), а открываемая — потомком. Поскольку каждая вершина(кроме корневой) имеет только одного родителя — можно составить дерево вершин. Оно поможет определить кратчайший путь от корня(корневой вершины) к другим вершинам.
BFS(G,s)
Инициализируем каждую вершину u ∈ V [G] следующим образом:
state[u] = "undiscovered"
p[u] = nil, т. е. в начале дерева вершины-родители отсутствуют
state[s] = "discovered"
p[s] = nil
Q = {s}
while Q ≠ ∅ do
u = dequeue[Q]
обрабатываем вершину u, если требуется
для каждой вершины v, смежной с u
обрабатываем ребро (u, v), если требуется
if state[v] = "undiscovered" then
state[v] = "discovered"
p[v] = u
enqueue[Q,v]
state[u] = "processed"
//adj - матрица смежности(можно список)
//V - вершины V[G]
void BFS(int** adj, int V, int s) {
//Инициализируем каждую вершину u из V следующим образом:
string* state = new string[V+1];
int* p = new int[V+1];//нумерация в c++ с нуля, а у нас 0 - отсутствие родителя(nil)
for (int u = 1; u < V+1; u++) {
state[u] = "undiscovered";
p[u] = 0;
}
state[s] = "discovered";
p[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int v = 1; v < V+1; v++) {
if (adj[u][v] == 1) { //если v и u смежные
if (state[v] == "undiscovered") {
state[v] = "discovered";
p[v] = u;
Q.push(v);
}
}
}
state[u] = "processed";
}
}
[ Скиена 2022 с. 251]