Алгоритмы обхода графа. Графическая схема алгоритмов. Порядок обхода конкретного графа

Лабораторная №1

Алгоритмы обхода графа(4 часа)

Цель: Изучение основных алгоритмов обхода графа.

Задание:

1.  Для неориентированного  графа сохранить его в виде списка смежности.

2.  Предусмотреть возможность добавления в граф связей, удаления ребер и вершин.

3.  Построить алгоритмы обхода графа в глубину(DFS рекурсивный и нерекурсивный ) и в ширину (BFS). Для каждого из алгоритмов вывести порядок обхода графа.   

Отчет должен содержать: Постановку задачи, графическую схему алгоритма, порядок обхода для конкретного графа из варианта задания при использовании различных алгоритмов.  Отчет оформляется от руки за исключением текста и результатов программы.

Вариант 1,13.

Количество вершин 8 ,  количество связей 10.

1 -> 3

1 -> 5

2 -> 4

6 - > 8

7 -> 5

2 -> 8

8 -> 4

3 -> 5

Вариант 2,14.

Количество вершин 8 ,  количество связей 10.

2 -> 3

1 -> 5

2 -> 4

7 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 3, 15.

Количество вершин 8 ,  количество связей 10.

1-> 2

1 -> 5

2 -> 4

6- >3

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 4,16.

Количество вершин 8 ,  количество связей 10.

2 -> 8

1 -> 5

2 -> 1

3 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 5,17.

Количество вершин 8 ,  количество связей 10.

2 -> 6

1 -> 5

2 -> 1

3 - > 1

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 6,18.

Количество вершин 8 ,  количество связей 10.

4 -> 8

6 -> 5

2 -> 1

3 - > 8

7 -> 5

2 -> 8

8 -> 4

4 -> 5

Вариант 7,19.

Количество вершин 8 ,  количество связей 10.

1 -> 7

2 -> 5

2 -> 1

3 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 1

Вариант 8,20.

Количество вершин 8 ,  количество связей 10.

2 -> 8

4 -> 5

2 -> 1

3 - > 8

7 -> 5

7 -> 8

8 -> 4

6 -> 5

Вариант 9,21.

Количество вершин 8 ,  количество связей 10.

2 -> 8

1 -> 4

2 -> 6

3 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 10,22.

Количество вершин 8 ,  количество связей 10.

2 -> 7

3 -> 5

2 -> 1

1 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 11, 23.

Количество вершин 8 ,  количество связей 10.

3 -> 4

1 -> 5

2 -> 1

1 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 5

Вариант 12,24.

Количество вершин 8 ,  количество связей 10.

2 -> 8

1 -> 5

2 -> 1

3 - > 8

7 -> 5

2 -> 8

8 -> 4

6 -> 7

Задачи  из сайта dl.gsu.by.(для желающих). Там их  можно оттестировать.

Задача 1.( USACO 2004-2011\Bronze\Граф\DFS\10_NovB - "Daisy Chains in the Field" 101706  Sherry Wu, 2010 Англ. вариант)

Фермер Джон разрешил своим N (1 <= N <= 250) коровам, последовательно 

пронумерованным от 1 до N, поиграть в поле. Некоторые коровы решили себя 

связать попарно веревками и создали M (1 <= M <= N*(N+1)/2) попарных связей.

Конечно, никакие две коровы не связаны непосредственно более чем одной веревкой. 

Ввод показывает пары коров c1 и c2, которые связаны.  

 (1 <= c1 <= N; 1 <= c2 <= N; c1 != c2).

ФД приказал коровам быть частью цепочки, которая содержит корову 1.

Помогите ФД найти номера всех коров, которые не связаны в цепочку 

(посредством одной или нескольких веревок) с коровой 1. Корова 1 

всегда связана с собой. Если таких непослушных коров нет, выведите 0.

Для примера рассмотрим 6 коров с четырьмя веревками:

    1---2  4---5

     \  |

      \ |      6

       \|

        3

Визуально мы видим, что коровы 4 5 и 6 не связаны с коровой 1.

INPUT FORMAT:

* Строка 1: Два разделенных пробелом целых числа : N и M

* Строки 2..M+1: Строка i+1 показывает двух коров, соединенных веревкой i 

                 с помощью двух целых чисел, разделенных пробелом:

                 c1 и c2

SAMPLE INPUT 

6 4

1 3

2 3

1 2

4 5

OUTPUT FORMAT:

* Строки 1..???: Каждая строка содержит одно целое число.

SAMPLE OUTPUT

4

5

6

Задача 2 (USACO 2004-2011\Bronze\Граф\BFS\11_MarB - "Pathfinding" 103156  Sherry Wu, 2011 Англ. вариант)

Беси стоит на берегу заброшенного арктического острова и хочет 

определить все пути, которыми она может вернуться на свое пастбище.

Она проверила свою лодку и знает, что она может плыть от острова 

к острову за единицу времени, если имеется маршрут между этой

парой островов.

Она создала карту океана с проложенными маршрутами между каждой 

парой из N (1<=N<=100)  островов, пронумерованных последовательно

от 1 до N. Все маршруты однонаправленные. Два острова могут быть 

связаны двумя разными однонаправленными маршрутами, что обеспечит

двунаправленное соединение. На карте нет маршрутов, соединяющих

остров сам с собой.

Задано начальное положение Беси M (1 <= M <= N) и карта, помогите 

Беси определить все острова на расстоянии «одного перехода», «двух 

переходов» и т.д. Если Беси может попасть на какой-то остров множеством 

способов, рассматривайте только путь с кратчайшим расстоянием.

Например, ниже представлены N=4 связанных острова (M=1 в этом примере), 

       start--> 1-------->2

                |         |

                |         |

                V         V

                4<--------3

Беси может попасть на остров 1 в момент времени 0 (поскольку M=1),

на острова 2 и 4 в момент времени 1, на остров 3 в момент времени 2.

Ввод для данной задачи – матрица C, где ненулевое значение C_rc

(0 <= C_rc <= 1) в строке r и колонке c означает «Беси может переплывать»

от острова r к острову c за одну единицу времени. Строка C_r состоит 

из N элементов, соответственно C_r1..C_rN, каждый из которых

равен либо 0, либо 1.  

PROBLEM NAME: pathfind

INPUT FORMAT:

* Строка 1: Два разделенных пробелом целых числа: N M

* Строки 2..N+1: строка i+1 содержит N разделенных пробелом целых чисел: