Отчет 3-4

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

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра ВМиК

Отчёт

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

«Алгоритм поиска в глубину и в ширину в графе »

Выполнила: студ. гр. МО-204

Валиева Э.А.

Проверила:

Верхотурова Г.Н.

Уфа - 2014

Постановка задачи:

Реализовать алгоритм «Поиск в глубину» в порядке возрастания первоначальной нумерации вершин графа.

Алгоритм поиска в глубину:

1. Задаем начальную вершину V, с которой начинаем обход

2. Посетить вершину V и проверить была ли она обработана в результирующем списке

3. Если нет, то провести обработку этой вершины включив ее в результирующий список

   1. Получаем первую смежную вершину с вершиной V

   2. Рекурсивно запускаем от первой смежной вершины с V функцию обхода в глубину

4. Если да, завершаем процесс

Входные и выходные данные:

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

int start = 1;//Задали начальную вершину, в которой начинаем обход

bool[] visited1 = new bool[20];//массив-флагов для обработанных вершин

textBox2.Text = textBox2.Text + (st + 1) + " ";//Результат записываем в текстбокс

Реализация поиска в глубину:

void DFS(int st)

{

int N = dataGridView1.RowCount - 1;//Количество строк в таблице смежность

textBox2.Text = textBox2.Text + (st + 1) + " ";

visited1[st] = true;//Помечаем вершину

for (int r = 0; r < N; r++) //Перебираем вершины

if (dataGridView1.Rows[st].Cells[r].Value!=null && !visited1[r])

//Если вершина не помечена и смежна с текущей

DFS( r);//рекурсивно запускаем от нее DFS

}

private void button1_Click(object sender, EventArgs e)

{

int start = 1;//Задали начальную вершину, в которой начинаем обход

int N = dataGridView1.RowCount - 1;//Количество строк в таблице смежность

bool[] visited = new bool[N];//Создаем матрицу-флагов

for (int i = 0; i < N; i++)

{

visited[i] = false;

}

BFS(visited, start - 1);//Рекурсия

}

Оценка сложности: O(N²)

Постановка задачи:

Реализовать алгоритм «Поиск в ширину» в порядке возрастания первоначальной нумерации вершин графа.

Алгоритм поиска в ширину:

1. Помещаем вершину V в пустую очередь

2. Начинаем итерационный процесс, пока очередь не опустеет.

   1. Взять первую вершину V с очереди и проверяем ее наличие в результирующем списке

   2. Если ее нет в результирующем списке, то посещаем вершину V и помещаем в очередь смежные вершины с V.

Входные и выходные данные:

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

int start = 1;//Задали начальную вершину, в которой начинаем обход

bool[] visited = new bool[N];//Создаем матрицу-флагов

int[] queue = new int[N];// Создаем очередь

textBox1.Text = textBox1.Text + (unit + 1) + " ";//Результат записываем в текстбокс

Реализация поиска в ширину:

void BFS(bool[] visited, int unit)

{

int N = dataGridView1.RowCount-1;//Количество строк в таблице смежность

int[] queue = new int[N];//Создаем очередь

int count, head;

for (int i = 0; i <N; i++) queue[i] = 0;//Очищаем ее

count = 0; head = 0;

queue[count++] = unit;//Помешаем вершину в пустую очередь

visited[unit] = true;

while (head < count) //Пока очередь не пуста

{

unit = queue[head++];//Взять первую вершину с очереди

textBox1.Text = textBox1.Text + (unit + 1) + " ";

//Результат записываем в текстбокс

for (int i = 0; i < N; i++)

if (dataGridView1.Rows[unit].Cells[i].Value != null && !visited[i])

//Если у вершины есть непосещенные смежные вершины

{

queue[count++] = i;

//Посещаем вершину, помещаем в очередь смежные вершины

visited[i] = true;

}

}

}

private void button1_Click(object sender, EventArgs e)

{

int start = 1;//Задали начальную вершину, в которой начинаем обход

int N = dataGridView1.RowCount - 1;//Количество строк в таблице смежность

bool[] visited = new bool[N];//Создаем матрицу-флагов

for (int i = 0; i < N; i++)

{

visited[i] = false;

}

BFS(visited, start - 1);//Рекурсия

}

Оценка сложности: O(N³)

Вывод:

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