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

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

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

Фрагмент текста работы

Лабораторная №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 разделенных пробелом целых чисел:

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

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