Курсовая работа
по практикуму на ЭВМ: структуры данных и алгоритмы
Факультет: прикладной математики и информатики
Группа: ПМ-01
Студент: Гайворонских А. С
Преподаватель: Тракимус Ю. В
Новосибирск
Условие задачи
Дан граф G. Построить транзитивное замыкание графа G G’. Вершины i и j соединены ребром в транзитивном замыкании G’ тогда и только тогда, когда существует путь между вершинами i и j в исходном графе G.
Анализ задачи
Транзитивное отношение – если для всех x, y, z 
A из того, что (x,y) 
P и (y,z) P, следует, что (x,z) P.
Графические особенности диаграммы: для любых двух дуг, таких, что одна направлена от а к b, а другая от b к с, существует дуга, соединяющая а и с в направлении от а к с.
Характеристики графа:
- ориентированный – поскольку это позволит решить задачу в более широком смысле (т.к неориентированный граф можно рассматривать, как частный случай ориентированного)
- размеченный – каждой вершине необходимо поставить в соответствие какое-либо имя, которое бы отличало ее от других вершин.
- невзвешенный – в задаче ничего не сказано о весе ребер, поэтому для однозначности будем считать все ребра равными, с длиной равной 1.
- несвязный – это позволит решить задачу в более широком смысле.
- простой – наличие кратных ребер и петель не влияет на транзитивность, т.к всегда рассматриваются минимум 3 различные вершины: x, y и z.
Дано:
ГрафG = (V, E)
Результат:
Граф G’ = (V, E’) – транзитивное замыкание графа G
Решение:
W[N][N] – матрица достижимости
graph[N][N] – матрица смежности
Строится матрица достижимости. Если из одной вершины в другую существует путь, то в матрицу достижимости заносится 1, в противном случае 0.
W[ i ][ j ] = graph [ i ][ j ]
Повторять
При к = 0;
Повторять
При i = 0;
Повторять
При j = 0;
W[ i ][ j ] = W[ i ][ j ] или (W[ i ][ k ] и W[ k ][ j ])
j = j+1;
Пока j < n
i = i+1;
Пока i < n
k = k+1;
Пока k < n
Вывод транзитивного замыкания графа G по полученной матрице достижимости.
Таким образом, можно выделить две основные подзадачи:
1. Построение матрицы достижимости. Для этого можно воспользоваться алгоритмом Уоршелла (представлен выше);
2. Вывод транзитивного замыкания графа G.
Структуры данных, используемые для представления исходных данных и результатов задачи
Входные данные. Внешнее представление
Набор символов (имена вершин), попарно записанных в столбец – перечисление ребер графа.
Входные данные. Внутреннее представление
При применении алгоритма Уоршелла строится матрица достижимости, и её заполнение существенно облегчается, т.к изначально была использована матрица смежности. Названия вершин помещаются в отдельный список, обеспечивается связь между матрицей смежности и матрицей достижимости по номерам столбцов и строк.
char name[N][255]-список имен вершин
int graph[N][N] - матрица смежности
n – количество вершин (вычисляется при вводе)
Выходные данные. Внешнее представление
Набор символов (имена вершин), попарно записанных в столбец – перечисление ребер транзитивного замыкания графа G.
Выходные данные. Внутреннее представление
Матрица достижимости, составленная из нулей и единиц: 1 если существует путь из одной вершины в другую в исходном графе, 0 в противном случае.