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

Страницы работы

15 страниц (Word-файл)

Содержание работы

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

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


  Кафедра ПМИ


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

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


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

Группа: Пми-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.

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

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”. С записанными названиями вершин графа через <,>.

Похожие материалы

Информация о работе