|
|
1 |
0 |
0 |
||
|
4 |
0 |
0 |
1 |
1 |
0 |
|
5 |
0 |
0 |
1 |
0 |
1 |
Рис. 2.3(а). Пример графа Рис.
2.3(б). Матрица связности для графа
Значение элемента матрицы связности определяется следующим образом:
Для определения максимальной связной компоненты графа, представленного матрицей
связности A[n*n] требуется выполнить следующее:
Шаг 1: Заполнить массив индексов idx[n] значениями -1
Шаг 2: Присвоить переменной x значение
0
Шаг 3: Найти idx[i] такое, что idx[i] = -1. Если не найдено – перейти к шагу 7
Шаг 4: Присвоить idx[i] значение x.
Шаг 5: Используя алгоритм поиска в ширину, получить список вершин, к которым
существует путь из вершины i. Для
каждой такой вершины установить значение соответствующего индекса в массиве idx равным x
Шаг 6: Увеличить x на единицу и перейти к шагу
3
Шаг 7: Получить для чисел от 0 до x количество вхождений в массив idx. Результат поместить в массив C таким образом, что в C[1] будет
находиться количество вхождений в idx чисел 1, в C[2] – чисел 2 и так далее
Шаг 8: Вычислить Cnmax – номер максимального
значения в массиве C
Шаг 9: Удалить из графа все вершины, значение idx[i] которых не равно Cnmax.
Полученный граф будет являться подграфом исходного графа, представляющий собой
его максимальную связную компоненту.
Например, для графа, представленного на рисунке 2.4 процесс выделения
максимальной связной компоненты графа выглядит так, как это показано на рис. 2.
4
Рис. 2. 4. Пример графа
Построим таблицу связности для данного графа – таблица 2.3
Таблица 2.3
Таблица связности графа
1
2
3
4
5
6
7
8
9
10
1
1
1
0
0
0
0
0
0
0
0
2
1
1
1
0
0
0
0
0
0
0
3
0
1
1
0
0
0
0
0
0
0
4
0
0
0
1
1
0
0
0
0
0
5
0
0
0
1
1
1
0
0
0
0
6
0
0
0
0
1
1
0
0
0
1
7
0
0
0
0
0
0
1
0
0
0
8
0
0
0
0
0
0
0
1
1
0
9
0
0
0
0
0
0
0
1
1
0
10
0
0
0
0
0
1
0
0
0
1
Выполнение шагов от 1 до 6 включительно представлено в таблице 2.4
Таблица 2.4
Выполнение алгоритма поиска максимальной связной компоненты на шагах 1-6 (Массив idx)
Итерация
1
2
3
4
5
6
7
8
9
10
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
0
0
-1
-1
-1
-1
-1
-1
-1
2
0
0
0
1
1
1
-1
-1
-1
1
3
0
0
0
1
1
1
2
-1
-1
1
4
0
0
0
1
1
1
2
3
3
1
На следующем шаге формируется матрица C, представленная в таблице 2.5
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42
При использовании материалов активная ссылка на источник обязательна.