Мой отчёт по лабе 4
.docxМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра ВМиК
Отчёт
по лабораторной работе
«Алгоритм поиска в ширину в графе»
Выполнила: студ. гр. МО-201
Фатхутдинова Л.М.
Проверила:
Верхотурова Г.Н.
Уфа - 2012
Постановка задачи
Реализовать алгоритм «поиск в ширину» в неориентированном невзвешенном графе.
Входные и выходные данные
Рассмотрим входные и выходные данные, используемые в программе:
-
list – список вершин графа.
-
dataGridView1 – матрица смежности.
-
queue – очередь, используемая для хранения смежных вершин при поиске в ширину.
-
lst – список, используемый для хранения результата.
Алгоритм поиска в ширину
1. Помещаем начальную вершину в очередь
2. Начинаем итерационный процесс, на каждом шаге которого выполняются следующие действия:
2.1. Удаляем вершину из очереди
2.2. Проверяем по списку была ли она обработана. Если нет – проводим обработку этой вершины: включаем ее в список и помещаем в очередь все смежные с ней вершины, которых еще нет в списке.
Процесс завершается, когда очередь становится пустой. Список будет содержать список обработанных вершин.
Реализация
private void button3_Click(object sender, EventArgs e)// в ширину
{
lst.Clear();
int tmp = 0;
queue.Enqueue(1);//очередь
for (int j = 1; j < list.CList.Count * 2; j++)
{
tmp = 0;
if (queue.Count > 0)
{
//вытаскиваем элемент из очереди,обрабатываем
int n = queue.Dequeue();
if (n != 0)
{
if (lst.Contains(n))// была ли обработана вершина
tmp = 1;
if (tmp != 1)
{
textBox2.Text = textBox2.Text + n.ToString() + ' ';
lst.Add(n);
// tmp = 0;
}
for (int i = 0; i < list.CList.Count; 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 (flg == true){
queue.Enqueue(i + 1);
}
}
}
}
}
}
}
}
Оценка сложности
Вывод
В ходе лабораторной работы я познакомилась с такими понятиями как неориентированный граф, матрица смежности, стек, поиск в ширину. Также научилась применять их для решения задач.