Продолжение темы 6. Алгоритмы обхода графов с использованием структур типа стеки, очереди.
Лекция 25 АЛГОРИТМЫ ОБХОДА ГРАФА
25.1 Алгоритмы обхода графа
Существует целый класс транспортных задач, в которых необходимо «просмотреть» все вершины графа. При этом каждая вершина должна «просматриваться» точно один раз. Такой «просмотр» графа обычно называют его обходом.
В теории графов известны два основных алгоритма обхода вершин графа – обход графа в «глубину» и обход графа в «ширину».
В первом случае в алгоритме применяется структура типа стек, а во втором случае – структура типа очередь. С точки зрения «алгоритмизации» первый случай представляет больший интерес, поскольку в нем реализован алгоритм «с возвращением», который часто используется при анализе сложных структур. Рассмотрим работу алгоритма обхода графа в глубину на примере графа средней сложности изображенного на рисунке 25.1:
Рисунок 25.1 – Граф средней сложности.
Алгоритм обхода графа в «глубину» использует понятие «новых» вершин графа то есть еще не «просмотренных» вершин. Рассмотрим его работу:
– все вершины графа объявляются «новыми» (в алгоритме Дейкстры использован термин «временные»). Начинаем просмотр графа с некоторой исходной вершины, например, с вершины 0. Просматриваем ее (печатаем номер ее вершины) и помечаем как «неновая»;
– из всего списка смежных новых вершин, подключенных к исходной вершине, выбираем вершину с наименьшим номером. В нашем примере это вершина 1;
– объявляем ее исходной, просматриваем ее и помечаем как «неновая»;
– если у просмотренной вершины нет «новых» смежных вершин, то возвращаемся к вершине, из которой мы попали в данную вершину (работа стека);
– процесс повторяется, пока существуют «новые» вершины.
Применив рассмотренный алгоритм к графу изображенному на рисунке
13.1, получим следующую последовательность просмотра его вершин:
0 – 1 – 3 – 4 – 5 – 7 – 8 – 6 – 2 – 12 – 11 – 9 – 10.
Алгоритм обхода графа в «ширину» так же предполагает использование понятия «новых» вершин графа. Рассмотрим его работу:
– все вершины графа объявляются «новыми». Начинаем просмотр графа с некоторой исходной вершины, например, с вершины 0. Просматриваем ее (печатаем номер ее вершины) и помечаем как «неновая»;
– весь список смежных новых вершин, подключенных к просмотренной вершине, в возрастающем порядке вершин помещаем в очередь: 1 – 3 – 11;
– выбираем вершину из очереди (в нашем примере это вершина 1), просматриваем ее, помечаем как «неновая» и весь список смежных новых вершин, подключенных к просмотренной, в возрастающем порядке вершин помещаем в очередь: 3 – 11;
– процесс повторяется пока, в очереди есть вершины графа.
Последовательность просмотренных вершин графа:
0 – 1 – 3 – 11 – 4 – 6 – 9 – 10 – 5 – 8 – 12 – 2 – 7.
25.2 Реализация алгоритма обхода графа в глубину
Программную реализацию алгоритма обхода графа в глубину рассмотрим на примере графа изображенного на рисунке 25.1.
Исходный код программы имеет следующий вид:
using System;
using System. Collections;
using System. Linq;
using System. Text;
namespace ConsoleApplication1
{
class Program
{
public static int i, j, k, n, kol;
static void vkl(Stack vst, int n)
{
vst. Push(n);
}
static void iskl(Stack vst)
{
if (vst == null) Console. WriteLine("Стек пуст !");
else
n = (int)vst. Pop();
}
public static void Main()
{
Stack vstek = new Stack();
//int i, j, k, n;
bool[] nov = new bool[13];
int[,] p = new int[13, 13];
int[,] a = new int[13, 13]
{{ 0, 1,1000, 1,1000,1000,1000,1000,1000,1000,1000, 1,1000},
{ 1, 0,1000, 1,1000,1000,1000,1000,1000,1000,1000,1000,1000},
{1000,1000, 0,1000,1000,1000, 1,1000,1000,1000,1000,1000,1000},
{ 1, 1,1000, 0, 1,1000, 1,1000,1000,1000,1000, 1,1000},
{1000,1000,1000, 1, 0, 1, 1,1000, 1,1000,1000,1000, 1},
{1000,1000,1000,1000, 1, 0,1000, 1, 1,1000,1000,1000,1000},
{1000,1000, 1, 1, 1,1000, 0,1000,1000,1000,1000,1000,1000},
{1000,1000,1000,1000,1000, 1,1000, 0, 1,1000,1000,1000,1000},
{1000,1000,1000,1000, 1, 1,1000, 1, 0,1000,1000,1000,1000},
{1000,1000,1000,1000,1000,1000,1000,1000,1000, 0, 1, 1,1000},
{1000,1000,1000,1000,1000,1000,1000,1000,1000, 1, 0, 1,1000},
{ 1,1000,1000, 1,1000,1000,1000,1000,1000, 1, 1, 0,1000},
{1000,1000,1000,1000, 1,1000,1000,1000,1000,1000,1000,1000, 0},};
for (i = 0; i < 13; i++)
{
p[i,0] = i;k=1;
for (j = 0; j < 13; j++)
if ((a[i, j] != 1000) && (a[i, j] != 0))
{
p[i, k]=j;
k++;
}
p[i, k]=1000;
}
for (i = 0; i < 13; i++)
{
k = 0;
while (p[i, k] != 1000)
{
Console. Write(" {0}", p[i, k]);
k++;
}
Console. WriteLine();
}
// Начало обхода графа
bool b;
// задание начальных условий
for (i = 0; i < 13; i++) nov[i] = true;
//vs = null;
vkl(vstek, p[0,0]);
kol = 1;
Console. Write(" {0}", p[0, 0]);
nov[0] = false;
// цикл обхода графа в глубину
while (kol!= 0)
{
i = (int)vstek. Peek();
if (p[i,0] == 1000) b = false;
else b = !nov[p[i,0]];
// поиск новой вершины графа
k = 0;
while (b == true)
{
k++;
if (p[i, k] == 1000) b = false;
else
{
b = !nov[p[i, k]];
if (nov[p[i, k]]) { vkl(vstek, p[i, k]); kol++; }
}
}
if (p[i, k] != 1000)
// если найдена новая вершина
{
i = p[i, k];
Console. Write(" {0}", i);
nov[i] = false;
}
else
// новой вершины в данном списке нет, необходим возврат
// к предыдущей вершине
{
iskl(vstek); i = n; kol--;
}
}
Console. WriteLine();
Console. WriteLine("Для продолжения нажмите клавишу Enter");
Console. ReadLine();
}
}
}
Работа программы:
0 1 3 11
1 0 3
2 6
3 0 1 4 6 11
4 3 5 6 8 12
5 4 7 8
6 2 3 4
7 5 8
8 4 5 7
9 10 11
10 9 11
11 0 3 9 10
12 4
0 1 3 4 5 7 8 6 2 12 11 9 10
Для продолжения нажмите клавишу Enter
В начале программы формируется матрица p[13,13], в которую записываются списки всех смежных вершин графа. Для контроля содержимое этих списков выводится на экран монитора.
В программе использован стек, в который сначала записывается заголовок списка начальной вершины графа. Во время работы цикла обхода графа в глубину, в стек записываются заголовки списков наименьших новых смежных вершин графа, которые выбираются из списка, заголовок которого находится в вершине стека. Если новой смежной вершины в этом списке нет, то заголовок соответствующего списка удаляется из стека и вершина стека переходит на предыдущий список.
Работа алгоритма заканчивается, когда в стеке нет заголовков списков смежных вершин графа.
25.3 Работа стека в алгоритме обхода графа в глубину
Важной частью алгоритма обхода графа в глубину является работа стека. Поэтому начальный фрагмент работы стека при обходе графа в глубину рассмотрим на рисунке 25.2.
Рисунок 25.2 – Работа стека при обходе графа в глубину
На рисунке 25.2 видно, что из первого списка смежных вершин графа выбирается вершина 1, из второго списка – вершина 3, из третьего списка – вершина 4 и т. д. По мере заполнения стека значения выбранных вершин меняется с true (t) на false (f). После просмотра списка вершины 8, из стека будут удалены вершины 8, 7 и 5 – в них нет новых вершин. В списке вершины 4 есть новая вершина под номером 6, заголовок списка которой и будет включен в стек и т. д.
25.4 Вопросы для проверки
25.4.1 Как в алгоритмах обхода графа в ширину фиксируется, что просмотренная вершина не новая?
A) С помощью специального логического массива.
B) С помощью специального массива смежных вершин графа.
C) С помощью записи в очередь на место просмотренной вершины значения нуля.
D) Перемещением указателя по массиву смежных вершин.
E) Перемещением указателя по очереди.
25.4.2 Условие окончания алгоритма обхода графа в глубину?
A) Нет новых вершин графа.
B) Все списки смежных вершин графа просмотрены.
C) Количество элементов в стеке равно нулю.
D) Вершина стека равна нулю и нет новых вершин графа.
E) Нет новых вершин графа и списки смежных вершин графа просмотрены.
25.4.3 Как называется алгоритм обхода графа, использующий для своей работы очередь?
25.4.4 Что хранится в стеке алгоритма обхода графа, использующий для своей работы стек?
25.4.5 Что хранится в очереди алгоритма обхода графа, использующего для своей работы очередь?
Продолжение темы 6. Алгоритмы обхода графов с использованием структур типа стеки, очереди.
Лекция 26 АЛГОРИТМ ПОИСКА ВСЕХ МАРШРУТОВ МЕЖДУ ДВУМЯ ЗАДАННЫМИ ВЕРШИНАМИ ГРАФА
26.1 Алгоритм поиска всех маршрутов между двумя заданными вершинами графа
Алгоритм нахождения всех маршрутов между двумя заданными вершинами графа основан на алгоритме обхода графа в глубину. Первое отличие заключается в использовании стека для запоминания не только номеров вершин графа, но и номера списка смежных вершин и позиции вершины в списке.
Второе отличие заключается в «возврате» вершинам графа «новых» значений. Т. е. если список вершины графа исчерпан – нет «новых» вершин, то вершина удаляется из стека и ей возвращается значение «новой», чтобы ее можно было бы использовать в других маршрутах.
Задача 26.1 Для графа, изображенного на рисунке 26.1 и представленного матрицей смежности (см. таблицу 26.1), разработать программу, позволяющую найти все маршруты между двумя вершинами, заданными в режиме диалога с ЭВМ
 |
Рисунок 26.1 – Неориентированный граф
Матрица смежности графа, изображенного на рисунке 26.1 представлена в таблице 26.1.
Таблица 26.1 – Матрица смежности графа рисунка 26.1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
0 | 0 | 3 | 1000 | 4 | 1000 | 1000 | 1000 | 1000 | 1000 |
1 | 3 | 0 | 4 | 1000 | 1000 | 1000 | 1000 | 7 | 1000 |
2 | 1000 | 4 | 0 | 5 | 2 | 4 | 4 | 6 | 9 |
3 | 4 | 1000 | 5 | 0 | 6 | 1000 | 1000 | 1000 | 1000 |
4 | 1000 | 1000 | 2 | 6 | 0 | 5 | 1000 | 1000 | 1000 |
5 | 1000 | 1000 | 4 | 1000 | 5 | 0 | 3 | 1000 | 4 |
6 | 1000 | 1000 | 4 | 1000 | 1000 | 3 | 0 | 1000 | 4 |
7 | 1000 | 7 | 6 | 1000 | 1000 | 1000 | 1000 | 0 | 8 |
8 | 1000 | 1000 | 9 | 1000 | 1000 | 4 | 4 | 8 | 0 |
Исходный код программы имеет следующий вид:
using System;
using System. Collections;
using System. Linq;
using System. Text;
namespace ConsoleApplication1
{
class Program
{
public static int i, j, k, kol;
public struct uzel
{
public int nom;
public int ki;
public int kj;
};
public static uzel n = new uzel();
static void vkl(Stack vst, uzel n)
{
vst. Push(n);
}
static void iskl(Stack vst)
{
if (vst == null) Console. WriteLine("Стек пуст !");
else n = (uzel)vst. Pop();
}
public static void Main()
{
Stack vstek = new Stack();
string buf;
int beg, en, x, i1,i2;
uzel y1 = new uzel();
bool[] nov = new bool[10];
int[,] p = new int[9, 9];
int[] m = new int[10];
//Матрица смежности графа
int[,] a = new int[9, 9]
{{ 0, 6,1000, 4,1000,1000,1000,1000,1000},
{ 6, 0, 5,1000,1000,1000,1000, 4,1000},
{1000, 5, 0, 3, 4,1000, 5, 6,1000},
{ 4,1000, 3, 0, 7,1000,1000,1000,1000},
{1000,1000, 4, 7, 0, 5,1000,1000,1000},
{1000,1000,1000,1000, 5, 0, 4,1000, 9},
{1000,1000, 5,1000,1000, 4, 0,1000, 6},
{1000, 4, 6,1000,1000,1000,1000, 0, 8},
{1000,1000,1000,1000,1000, 9, 6, 8, 0}};
//Формирование списков смежных вершин по матрице а
for (i = 0; i < 9; i++)
{
p[i,0] = i;k=1;
for (j = 0; j < 9; j++)
if ((a[i, j] != 1000) && (a[i, j] != 0))
{
p[i, k]=j;
k++;
}
p[i, k]=1000;
}
//Печать списков смежных вершин
for (i = 0; i < 9; i++)
{
k = 0;
while (p[i, k] != 1000)
{
Console. Write(" {0}", p[i, k]);
k++;
}
Console. WriteLine();
}
Console. Write("Введите номер начального узла графа? ");
buf = Console. ReadLine();
beg = Convert. ToInt32(buf);
Console. Write("Введите номер конечного узла графа? ");
buf = Console. ReadLine();
en = Convert. ToInt32(buf);
//Начальные установки программы
for (i = 0; i < 9; i++)
{
nov[i] = true;
m[i] = 0;
}
nov[9] = false;
x = 1; //Номер очередного маршрута
m[1] = beg; i1 = 2;
y1.nom = beg; //Определяем поле nom узла y1
y1.ki = beg; // Запоминаем номер списка смеж. вершин
y1.kj = 0; // Запоминаем номер текущей позиции в списке
vkl(vstek, y1);
kol = 1; //Количество элементов в стеке
nov[beg] = false;
nov[en] = false;
i = beg; j = 0;
//Цикл поиска всех маршрутов в графе
while (kol!= 0)
{
do
{
j++;
if (p[i, j] == en)
{
Console. Write(" путь - {0} -", x); x++;
for (i2 = 1; i2 < i1; i2++)
Console. Write(" {0}", m[i2]);
Console. WriteLine(" {0}", en);
}
}
while ((p[i, j] != 1000) && (!nov[p[i, j]]));
if (p[i, j] != 1000)
if (nov[p[i, j]])
{
y1.ki = i;
y1.kj = j;
i = p[i, j];
y1.nom = i;
vkl(vstek, y1);
j = 0;
kol++;
nov[i] = false;
m[i1] = i;
i1++;
};
if (p[i, j] == 1000)
{
kol--;
if (kol!= 0)
{
iskl(vstek);
i = n. ki;
j = n. kj;
i1--;
m[i1] = 0;
nov[n. nom] = true;
}
};
}
Console. WriteLine();
Console. WriteLine("Для продолжения нажмите клавишу Enter");
Console. ReadLine();
}
}
}
Работа программы:
0 1 3
1 0 2 7
2 1 3 4 6 7
3 0 2 4
4 2 3 5
5 4 6 8
6 2 5 8
7 1 2 8
8 5 6 7
Введите номер начального узла графа? 1
Введите номер конечного узла графа? 4
путь - 1 - 1 0 3 2 4
путь - 2 - 1 0 3 2 6 5 4
путь - 3 - 1 0 3 2 6 8 5 4
путь - 4 - 1 0 3 2 7 8 5 4
путь - 5 - 1 0 3 2 7 8 6 5 4
путь - 6 - 1 0 3 4
путь - 7 - 1 2 3 4
путь - 8 - 1 2 4
путь - 9 - 1 2 6 5 4
путь - 10 - 1 2 6 8 5 4
путь - 11 - 1 2 7 8 5 4
путь - 12 - 1 2 7 8 6 5 4
путь - 13 - 1 7 2 3 4
путь - 14 - 1 7 2 4
путь - 15 - 1 7 2 6 5 4
путь - 16 - 1 7 2 6 8 5 4
путь - 17 - 1 7 8 5 4
путь - 18 - 1 7 8 5 6 2 3 4
путь - 19 - 1 7 8 5 6 2 4
путь - 20 - 1 7 8 6 2 3 4
путь - 21 - 1 7 8 6 2 4
путь - 22 - 1 7 8 6 5 4
Для продолжения нажмите клавишу Enter
Если задать две одинаковые вершины, то можно получить все циклы графа, которые начинаются и заканчиваются в заданной вершине, например:
0 1 3
1 0 2 7
2 1 3 4 6 7
3 0 2 4
4 2 3 5
5 4 6 8
6 2 5 8
7 1 2 8
8 5 6 7
Введите номер начального узла графа? 6
Введите номер конечного узла графа? 6
путь - 1 - 6 2 1 0 3 4 5 6
путь - 2 - 6 2 1 0 3 4 5 8 6
путь - 3 - 6 2 1 7 8 5 6
путь - 4 - 6 2 1 7 8 6
путь - 5 - 6 2 3 0 1 7 8 5 6
путь - 6 - 6 2 3 0 1 7 8 6
путь - 7 - 6 2 3 4 5 6
путь - 8 - 6 2 3 4 5 8 6
путь - 9 - 6 2 4 3 0 1 7 8 5 6
путь - 10 - 6 2 4 3 0 1 7 8 6
путь - 11 - 6 2 4 5 6
путь - 12 - 6 2 4 5 8 6
путь - 13 - 6 2 6
путь - 14 - 6 2 7 1 0 3 4 5 6
путь - 15 - 6 2 7 1 0 3 4 5 8 6
путь - 16 - 6 2 7 8 5 6
путь - 17 - 6 2 7 8 6
путь - 18 - 6 5 4 2 1 7 8 6
путь - 19 - 6 5 4 2 3 0 1 7 8 6
путь - 20 - 6 5 4 2 6
путь - 21 - 6 5 4 2 7 8 6
путь - 22 - 6 5 4 3 0 1 2 6
путь - 23 - 6 5 4 3 0 1 2 7 8 6
путь - 24 - 6 5 4 3 0 1 7 2 6
путь - 25 - 6 5 4 3 0 1 7 8 6
путь - 26 - 6 5 4 3 2 1 7 8 6
путь - 27 - 6 5 4 3 2 6
путь - 28 - 6 5 4 3 2 7 8 6
путь - 29 - 6 5 6
путь - 30 - 6 5 8 6
путь - 31 - 6 5 8 7 1 0 3 2 6
путь - 32 - 6 5 8 7 1 0 3 4 2 6
путь - 33 - 6 5 8 7 1 2 6
путь - 34 - 6 5 8 7 2 6
путь - 35 - 6 8 5 4 2 6
путь - 36 - 6 8 5 4 3 0 1 2 6
путь - 37 - 6 8 5 4 3 0 1 7 2 6
путь - 38 - 6 8 5 4 3 2 6
путь - 39 - 6 8 5 6
путь - 40 - 6 8 6
путь - 41 - 6 8 7 1 0 3 2 4 5 6
путь - 42 - 6 8 7 1 0 3 2 6
путь - 43 - 6 8 7 1 0 3 4 2 6
путь - 44 - 6 8 7 1 0 3 4 5 6
путь - 45 - 6 8 7 1 2 3 4 5 6
путь - 46 - 6 8 7 1 2 4 5 6
путь - 47 - 6 8 7 1 2 6
путь - 48 - 6 8 7 2 1 0 3 4 5 6
путь - 49 - 6 8 7 2 3 4 5 6
путь - 50 - 6 8 7 2 4 5 6
путь - 51 - 6 8 7 2 6
Для продолжения нажмите клавишу Enter
В основном цикле while поиска всех маршрутов графа находится цикл do_while и два оператора if.
В цикле do_while, по алгоритму обхода графа в глубину, ищется новая вершина графа. Если очередная вершина графа равна его «конечной» вершине, то происходит печать содержимого стека. В стеке находится перечень вершин маршрута между «начальной» и найденной «конечной» вершинами графа.
В первом операторе if описаны действия алгоритма, если найденная вершина графа является «новой» вершиной.
Во втором операторе if описаны действия алгоритма, если в просматриваемом списке смежных вершин нет «новой» вершины.
26.2 Вопросы для проверки
26.2.1 Зачем в алгоритме поиска всех циклов графа просмотренным вершинам графа «возвращается» свойство новой вершины?
A) Для того, чтобы просмотренную вершину можно было бы использовать в других маршрутах.
B) Для того, чтобы просмотренную вершину в данном маршруте больше не учитывать.
C) Для запоминания наименьшей по номеру новой смежной вершины.
D) Для запоминания всех новых смежных вершин текущей вершины.
E) Для запоминания всех новых ребер инцидентных текущей вершины.
26.2.2 Условие окончания поиска всех циклов графа?
A) Нет новых вершин графа.
B) Все списки смежных вершин графа просмотрены.
C) Количество элементов в стеке равно нулю.
D) Вершина стека равна нулю и нет новых вершин графа.
E) Нет новых вершин графа и списки смежных вершин графа просмотрены
26.2.3 Что хранится в стеке алгоритма поиска всех маршрутов между двумя заданными вершинами?
26.2.4 Что хранится в вершине («узле») графа при поиске всех маршрутов между двумя заданными вершинами?
26.2.5 Зачем в алгоритме поиска всех маршрутов между двумя заданными вершинами используется цикл do_while?
Основные порталы (построено редакторами)