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

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

Пензенский государственный университет

Кафедра «Вычислительная техника»

ОТЧЕТ

по лабораторной работе №4

по курсу «Л и ОА в ИЗ»

на тему «Обход графа в глубину»

Пенза 2020

Цель работы:

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

Ход работы:

Задание 1

1. Сгенерируйте (используя генератор случайных чисел) две матрицу

смежности для неориентированного графа G. Выведите сгенерированные

матрицы на экран.

2. Для сгенерированного графа осуществите процедуру обхода в

глубину, реализованную в соответствии с приведенным выше описанием.

Задание 2*

1. Для матричной формы представления графов выполните

преобразование рекурсивной реализации обхода графа к не рекурсивной.

[pic 1]

Результат работы программы

Объяснение вывода программы:

Для начала работы, программа просит ввести размерность матрицы смежности. В нашем случае это 5×5. После чего выводится сама матрица смежности. После выводится каждая вершина, а также вершины смежные с ней. Далее программа просит ввести номер вершины, с которой Вы бы хотели начать обход. В нашем случае это вершина 5. После чего на экран выводится порядок обхода. Сначала результат нерекурсивного обхода, а потом рекурсивного.

 Проверка работы программы:

[pic 2]

[pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11]

5→2→3→1→4

Листинг:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <conio.h>

#include <time.h>

#include <stack>

#include <queue>

using namespace std;

int i, j, m;

bool* visited = new bool[m];

int** graph;

stack <int> s;

stack <int> DFSstack;

void DFS_2(int vertex) {

        DFSstack.push(vertex);

        visited[vertex] = 1;

        while (!DFSstack.empty()) {

                vertex = DFSstack.top();

                printf("%d ", vertex + 1);

                DFSstack.pop();

                for /*(int i = 0; i <= m; i++)*/(int i = m; i >= 0; i--) {

                        if (graph[vertex][i] == 1 && visited[i] != 1) {

                                visited[i] = 1;

                                DFSstack.push(i);

                        }

                }

        }

}

void DFS_1(int st)

{        

        stack <int> ss;

        visited[st] = true;

        printf("%d ", st + 1);

        ss.push(st);

        int v;

        while (!ss.empty())

        {

                v = ss.top();

                ss.pop();

                for (i = 0; i < m; i++)

                {

                        if ((graph[v][i] == 1) && (visited[i]== false ))

                        {