Поиск минимального подмножества вершин заданного орграфа, от которых достижимы все остальные его вершины

Министерство Образования и науки Российской Федерации

Новосибирский   Государственный   Технический   Университет

  Кафедра ПМИ

Курсовая работа  по дисциплине

“Структуры данных и алгоритмы”

Факультет: ПМИ

Группа: Пми-51

Студент: Коновалов В.О.

Преподаватель: Шапошникова Т. А.

Новосибирск, 2006

1.Условие задачи

(№56 – Касьянов) Найти минимальное подмножество вершин заданного орграфа, от которых достижимы все остальные его вершины.

2.Анализ задачи

Дано:  Входной файл “D:\input.txt”.

Представление данных: <Граф>

<Граф>:= <Список вершин> {<Список дуг>}

<Список вершин>:=<Название вершины> {<,>  <Название вершины>}

<Список дуг>:=<Дуга> {<Дуга>}

<Название вершины>:=<Символ>{<Символ>}

<Символ>:=<a> || <b> || … || <z> || <0> || <1> || … || <9> || < > || <A> || <B> || … || <Z>

<Дуга>:=<\n> <Название вершины> <-> <Название вершины>

Результат: Выходной файл “D:\output.txt”.

Представление данных: <Подмножество вершин>

<Подмножество вершин>:=<Название вершины> <,>{<Название вершины> < >}

<Название вершины>:=<Символ>{<Символ>}

<Символ>:=<a> || <b> || … || <z> || <0> || <1> || … || <9> || < > || <A> || <B> || … || <Z>

Метод решения:

1. Создаём матрицу-дуг (матрица дуг – матрица размером количество вершин на количество вершин графа, где строчка – одна вершина, а ячейка из этой строчки равна 1, если из этой вершины есть дуга в вершину, с номером, совпадающим с номером столбца, и равна 0 в противном случае).
2. Создаём матрицу-путей (матрица путей – матрица размером количество вершин на количество вершин графа, где строчка – одна вершин, а ячейка из этой строчки равна 1, если из этой вершины есть путь в вершину, с номером, совпадающим с номером столбца, и равна 0 в противном случае).
1. все элементы Матрица-путей_i,i=1, Остальные элементы = 0;
2. запоминаем номер строчки, которую мы проверяем на пути (например l), а так же кладём её в стек.
3. перебираем элементы по строчке i в Матрице дуг, пока он не равен 1, и элемент Матрица_{l,столбец}, не равен 1, и пока не конец строки i,
4. если конец строки i, то берём элемент из стека. Если стек не пуст, то смотрим, что за элемент там лежит (приравниваем i этому элементу), но не забираем, иначе выход из определения путей для этой строки.
5. если не конец строки, то i приравниваем столбцу который мы нашли, помещаем номер этой вершины в стек, Матрица-путей_l,i=1;
3. Анализируем матрицу путей. Берём подмножество вершин, состоящее из i вершин (i от 1, до количества вершин минус 1) и проверяем его на доступность всех путей из этого подмножества. Анализ идёт, пока не найдено решение и не перебраны все варианты.
1. Перебор вариантов осуществляется по алгоритму:

  i.  Вариант из i заполняется номерами вершин по порядку с 1 до i-й вершины.

  ii.  Проверяем подмножество на доступность всех путей из этого подмножества:

1.  создаём строчку обнулённую размером количество вершин графа, а затем записываем в ячейки 1, если из подмножества доступна вершина, с порядковым номер = номеру столбца строчки.

  iii.  Если количество вариантов закончилось, то начинаем анализ с подмножеством, состоящим из i + 1 вершин (Количество вариантов закончилось, если 1-й элемент варианта равен количество вершин минус i плюс 1

  iv.  Создаём следующий вариант

1.  q=i.

2.  увеличиваем q-ое число в варианте на единицу.

3.  делаем все все числа с q+1 до i-го равными q-ое+1, q-ое+2 и т.п.

4.  если q-ое число больше, чем количество вершин + q минус i, то уменьшаем q на единицу и идём в действие №3.a,iv,2.

  v.  Проверяем подмножество на доступность всех путей из этого подмножества.

  vi.  идём в действие №3.a.iii.

4. Если решение не найдено, то решение – все вершины.

3.Структура основных входных и выходных данных      

	Внешнее представление	Внутреннее представление
Входные данные	Заданы названия вершин. На следующей строке могут быть заданы, либо отсутствовать, дуги: от какой вершины какая дуга ведёт к какой вершине (название вершины - название вершины, переход на следующую строку либо конец файла)	Динамический список-списков list *head, с Названиями вершин, заданный структурой: struct name { name *next;                            char sim; }; struct list { list *next;                     name *sim; }; После анализа дуг граф представляется двумерным массивом размером количество вершин на количество вершин, в котором строка представляет собой порядковый номер вершины, а элементы в ней либо 0, либо 1, если из вершины идёт дуга в вершину с порядковым номером = номеру столбца.
Выходные данные	Перечисление вершин, составляющих  минимальное подмножество вершин, от которых достижимы все остальные его вершины.	Динамический список-списков list *head, с Названиями вершин, заданный структурой: struct name { name *next;                            char sim; }; struct list { list *next;                     name *sim; }; Динамический массив buf с порядковыми номерами вершин. Выходной файл: “D:\output,txt”. С записанными названиями вершин графа через <,>.