Обход в ширину (реализация на C++)

C++   5 июля 2015  Автор статьи: admin 
geekbrains.ru/

Задан неориентированный граф, состоящий из N вершин и M ребер. Исходный граф задается списком ребер. Требуется произвести обход в ширину из всех еще не посещенных вершин графа в порядке увеличения их номера.
С целью осуществления обхода в ширину исходный граф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Булевский массив used служит для отметки о том, стала вершина v посещенной в процессе обхода в ширину или еще нет. При этом, если used[v] = true, то вершина v является посещенной, если used[v] = false, то нет. Процедура использует очередь q для хранения еще не посещенных вершин, достижимых из текущей обрабатываемой вершине в обходе.


vector *adj; //список смежности орграфа
//массив для хранения информации о пройденных и не пройденных вершинах
vector used;
queue q;//очередь для добавления вершин при обходе в ширину

В качестве списка смежности для представления орграфа и транспонированного орграфа на языке C++ удобно использовать массив, каждый элемент которого является структурой данных vector<int>.
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: N (1 \le N \le 10^5) – количество вершин в графе и M (1 \le M \le 10^6) – количество ребер графа соответственно. Каждая из следующих M строк содержит описание ребра графа – два целых числа из диапазона от 1 до N – номера концов ребра.

Выходные данные

В строке выходного файла показаны вершины графа в порядке обхода в ширину, начиная с первой вершины.


#include
#include
#include
#include
#include

using namespace std;

int n; //количество вершин в орграфе
int m; //количество дуг в орграфе
vector *adj; //список смежности орграфа
//массив для хранения информации о пройденных и не пройденных вершинах
vector used;
queue q; //очередь для добавления вершин при обходе в ширину

//процедура обхода в ширину
void bfs(int v) {
if (used[v]) { //если вершина является пройденной, то не производим из нее вызов процедуры
return;
}
q.push(v); //начинаем обход из вершины v
used[v] = true; //помечаем вершину как пройденную
while (!q.empty()) {
v = q.front(); //извлекаем вершину из очереди
q.pop();
printf("%d ", (v + 1));
//запускаем обход из всех вершин, смежных с вершиной v
for (int i = 0; i < adj[v].size(); ++i) { int w = adj[v][i]; //если вершина уже была посещена, то пропускаем ее if (used[w]) { continue; } q.push(w); //добавляем вершину в очередь обхода used[w] = true; //помечаем вершину как пройденную } } } //процедура считывания данных с консоли void readData() { scanf("%d %d", &n, &m); //считываем количество вершин и количество ребер графа adj = new vector[n];

//считываем граф, заданный списком ребер
for (int i = 0; i < m; ++i) { int v, w; scanf("%d %d", &v, &w); v--; w--; adj[v].push_back(w); } //помечаем все вершины, как непосещенные used.resize(n, false); } void run() { readData(); for (int v = 0; v < n; ++v) { bfs(v); } //освобождаем память for (int i = 0; i < n; ++i) { adj[i].clear(); } delete[] adj; used.clear(); } int main() { run(); return 0; }

 

Пример

Рассмотрим работу алгоритма на графе G, изображенном на рисунке.

pic5

Начальной вершина обхода в ширину будет являться вершина с номером 1. После завершения работы алгоритма будет построено дерево поиска в ширину G_\pi. Ребра исходного графа G, которые входят в дерево поиска в ширину G_\pi изображены на рисунке жирной линией.

Входные данные
8 9
1 2
1 4
2 3
3 4
3 5
3 6
5 7
6 7
7 8
Выходные данные
1 2 4 3 5 6 7 8

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/