Поиск кратчайших путей в графе

Обход в ширину одной компоненты связности графа

Обход в ширину

Обход в глубину

Глобальные данные

Решение задачи 4

Пример графа

#define NMAX 20 // макс. число вершин

int n; // число вершин графа

int visit [NMAX] = {0}; /* вектор посещенных вершин */

int g[NMAX][NMAX]; // м-ца смежности

// Главная функция (фрагмент)

int k =0; // счетчик компонент связности

int v; // очередная вершина

// обход всех компонент связности

for (v=0; v<n; v++)

if (visit[v] == 0) // вершина v не посещалась

{ round (v); /* обход графа, начиная с вершины v */

k++; }

Последовательность посещения вершин: 0, 1, 2, 6, 7, 8.

Подпрограмма обхода графа в глубину может быть рекурсивной и не рекурсивной (итеративной).

/* Итеративная функция обхода графа в глубину, начиная с вершины v */

void round (int v)

/* Глоб. данные:

g [NMAX][NMAX] – м-ца смежности,

n – число вершин,

visit [NMAX] – вектор посещ. вершин

*/

{ int st [NMAX]; // стек

int us = 0; // указатель стека

int i, j;// индексы строки и столбца м-цы смеж.

st[0] = v; visit [v ] = 1;

while (us >=0) // стек не пуст

{ i = st [us];

/* просмотр i-й строки м-цы смежности и

поиск 1-й непосещенной вершины,

смежной с i */

for (j=0; j<n; j++)

if (g[i][j] == 1 && visit[j] == 0)

{ us++; st[us]=j; visit[j] = 1; break; }

if (j == n) us--;

}

}

/* Рекурсивная функция обхода графа в глубину, начиная с вершины v */

void round (int v)

/* Глоб. данные:

g [NMAX][NMAX] – м-ца смежности,

n – число вершин,

visit [NMAX] – вектор посещ. вершин

*/

{ int w; // очередная вершина

visit [v] = 1;

for (w=0; w<n; w++)

if (g[v][w] == 1) // w смежна с v

if (visit [w] == 0 ) // w не посещалась

round(w);

}

Обход выполняется, начиная с заданной вершины, по уровням:

сначала посещается заданная вершина,

затем – вершины на расстоянии 1 от нее,

затем – вершины на расстоянии 2, 3 и т.д.

Расстояние между двумя вершинами – это длина (количество ребер) кратчайшего пути между вершинами.

Обход в ширину позволяет получить кратчайшие пути от заданной вершины до остальных.

Последовательность посещения вершин: 0, 1, 7, 8, 2, 6.

/* Функция обхода графа в ширину, начиная с вершины v */

void round (int v)

/* Глоб. данные:

g [NMAX][NMAX] – м-ца смежности,

n – число вершин,

visit [NMAX] – вектор посещ. вершин */

{ int och [NMAX]; /* очередь вершин на посещение */

int in, ik; // индексы начала и конца очереди

int w; // очередная вершина

in = ik = 0; // инициализация очереди

och [ik++] = v; visit [v ] = 1;

do

{ /* посещение вершины, первой в очереди, и удаление ее из очереди */

v = och [in++];

/* поиск непосещенных смежных с v вершин и добавление их в очередь */

for (w = 0; w<n; w++)

if (g[v][w] && visit[w] == 0)

{ och [ik++] = w; visit[w] = 1; }

}

while (in != ik); // очередь не пустая

}

В векторе visit можно хранить дерево кратчайших путей от каждой вершины до начальной (дуги направлены к корню). Для этого в элемент visit [w] следует записывать не 1, а вершину v, предшествующую вершине w в дереве кратчайших путей. До обхода вектор visit нужно заполнить -1, а не нулями.

Изменения в функции обхода round