Разработка и реализация на языке высокого уровня алгоритма выделения сильносвязных компонент ориентированного графа
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
111000000V1010100000V2001111100V3000000000V4000000110V5000000001V6100001011V7
Если граф G является разреженным, то есть число ребер m значительно меньше величины (число ребер полного графа
),
то эффективным представлением графа является список его ребер, задаваемый парами вершин. Для этого формируют два массива: (,…, ) и (,…, ). Каждый элемент в массиве есть метка вершины, а i-e ребро графа выходит из вершины . Например неориентированный граф, представленный на рис. 1 будет представлен следующими двумя массивами:
g = (1, 1, 1, 2, 2, 3, 3, 3, 3, 5, 5, 6, 7)
h = (2, 3, 7, 1, 3, 3, 1, 5, 7, 3, 7, 7, 6)
1.3 Сильная связность графов
На практике часто возникают задачи в отыскании сильно связных подграфов (сильно связных компонентов) ориентированного графа.
Для определения сильно связных подграфов введем понятие следующих матриц:
матрица достижимости R=||rij||;
матрица контрдостижимости Q=||qij||;
матрица взаимодостижимости H=||hij||.
Размер всех матриц nn, где n - число вершин графа, элементы матриц определяются следующим образом:
rij=1, если вершина j достижима из вершины i,
rij=0, если вершина j не достижима из вершины i,
qij=1, если вершина i достижима из вершины j,
qij=0, если вершина i не достижима из вершины j,
hij=1, если вершина j достижима из вершины i и вершина i достижима из вершины j, то есть если rij=1 и qij=1.
hij=0, если вершина j не достижима из вершины i или вершина i не достижима из вершины j, то есть если rij=0 или qij=0.
Отношение взаимодостижимости, определяемое матрицей H=||hij||, разбивает все множество вершин V орграфа G на классы взаимодостижимых вершин. Каждый такой класс порождает подграф, который называется сильно связным. Орграф и его сильно связные компоненты показаны на рис. 3.18.
Для алгоритмизации процесса выделения сильно связных подграфов выполним следующие действия:
. Используя технику поиска в глубину или в ширину, найдем матрицу достижимости R.
. Так как rij=qij, то есть R=QT и Q=RT, то, транспонируя матрицу R, получим матрицу контрдостижимости Q.
. Из матриц R и Q получим матрицу взаимодостижимости H.
. Анализируя матрицу H, выделяем классы взаимодостижимых вершин и строим сильно связные подграфы исходного орграфа.
Для орграфа, изображенного на рис. 3.18, матрица достижимости R, контрдостижимости Q и взаимодостижимости H представлены в табл.3.5 - 3.7 соответственно.
Таблица 3.5.
Матрица достижимости орграфа, изображенного на рис. 3.18
v1v2v3v4v5v6v7v11111001v21111001v31111001v41111001v51111111v61111111v70000001
Таблица 3.6.
Матрица контрдостижимости орграфа, изображенного на рис. 3.18
v1v2v3v4v5v6v7v11111110v21111110v31111110v41111110v50000110v60000110v71111111
Таблица 3.7.
Матрица взаимодостижимости орграфа, изображенного на рис. 3.18
v1v2v3v4v5v6v7v11111000v21111000v31111000v41111000v50000110v60000110v70000001
Анализируя матрицу взаимодостижимости, находим следующие классы взаимодостижимых вершин: {v1,v2,v3,v4}, {v5,v6}, {v7}. Сильносвязные компоненты орграфа представлены выше на рис. 3.18.
2. Последовательность выполнения работы
Итак, чтобы перейти к реализации данного алгоритма, необходимо разделить каждую фазу, обозначенную выше, на определенное количество шагов:
Две вершины A,B ориентированного графа называются сильно, связанными если есть пути из A в B и из B в A. Отношение сильной связанности транцитивно, то есть если A сильно связана с B, а B сильно связана с C, то A сильно связана с C.
Сильно связной компонентой ориентированного графа называют множество вершин графа, в котором для любых двух вершин есть пути сиз первой во вторую и из второй в первую.
Многие алгоритмы, работающие на ориентированных графах начинают свою работу с выделения сильно связныхкомпонент: после этого задача решается для каждой компоненты в отдельности, и решения комбинируются.
Граф задается массивом связей, выходящих из каждой вершины.
Для выделения сильно связных компонент используют два поиска в глубину.
-ый раз на исходном графе, 2-ой на транспонированном (исходный граф, в котором обращены все разрешенные направления).
- Connected - Components (G)
1.С помощью DFS(G), для каждой вершины u, найти время окончания обработки - f[u]
2.Построить GT - транспонированный граф
.Вызвать DFS(GT), при этом в его внешнем цикле перебирать вершины в порядке убывания величины f[u] (вычисленной в 1-ой строке)
.Сильно связными компонентами будут деревья поиска, построенные на шаге 3.
3. Тестирование разработанного программного обеспечения
.1 Подбор тестовых данных
Теперь требуется протестировать программу примером, для того чтобы выявить ошибки и исправить их если они допущены.
.)Вводим число вершин в графе.
.)Вводим начальную вершину, из которой будет выходить ребро.
.)Вводим вершину, куда ведет связь.
На выходе мы получаем сильносвязный компонент ориентированного графа.
P.S Граф задается массивом связей, выходящих из каждой вершины.
Для упрощения ввода, вершины считаются пронумерованными от 0 и далее. Для работы с вершинами, которые задаются, например, строковыми именами, следует обратить внимание на топологическую сортировку.
Входные данные: Выходные данные:
1 1
1 2 1
2 3 0 1
0 4 2
4 3 2
3
.2 Анализ и исправление ошибок
Листинг программы рабочий. Преобразования проходят успешно. Ошибок в коде нет. Вносить коррективы не нужно.
Заключение
Курсовой проект выполнен успешно. Программа работает быстро и без сбоев. Блок-схема простая и достаточно понятная. Среда