О задачах обхода графа
3
Строки этой матрицы разбиваются на массивы, каждый из кото-
рых состоит из одинаковых строк. Соответствующие вершины графа
дают разбиение на компоненты связности.
Пример 1.
Пусть граф задан матрицей смежности
1 0 1 0
0 1 0 0
.
1 0 1 1
0 0 1 1
A
Тогда
2
3
1 0 1 1
1 0 1 1
0 1 0 0
0 1 0 0
,
.
1 0 1 1
1 0 1 1
0 0 1 1
0 0 1 1
A
A
Выясняется, что матрица
A
3
= A
2
, и, следовательно, равна матрице
достижимости. Матрица достижимости содержит три одинаковые
строки — первую, третью и четвертую, соответствующие вершины
образуют одну компоненту связности, а другую образует вторая вер-
шина. Геометрический граф для этой матрицы изображен на рис. 1.
Рис. 1
. Граф с матрицей смежности
А
Также для нахождения матрицы достижимости можно использо-
вать другую, более быструю, процедуру.
Матрица достижимости будет строиться из матрицы смежности с
единицами на главной диагонали.
Последовательно просматривается первая строка матрицы
A
. Ес-
ли обнаруживается единица в
i
-м столбце, то все единицы
i
-й строки
переносятся в первую строку той же матрицы на соответствующие
места (если там уже стоит единица, то она остается), а номер
i
зано-
сится в специальный массив достижимых вершин
D
1
(будущий спи-
сок вершин из одной компоненты связности). Далее ищем в первой
строке единицы после
i
-го столбца. Дойдя до конца первой строки,
возвращаемся в начало и повторяем процедуру (не обращая внима-
ния на столбцы с номерами из
D
1
) до тех пор, пока в этой первой
строке не перестанут появляться новые единицы. В итоге мы полу-
чим список
D
1
вершин, достижимых из первой вершины, т. е. мы по-
1
2
3
4
