Практическая работа №17. Работа с графами

Практическая работа №17

Работа с графами

Цель работы

• Изучить основные понятия теории графов
• Познакомиться со способами представления графов в памяти компьютера
• Реализовать алгоритмы обхода графа:
  • DFS (поиск в глубину)
  • BFS (поиск в ширину)
• Научиться использовать стек, очередь и рекурсию

---

1. Теоретические сведения

1.1 Что такое граф

Граф — это структура данных, состоящая из:

• вершин (узлов)
• рёбер (связей между вершинами)

Формально граф записывается так:

G = (V, E)

где:

• V — множество вершин
• E — множество рёбер

Пример графа

0 ---- 1
|      |
2 ---- 3

---

2. Основные термимы

Путь — последовательность вершин, соединённых рёбрами.

Цикл — путь, который начинается и заканчивается в одной вершине.

Степень вершины — количество рёбер, связанных с вершиной.

Компонента связности — подграф, в котором существует путь между любой парой вершин.

---

3. Типы графов

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

A ---- B

Движение возможно в обе стороны.

---

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

A → B

Движение возможно только по направлению стрелки.

---

Взвешенный граф

A --5--> B

Число означает вес ребра (например расстояние).

---

4. Представление графа в памяти

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

Граф можно хранить в виде двумерного массива.

Если между вершинами i и j есть ребро:

A[i][j] = 1

иначе:

A[i][j] = 0

Пример

	0	1	2
0	0	1	1
1	1	0	0
2	1	0	0

Память: O(N²)

---

4.2 Список смежности

Каждая вершина хранит список своих соседей.

Пример:

0 → 1, 2
1 → 0
2 → 0

Память: O(V + E)

---

5. Обход графа

Основные алгоритмы обхода:

Алгоритм	Использует
DFS	стек / рекурсия
BFS	очередь

---

DFS — поиск в глубину

Алгоритм:

1. Начать с выбранной вершины
2. Перейти к соседней вершине
3. Продолжать движение вглубь
4. Если дальше идти нельзя — вернуться назад

---

BFS — поиск в ширину

Алгоритм:

1. Начать с вершины
2. Посетить всех соседей
3. Затем соседей этих соседей

Используется очередь.

---

6. Практическое задание

Необходимо разработать консольную программу на C++, которая выполняет обход графа.

Граф необходимо хранить в виде матрицы смежности.

---

7. Исходный граф

Используйте следующий граф:

const int N = 7;

0 1 1 0 0 0 0
1 0 0 1 1 0 0
1 0 0 0 0 0 1
0 1 0 0 0 1 0
0 1 0 0 0 1 0
0 0 0 1 1 0 0
0 0 1 0 0 0 0

Количество вершин: 7

---

8. Задание №1

Реализуйте алгоритм DFS (поиск в глубину).

Требования:

• использовать стек
• вывести порядок обхода вершин

Пример вывода:

DFS обход графа:
0 1 3 5 4 2 6

(порядок может отличаться)

---

9. Задание №2

Реализуйте алгоритм BFS (поиск в ширину).

Требования:

• использовать очередь
• вывести порядок обхода вершин

Пример вывода:

BFS обход графа:
0 1 2 3 4 6 5

---

10. Дополнительное задание

Определите количество компонент связности в графе.

Подсказка:

• если вершина ещё не посещена
• запустите DFS
• увеличьте счётчик компонент

---

11. Тестовые данные для проверки

Тест 1

Граф:

0 - 1 - 2 - 3 - 4

Ожидаемый DFS:

0 1 2 3 4

Компоненты связности:

1

---

Тест 2

Граф:

0
|
1
|
2

Ожидаемый DFS:

0 1 2

Компоненты связности:

1

---

Тест 3

Несвязный граф:

0 - 1

2 - 3

Ожидаемый DFS (с 0):

0 1

Количество компонент:

2

---

Тест 4

Граф:

0 - 1 - 2
|
3

Пример DFS:

0 1 2 3

---

12. Требования к программе

Программа должна:

• корректно реализовывать DFS
• корректно реализовывать BFS
• выводить порядок обхода
• использовать стек и очередь
• корректно компилироваться

---

13. Контрольные вопросы

1. Что такое граф?
2. Какие элементы содержит граф?
3. Чем ориентированный граф отличается от неориентированного?
4. Что такое матрица смежности?
5. Чем DFS отличается от BFS?
6. Какие структуры данных используются в этих алгоритмах?

---