07.07.256. Применение обхода в ширину - justjune/AiSD2026 GitHub Wiki
Перед прочтением данного раздела рекомендуется ознакомиться с подразделом 07.06.251. Обход в ширину
Для графа с количеством ребер и вершин, равным m и n соответственно, алгоритм обхода графа в ширину исполняется за время O(m+n). Далее приведено несколько примеров использования обхода в ширину.
Граф является связным, если имеется путь между любыми двумя его вершинами.
Компонент связности неориентированного графа - это максимальный набор его связных вершин. Является своего рода "куском" графа, не связанным с остальными компонентами. Многие кажущиеся сложными проблемы могут быть сведены к поиску либо подсчету компонентов связности. Например, задачи вида "возможно ли достичь результат X, начав из стартового условия Y" сводятся к проверке графа возможных конфигураций.
Компоненты связности могут быть найдены с помощью обхода в ширину. Начиная от произвольной вершины, алгоритм получает все члены одного компонента связности. Повторяя обход с неоткрытых вершин, можно найти все компоненты связности данного графа. Алгоритм такого обхода представлен в листинге 7.14:
void connected_components(graph *g){ //граф взят по указателю во избежание ненужного копирования
int c; //номер компонента (будет выводится функцией)
int i; //счетчик (для перемещения между вершинами)
initialize_search(g); //инициализация вершин как неоткрытых (для обхода)(см. Скиена стр. 253)
c=0;
for(i = 1; i <= g->nvertices; i++){ //цикл повторяется, пока i меньше количества вершин в графе
if(!discovered(i)){ //поверяет, нетронута ли вершина
c=c+1;
printf("Component %d:", c); //выводит номер компонента связности
bfs(g, i); //выводит содержание компонента связности
printf("\n");
}
}
}
void process_vertex_early(int v){ //часть процедуры bfs
printf(" %d", v); //выводит номер вершины
}
void process_edge(int x, int y){ //часть процедуры bfs
}
void process_vertex_late(int v){ //часть процедуры bfs
}Задача раскраски вершин требует присвоения метки (или цвета) каждой вершине графа таким образом, чтобы любые две соединенные ребром вершины имели разные цвета - при том нужно использовать минимальное количество цветов. Эта задача часто возникает в приложениях календарного планирования (подробнее см. Скиена стр. 675).
Граф является двудольным (bipartite), если его вершины можно правильно раскрасить двумя цветами. Важность таких графов заключается в том, что они естественно образуются во многих приложениях. Например, граф взаимных заинтересованностей среди гетеросексуалов - здесь раскраска графа определяется полом.
Можно расширить алгоритм обхода в ширину таким образом, чтобы раскрашивать каждую новую вершину цветом, противоположным цвету её предшественника, а затем проверять, не связывает какое-либо ребро две вершины одного цвета - конфликтность будет означать, что граф не является двудольным, а её отсутствие - что была создана правильная двухцветная раскраска графа. Сия процедура приведена в листинге 7.15:
void twocolor(graph* g){ //граф взят по указателю во избежание ненужного копирования
int i; //счетчик
for(i = 1; i <= g->nvertices; i++){ //обход графа
color[i] = UNCOLORED; //объявление всех вершин как непокрашенных
} //цвета определяются через перечисление (enum)
bipartite = true; //сначала метод считает, что граф двудольный
initialize_search(g); //инициализация вершин как нетронутых
for(i = 1; i <= g->nvertices; i++){ //обход графа
if(!discovered[i]){ //проверка, нетронута ли вершина
color[i] = WHITE; //присваивание начального цвета
bfs(g, i); //покраска компонента связности
}
}
}
void process_edge(int x, int y){ //содержательная часть процедуры покраски
if(color[x] == color[y]){ //проверка на совпадение цветов
bipartite = false; //теперь метод считает, что граф не двудольный
printf("Warning: not bipartite, due to (%d, %d)\n", x, y); //сообщение о проблеме
}
color[y] = complement(color[x]);
}
int complement(int color){ //покраска соседа
if(color == WHITE){
return (BLACK);
}
if(color == BLACK){
return (WHITE);
}
return (UNCOLORED);
}