Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Мой отчёт по лабе 2

.docx
Скачиваний:
43
Добавлен:
23.01.2014
Размер:
20.9 Кб
Скачать

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

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

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

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

Кафедра ВМиК

Отчёт

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

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

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

Фатхутдинова Л.М.

Проверила:

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

Уфа - 2012

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

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

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

Рассмотрим входные и выходные данные, используемые в программе:

  • list – список вершин графа.

  • dataGridView1 – матрица смежности.

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

  • lst – список, используемый для хранения результата.

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

1. Помещаем начальную вершину в стек

2. Начинаем итерационный процесс, на каждом шаге которого выталкиваем вершину из стека и обрабатываем ее.

2.1. Выталкиваем вершину из стека

2.2. Проверяем по списку, была ли она обработана. Если нет – проводим обработку этой вершины: включаем ее в список, чтобы избежать повторной обработки, и помещаем в стек все смежные с ней вершины, которых еще нет в списке.

Процесс завершается, когда стек становится пустым. Список будет содержать список обработанных вершин.

Реализация

private void button2_Click(object sender, EventArgs e) // в глубину

{

lst.Clear(); //список для хранения обработанных вершин, результат, который будет выводиться

stk.Push(1);// стек для хранения смежных вершин, поместим нач верш в стек

int tmpp = 0;

for (int j = 1; j < list.CList.Count + 1; j++) // итерации процесс прохода по всем вершинам

{

tmpp = 0;

if (stk.Count > 0)

{

int n = stk.Pop();// выталкиваем вершину из стека и обабатываем ее

if (n != 0)

{

if (lst.Contains(n))// была ли обработана вершина

tmpp = 1;

if (tmpp != 1)

{

textBox1.Text = textBox1.Text + n.ToString() + ' ';

lst.Add(n);

// tmp = 0;

}

for (int i = list.CList.Count - 1; i >= 0; i--)//дополнительное условие - не алгоритм, чтобы граф выводился по возрастанию

{

if (this.dataGridView1.Rows[n - 1].Cells[i].Value != null)// по таблице смотрим с какими вершинами у данного кружочка есть связь

{

bool flg = true;

string k = this.dataGridView1.Rows[n - 1].Cells[i].Value.ToString();

int l = 1;

if (k == l.ToString())

{

if (lst.Contains(i + 1))// если лист содержит ту вершину, с которой есть связь

flg = false;

//if (stk.Contains(i + 1))

// flg = false;

if (flg == true)// если нет - добавляем вершину в стек

{

stk.Push(i + 1);

}

}

}

}

}

}

}

}

Оценка сложности

Вывод

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