Course_manual
.pdf}
}
//функция обнаружения не пройденных вершин графа void WayDepth (void)
{ |
|
|
int u; |
|
|
nT = -1; |
//глобальная переменная для вычисления индекса |
|
|
//в массивах T и B |
|
count = -1; |
//глобальная переменная для вычисления меток |
|
|
//обнаруженных вершин |
|
for (u = 0; u < n; u++) Mark[u] = -1; |
//сначала все вершины графа |
|
|
|
//помечаем как не пройденные |
for (u = 0; u < n; u++) |
|
//выбор очередной не пройденной |
if (Mark[u] = = -1) Depth (u, -1); |
// вершины |
|
}
void main ( void )
{
File *p, *f; int i, j, n;
//ввод исходных данных
p = fopen( “spisok_Adj.in”, “r” ); if (fscanf (p, “%d”, &n ) != EOF)
{Fst [0] = 0; |
//установка указателя начала списка смежности для |
|
//первой вершины |
//ввод метки вершины //ввод числа вершин в списке // смежности вершины i
for ( j = 0; j < Nbr [i]; j++ ) //ввод списка смежности вершины i
fscanf (p, “%d”, &Adj [ Fst [i] + j] );
Fst [i + 1] = Fst [i] + Nbr [i]; //установка указателя начала
//списка смежности следующей вершины
} |
|
WayDepth ( ); |
// Проход графа в глубину |
// вывод результатов
f = fopen( “spisok_reber.out”, “w” ); for ( i = 0; i < nT/2; i++ )
printf (f, “%d “, Vt [ T[2*i – 1] ] ); printf (f, “\n”);
for ( i = 0; i < nT/2; i++ )
printf (f, “%d “, Vt [ T[2*i ] ] ); printf (f, “\n”);
for ( i = 0; i < nT/2; i++ ) printf (f, “%d “, B [ i ] );
printf (f, “\n”); fclose ( p ); fclose ( f );
}
Рассмотрим работу программы на примере неориентированного графа, представленного на рис. 1.4. В графе 7 вершин, вершины помечены целыми числами от 0 до 6).
Структура смежности этого графа:
v |
Adj [v] |
|
0 |
1, 2, 4 |
|
1 |
0, 2, 3 |
|
2 |
0, 1, 3, 4 |
|
3 |
1, 2 |
|
4 |
0, 2, 5, 6 |
|
5 |
4, 6 |
|
6 |
4, 5 |
|
|
|
|
Рис.1.4.
Исходные данные структуры смежности графа задаются в текстовом файле spisok_Adj.in в следующем формате:
•в первой строке файла содержится число вершин графа;
•далее для каждой вершины в отдельной строке указывается номер самой вершины, число вершин смежных с данной, и список этих вершин (вершины перечисляются в порядке возрастания меток вершин).
Исходный файл для графа на рис. 1.4.: 7
0 |
3 |
1 2 4 |
1 |
3 |
0 2 3 |
2 |
4 |
0 1 3 4 |
3 |
1 |
1 2 |
4 |
4 |
0 2 5 6 |
5 |
2 |
4 6 |
6 2 4 5
В программе эта структура реализована в массивах Vt, ADj, Fst, Nbr, имеющих следующий вид:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Vt |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[x] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
4 |
0 |
2 |
3 |
0 |
1 |
3 |
4 |
1 |
2 |
0 |
2 |
5 |
6 |
4 |
6 |
4 |
5 |
Adj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[x] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nbr [x] |
3 |
3 |
4 |
2 |
4 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Fst [x] |
0 |
3 |
6 |
10 |
12 |
16 |
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Данное отображение структуры смежности позволяет обращаться к элементам массивов по номерам (меткам) соответствующих вершин. Операция v ADj [x] в программной реализации представляется как
for (i = 0; i < Nbr[x]; i++) v = Adj [Fst [x] + i] . . . , где Nbr[x] – количество вершин в структуре смежности для вершины x; Adj [x] – массив, содержащий списки смежности для каждой вершины; Fst [x] – номер первой вершины в списке смежности, соответствующем вершине x, тогда Fst [x] + i – номер i – й вершины в списке смежности, соответствующем вершине x. Например, пусть x = 3, тогда
Fst [3] = 10 и |
Nbr [3] = 2 (в списке смежности вершины x два элемента), |
элементы |
Adj [ Fst [3] + 0] = Adj [10] = 1 и Adj [Fst [3] + 1] = Adj |
[11] = 2 составляют список смежности вершины x = 3.
Решение задачи начинается с вызова функции WayDepth, которая сначала помечает в массиве Mark все вершины как не пройденные (красит их меткой равной -1). Затем из вершин выбирается очередная (в порядке возрастания меток вершин) не пройденная вершина. Эта вершина рассматривается как корень дерева поиска в глубину и для нее запускается функция Depth, реализующая проход графа в глубину. Функция Depth помечает в массиве Mark эту вершину как обнаруженную (красит ее значением целой переменной count, т.е. пройденные вершины постепенно нумеруются от 0 до │V│ по мере того, как в них попадаем). Затем просматривается список смежности вершины, для которой запущена функция Depth. Если в этом списке есть еще не пройденные вершины (т. е. метка Mark [v] вершины v равна -1), то ребро (x, v) добавляется к множеству основных ребер дерева поиска в глубину (вершины x и v помещаются в массив T). Процесс прохода графа в глубину в этом случае продолжается, начиная с не пройденной вершины v (для вершины v запускается функция Depth). Когда в списке смежности вершины x обнаружена пройденная вершина, то при Mark [v] ≠ -1 ребро (x, v) будет являться обратным ребром, если Mark [v] < Mark [x] и v ≠ s. Условие Mark [v] < Mark [x] означает, что вершина v была пройдена раньше
вершины x. Поэтому ребро (x, v) будет обратным, если оно не является ребром дерева поиска, пройденным от предка s к x, т. е. v ≠ s.
Решение заканчивается, когда будут просмотрены все вершины графа (т. е. все элементы массива Mark станут отличны от -1).
Дерево поиска в глубину для графа на рис. 1.4. имеет следующий вид:
Сплошными линиями отмечены ребра дерева, которые были пройдены во время обхода графа в глубину, пунктирными – обратные ребра. (На рис. 1.4. жирными линиями отмечены ребра, которые были пройдены во время обхода графа в глубину).
Состояния рабочих массивов Mark, T и B после завершения алгоритма приведены ниже:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Mark |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[x] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
2 |
2 |
0 |
2 |
3 |
3 |
1 |
2 |
4 |
4 |
0 |
4 |
5 |
5 |
6 |
6 |
4 |
T [x] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B [x] |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
Результаты работы выводятся в файл spisok_reber.out в следующем формате:
•в первой строке файла метки начальных вершин ребер дерева поиска в глубину;
•во второй строке файла метки конечных вершин ребер дерева поиска в глубину;
•в третьей строке файла признаки ребер: значение 1 – признак основного ребра, значение 0 – признак обратного ребра.
Выходной файл для графа на рис. 1.4.:
0 1 2 2 3 2 4 4 5 6
12 0 3 1 4 0 5 6 4
11 0 1 0 1 0 1 1 0
Задача 2. В неориентированном графе G(V,E) требуется выделить компоненты связности.
Так как граф неориентированный, то для нахождения компонент связности достаточно пройти граф в глубину, пока остаются не пройденные вершины, при этом помечая вершины одной компоненты связности одинаковыми метками. Для этого достаточно использовать переменную, значение которой изменяется, если полностью пройдена компонента связности (в данной программе это глобальная переменная count). Компонента связности при проходе в глубину будет полностью пройдена, когда в списках смежности вершин этой компоненты не станется не пройденных вершин. Вершины графа помечены целыми числами. Граф задан структурой смежности Adj [u].
Программа выделения компонент связности – поиск в глубину (язык Си)
# include <stdio.h>
# define maxn 100 //максимальное число вершин в графе
# define maxADj 1000 // максимальная длина списка смежности графа
int n, count = 0;
int Adj [maxADj]; //список смежности графа
int Fst [maxn]; |
//указатели на списки смежности для каждой v V |
|
int Nbr [maxn]; |
//число вершин в списке смежности для каждой v V |
|
int Vt [maxn]; |
//список вершин графа |
|
int Mark [maxn]; |
//метки вершин графа |
|
//функция прохождения одной компоненты связности |
||
void Component ( int u ) |
|
|
{ |
|
|
int i, v; |
|
|
Mark [u] = count; |
|
// вершина u помечается как пройденная вершина |
for (i = 0; i < Nbr [u ]; i++) |
//просмотр списка смежности вершины u |
|
{ v = Adj [Fst [u ] + i]; |
//выбор из списка смежности u еще не |
|
if (Mark [v] = = 0) |
//пройденной вершины |
|
Component (v );
}
}
//функция поиска не пройденных вершин графа, т.е. новой компоненты связности void STRONGL_Comp2 (void)
{ |
|
int u; |
|
for (u = 0; u < n; u++) Mark[u] = 0; |
//сначала все вершины графа |
|
//помечаем как не пройденные |
for (u = 0; u < n; u++) |
//выбор очередной не пройденной вершины |
if (Mark[u] = = 0) |
|
|
{ count ++; |
//увеличение числа компонент связности |
|
Component (u ); |
|
|
} |
|
|
void main ( void ) |
|
|
{ |
|
|
File *p, *f; |
|
|
int i, j, n; |
|
|
// ввод исходных данных |
|
|
p = fopen( “spisok_Adj.in”, “r” ); |
|
|
if (fscanf (p, “%d”, &n ) != EOF) |
//ввод числа вершин графа |
|
{Fst [0] = 0; |
//установка указателя начала списка смежности для |
|
|
//первой вершины |
|
for ( i = 0; i < n; |
i++) |
|
{ fscanf (p, “%d”, &Vt [i] ); |
//ввод метки вершины |
|
fscanf (p, “%d”, &Nbr [i] ); |
//ввод числа вершин в списке |
|
|
|
// смежности вершины i |
for ( j = 0; j < Nbr [i]; j++ ) |
//ввод списка смежности вершины i |
|
fscanf (p, “%d”, &Adj [ Fst [i] + j] ); |
||
Fst [i + 1] = Fst [i] + Nbr [i]; |
//установка указателя начала |
|
|
//списка смежности следующей вершины |
|
}
STRONGL_Comp2 ( ); // Проход графа в глубину, поиск компонент связности
// вывод результатов
f = fopen( “component.out”, “w” ); for ( i = 0; i < n; i++ )
printf (f, “%d “, Vt [ i ] ); printf (f, “\n”);
for ( i = 0; i < n; i++ )
printf (f, “%d “, Mark [ i ] ); fclose ( p ); fclose ( f );
}
Рассмотрим работу программы на примере неориентированного графа, представленного на рис. 1.5. В графе 11 вершин, вершины помечены целыми числами, начиная с 1.
Рис.1.5.
Структура смежности этого графа:
v |
Adj [v] |
|
1 |
2, 3, 4 |
|
2 |
1, 3 |
|
3 |
1, 2, 4 |
|
4 |
1, 3 |
|
7 |
8, 9 |
|
8 |
7 |
|
9 |
7 |
|
12 |
14, 15, 21 |
|
14 |
12, 15 |
|
15 |
12, 14 |
|
21 |
12 |
|
|
|
|
Исходные данные структуры смежности графа задаются в текстовом файле spisok_Adj.in в формате аналогичном задаче 1.
Исходный файл для графа на рис. 1.5.:
11 |
|
|
|
|
1 |
3 |
2 |
3 |
4 |
2 |
2 |
1 |
3 |
|
3 |
3 |
1 |
2 |
4 |
4 |
2 |
1 |
3 |
|
7 |
2 |
8 |
9 |
|
8 |
1 |
7 |
|
|
9 |
1 |
7 |
|
|
12 3 |
14 |
15 21 |
||
14 2 |
12 |
15 |
||
15 2 |
12 |
14 |
||
21 1 |
12 |
|
||
В программе эта структура реализована в массивах Vt, ADj, Fst, Nbr, метки компонент – в массиве Mark. Состояния массивов после выполнения программы приведены ниже.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
7 |
8 |
9 |
12 |
14 |
15 |
21 |
|
|
|
|
|
|
|
|
|
|
|
Vt |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[u] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
2 |
3 |
2 |
2 |
1 |
1 |
3 |
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
Nbr |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[u] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Fst [u] |
0 |
3 |
5 |
8 |
10 |
12 |
13 |
14 |
17 |
19 |
21 |
|
|
|
|
|
|
|
|
|
|
|
Adj [u] |
2 |
3 |
4 |
1 |
3 |
1 |
2 |
4 |
1 |
3 |
8 |
9 |
7 |
7 |
14 |
15 |
21 |
12 |
15 |
12 |
14 |
12 |
Mark [x] |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
|
|
|
|
|
|
|
|
|
|
|
Результаты работы выводятся в файл component.out в следующем формате:
• в первой строке файла метки вершин графа;
• во второй строке файла номера компонент связности. Выходной файл для графа на рис. 1.5.:
1 |
2 |
3 |
4 |
7 |
8 |
9 |
12 |
14 |
15 |
21 |
1 1 |
1 |
1 2 2 2 |
3 |
3 |
3 |
3 |
||||
2.3.3. Обход (или поиск) в ширину
Пусть задан граф (исходный граф может быть неориентированным или ориентированным) и фиксирована начальная вершина s. В процессе поиска мы идем вширь, а не вглубь: сначала просматриваем все соседние с s вершины, затем соседей соседей и т. д. Алгоритм поиска в ширину перечисляет все достижимые из s (если идти по ребрам) вершины в порядке возрастания расстояния от s. Расстоянием считается длина (число ребер) кратчайшего пути. В процессе поиска из графа выделяется часть, называемая “деревом поиска в ширину” с корнем s. Оно содержит все достижимые из s вершины (и только их). Для каждой из этих вершин путь из корня (вершины s) в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм также использует цвета вершин. Вначале все вершины белые (не пройденные), в процессе поиска белая вершина может стать серой, если она обнаружена, а серая – черной. Различие между серой и черной вершиной позволяет поддерживать такое свойство: если (u,v) E и u черная, то v – серая или черная вершина. Таким образом, только серые вершины могут иметь смежные необнаруженные вершины.
Вначале дерево поиска в ширину состоит только из корня – начальной вершины s. Как только обнаружена белая вершина v, смежная с ранее найденной вершиной u, вершина v (вместе с ребром (u,v)) добавляется к дереву поиска, становясь потомком вершины u, а u становится родителем v. Каждая вершина обнаруживается только однажды, так что двух родителей у нее быть не может.
Приведенный ниже алгоритм использует представление графа списками смежных вершин Adj [u]. Для каждой вершины u графа дополнительно хранятся ее цвет Mark [u] и ее предшественник Pr [u]. Если предшественника нет (например, если u = s или u еще не обнаружена), то Pr [u ] = nil. Кроме того, в d [u] записывается расстояние от s до u. Алгоритм также использует очередь Q для хранения множества серых вершин.
Поиск_в_ширину (G, s)
1 {
2 for (каждая вершина u V[G] –{s})
3{ Mark [u]←БЕЛЫЙ;
4 |
d [u] ←∞; |
5 |
Pr [u] ←nil; } |
6Mark [s] ←СЕРЫЙ;
7 d [s] ←0;
8Pr [s] ←nil;
9Q←{s};
10While (Q ≠ )
11{ u←head [Q];
12 |
for (каждая вершина v Adj [u]) |
13 |
{ if (Mark [v] = БЕЛЫЙ) |
14 |
{ Mark [v]←СЕРЫЙ; d [v]←d [u]+1; |
15 |
Pr [v]←u; InQUEUE (Q, v); } |
16 |
} |
17 |
OutQUEUE (Q); |
18 |
Mark [u] ←ЧЕРНЫЙ; |
19 |
} |
20 |
} |
Сначала все вершины, кроме начальной s становятся белыми, все значения d бесконечными, а предком всех вершин объявляется nil (строки 1– 4 алгоритма). Затем начальная вершина считается обнаруженной и красится в серый цвет, расстояние d [s] объявляется равным 0, а предшественником вершины s объявляется nil (строки 5–7). Вершина s помещается в очередь Q (строка 8), и начинается проход графа в ширину. Основная часть алгоритма выполняется пока очередь не пуста, то есть существуют серые вершины (вершины, которые уже обнаружены, но списки смежности которых еще не просмотрены). Вершина, находящаяся в начале (голове) очереди помещается в u (строка 10). Для вершины u просматриваются все смежные с ней вершины (строки 11–16). Обнаружив среди них белую вершину, делаем ее серой (строка 13), объявляем u ее родителем (строка 15) и устанавливаем расстояние до вершины v равным d [u] + 1 (cтрока 14). Затем эта вершина добавляется в конец очереди Q (строка 16). Когда список смежности вершины u просмотрен полностью, удаляем вершину u из очереди, перекрасив ее в черный цвет (строки 17–18).
2.3.4. Пример решения задачи методом поиска в ширину
Задача 3. В неориентированном графе G(V,E) найти все вершины недостижимые от заданной вершины.
В неориентированном графе вершины недостижимые от заданной – это вершины, принадлежащие другой компоненте связности, чем заданная вершина. Поэтому, чтобы решить эту задачу достаточно пройти граф в глубину или в ширину, начиная с заданной вершины и пометить все вершины, которые встречаются при обходе. Когда будут пройдены все вершины компоненты связности, которой принадлежит заданная вершина, все вершины, оставшиеся не пройденными,
являются недостижимыми. Поскольку в процессе обхода достаточно просто пометить вершину как пройденную, то лучшим решением будет нерекурсивная
реализация |
обхода графа. В данной задаче воспользуемся возможностью |
различать |
при обходе вершины обнаруженные (серые вершины) и уже |
обработанные (черные). В этом случае при обходе в ширину достаточно использовать массив меток Mark со следующими значениями: 0 – не обнаруженная вершина, 1 – обнаруженная, 2 – обработанная вершина. Вершины графа помечены числами от 1 до │V│. Граф задан структурой смежности.
Программа поиска недостижимых вершин ( поиск в ширину) (язык Си)
#include <stdio.h>
#include <alloc.h>
#define SI sizeof (int)
struct VER
{int kol; int mv; int *adj; };
int n;
struct VER *Vt; File *p, *f;
//функция ввода списков смежности графа void vvod_graf ( )
{ |
|
int i, j, N, kol; |
|
p = fopen( “spisok_Adj.in”, “r” ); |
|
if (fscanf (p, “%d”, &n ) != EOF) |
//ввод числа вершин |
графа |
//выделение памяти основным |
{Vt = (struct VER *) calloc (n, SI); |
|
элементам |
//структуры смежности графа |
|
|
for ( i = 0; i < n; i++) |
|
{ fscanf (p, “%d”, &Vt [i] . mv ); |
//ввод метки вершины |
графа |
//ввод числа вершин в списке |
fscanf (p, “%d”, &Vt [i] . kol ); |
|
смежности |
//вершины i |
kol = Vt [i].kol; |
|
Vt [i] . adj = (int*) calloc (kol, SI); |
//выделение памяти списку смежности |
if (kol) |
|
for ( j = 0; j < kol; j++ ) |
//ввод списка смежности i-й вершины |
{ fscanf (p, “%d”, &N ); Vt [i]. adj [j] = N – 1; }
}
}
fclose ( p );
}
//функция прохождения графа с заданной вершины void proverka ( int u )
{
int i, v, flag = 1;