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

C++   21 марта 2015  Автор статьи: admin 
geekbrains.ru/

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


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

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

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

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

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

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

 


#include
#include

using namespace std;

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

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

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

 

Пример

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

демонстрация обхода в глубину

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

 

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

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/