Мой отчёт по лабе 2
.docxМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра ВМиК
Отчёт
по лабораторной работе
«Алгоритм поиска в глубину в графе»
Выполнила: студ. гр. МО-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);
}
}
}
}
}
}
}
}
Оценка сложности
Вывод
В ходе лабораторной работы я познакомилась с такими понятиями как неориентированный граф, матрица смежности, стек, поиск в глубину. Также научилась применять их для решения задач.