Лабораторная работа № 9. Алгоритмы обработки графов

ПредупреждениеНеобходимые файлы

Перед началом работы, скачайте по ссылке файл ds.py с реализацией необходимых структур данных.

Теоретическая часть

Матрица смежности

Элемент \(M[i,j]=1\), если \((i,j)\) является ребром графа \(G\) и \(M[i,j]=0\) в противоположном случае:

Матрица смежности

Абстрактный тип данных Graph

Класс Graph будет храниться в файле ds.py. Чтобы создать новый объект класса Graph необходимо импортировать класс из файла ds.py:

# импорт класса Graph из файла ds.py
from ds import Graph

# создание нового объекта класса Graph
# в скобках - максимальное количество вершин в графе
g = Graph(5)

В Таблице 1 перечислены методы класса Graph.

Таблица 1: Методы класса Graph

Метод	Назначение	Пример
add_edge(v, w)	Делает вершины vи w смежными.	g.add_edge(1, 2)
del_edge(v, w)	Удаляет ребро между вершинами v и w.	g.del_edge(1, 2;
has_edge(v, w)	Проверяет, являются ли смежными вершины v и w. Возвращает логическое значение	b = g.has_edge(0, 1)
set_value(v, st)	Сохраняет строку st в вершине v.	g.set_value(0, 'V')
get_value(v)	Возвращает значение, сохранённое в вершине v. Вернёт пустую строку, если значение до этого не сохранялось.	val = g.get_value(0)
neighbors(v)	Возвращает список вершин смежных с вершиной v.	lst = g.neighbors(1)
abj()	Выводит на экран матрицу смежности графа и возвращает её.	g.abj()

Рассмотрим изображение графа:

Неориентированный граф

Представим данный граф с помощью типа данных Graph. Также выведем на экран список вершин смежных с вершиной 2 и результат проверки на смежность двух пар вершин:

# импорт класса Graph из модуля ds
from ds import Graph

g = Graph(4) # создаём объект типа Graph с 4 вершинами
g.add_edge(0, 1) # добавляем ребро между вершинами 0 и 1
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

# список вершин, смежных с вершиной 2
print(g.neighbors(2)) # -> [0, 1, 3]

# смежны ли вершины 2 и 1 ?
print(g.has_edge(2, 1)) # -> True

# смежны ли вершины 1 и 3 ?
print(g.has_edge(1, 3)) # -> False

Выполнение кода проиллюстрировано на следующем изображении:

Иллюстрация работы кода

Обход графа в глубину

1. Начинаем обход с выбранной вершины, помечаем её как посещённую и рекурсивно переходим к непосещённым соседям.
2. При каждом переходе углубляемся до тех пор, пока не достигнем вершины без не посещённых соседей.
3. После завершения пути возвращаемся назад по стеку вызовов, продолжая обход с других не посещённых вершин.

Обход графа в ширину

1. Начинаем обход с выбранной вершины, добавляя её в очередь и помечая как посещённую.
2. Извлекаем вершину из очереди, посещаем всех её не посещённых соседей и добавляем их в очередь.
3. Повторяем процесс, пока очередь не станет пустой, обходя граф в ширину.

Для реализации данного алгоритма понадобится абстрактный тип данных Очередь - Queue. Чтобы использовать очередь, нужно создать объект класса Queue:

q = Queue() # создание пустой очереди и её хранение в переменной q

Интерфейс типа данных представлен в таблице:

Таблица 2: Методы класса Queue

Метод	Назначение	Пример
enqueue(el)	Метод добавляет el в конец очереди.	q.enqueue(1)
dequeue()	Метод удаляет элемент из начала очереди и возвращает его.	v = q.dequeue()
size()	Метод возвращает количество элементов в очереди.	q.size()

Задания для самостоятельной работы

УведомлениеВнимание

Задания обозначенные значком выполняются на распечатках или в тетради, обозначенные - на компьютере в среде программирования.

Задание 1. Матрица смежности

Заполните матрицу смежности для неориентированного графа из вашего варианта.

Вариант 1

2

3

4

5

6

7

8

9

10

11

12

13

14

Задание 2. Использование типа данных Graph (sam02.py)

Используйте тип данных Graph для описания графа из вашего варианта. Выведите на экран:

• матрицу смежности графа;
• список вершин смежных с указанной в варианте;
• являются ли смежными вершины, указанные в варианте.

Вариант 1

Выведите список вершин смежных с вершиной 0.

Являются ли смежными вершины 1 и 2.

2

Выведите список вершин смежных с вершиной 1.

Являются ли смежными вершины 2 и 3.

3

Выведите список вершин смежных с вершиной 2.

Являются ли смежными вершины 3 и 4.

4

Выведите список вершин смежных с вершиной 3.

Являются ли смежными вершины 4 и 0.

5

Выведите список вершин смежных с вершиной 4.

Являются ли смежными вершины 0 и 1.

6

Выведите список вершин смежных с вершиной 0.

Являются ли смежными вершины 1 и 2.

7

Выведите список вершин смежных с вершиной 1.

Являются ли смежными вершины 2 и 3.

8

Выведите список вершин смежных с вершиной 2.

Являются ли смежными вершины 3 и 4.

9

Выведите список вершин смежных с вершиной 3.

Являются ли смежными вершины 4 и 0.

10

Выведите список вершин смежных с вершиной 4.

Являются ли смежными вершины 0 и 1.

11

Выведите список вершин смежных с вершиной 0.

Являются ли смежными вершины 1 и 2.

12

Выведите список вершин смежных с вершиной 1.

Являются ли смежными вершины 2 и 3.

13

Выведите список вершин смежных с вершиной 2.

Являются ли смежными вершины 3 и 4.

14

Выведите список вершин смежных с вершиной 3.

Являются ли смежными вершины 4 и 0.

Задание 3. Алгоритмы обхода вершин графа

Для графа из Задания 1 запишите порядок обхода вершин начиная с вершины 0, используя алгоритм обхода в глубину и в ширину.

Задание 4. Реализация алгоритма обхода графа в глубину (sam04.py)

Реализуйте функцию DFS(g, v) для обхода графа g в глубину, начиная с вершины под номером v.

Используйте следующую блок-схему:

Рисунок 1

1

2

Шаблон решения:

from ds import Graph # импорт необходимых типо данных

def DFS(g, v):
    # реализация функции по блок-схеме
    
# граф для тестирования функции
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

# вызов функции - начало обхода с вершины 1
DFS(g, 1)

Задание 5. Реализация алгоритма обхода графа в ширину (sam05.py)

Реализуйте функцию BFS(g, v) для обхода графа g в ширину, начиная с вершины под номером v.

Используйте следующую блок-схему:

Рисунок 2

1

2

Шаблон решения:

from ds import Graph, Queue # импорт необходимых типо данных

def BFS(g, v):
    # реализация функции по блок-схеме
    
# граф для тестирования функции
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

# вызов функции - начало обхода с вершины 2
BFS(g, 2)

Задание 6. Проверка

Исправьте код из Задания 4 и Задания 5 так, чтобы проверить правильность выполнения Задания 3 - замените тестовый граф на описание графа из вашего варианта.

Задание 7. Список вершин

Исправьте функцию BFS(g, v) так, чтобы вместо вывода номеров вершин на экран функция возвращала список посещённых вершин.