Мой отчёт по лабе 5
.docxМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра ВМиК
Отчёт
по лабораторной работе
«Алгоритм нахождения эйлерового цикла в графе»
Выполнила: студ. гр. МО-201
Фатхутдинова Л.М.
Проверила:
Верхотурова Г.Н.
Уфа - 2012
Постановка задачи
Реализовать алгоритм «нахождение эйлерова цикла» в неориентированном невзвешенном графе.
Входные и выходные данные
Рассмотрим входные и выходные данные, используемые в программе:
-
matrix – матрица смежности.
-
temp_stk – очередь, используемая для хранения смежных вершин при поиске эйлерова цикла.
-
final_eyler_st – список, используемый для хранения результата.
Алгоритм нахождения эйлерового цикла
Пусть данный граф связный, и все его вершины имеют четную степень.
1. Помещаем начальную вершину в стек
2. Начинаем итерационный процесс, на каждом шаге которого выполняются следующие действия:
2.1. Получаем значение вершины стека
2.2. Если у этой вершины есть смежные, тогда заносим первую из них в стек и удаляем соответствующее ей ребро из матрицы смежности и делаем ее начальной. Если же смежных вершин нет, то удаляем исходную вершину из стека и заносим в список.
Процесс завершается, когда очередь становится пустой. Список будет содержать последовательность прохода по эйлерову циклу.
Реализация
private void button4_Click_1(object sender, EventArgs e)
{
Stack<int> final_eyler_st = new Stack<int>(); // стек для результата
Stack<int> temp_stk = new Stack<int>(); // промежуточный стек
bool flg = false;
bool eyler = true;
var matrix = new int[list.CList.Count, list.CList.Count]; // переносим матрицу смежности в двумерн массив
for (int i = 0; i < list.CList.Count; i++)
for (int j = 0; j < list.CList.Count; j++)
if (this.dataGridView1.Rows[i].Cells[j].Value == null)
matrix[i, j] = 0;
else
matrix[i, j] = 1;
flg = false;
int deg = 0;//счетчик степени
for (int i = 0; i < list.CList.Count; i++)
{
for (int j = 0; j < list.CList.Count; j++)
if (matrix[i, j] == 1)
{
deg++; // считаем степень каждой вершины
}
if (deg % 2 != 0 || deg == 0) // если хоть у одной вершины степень нечетная или =0
{
textBox3.Text = "Эйлерова цикла нет";
eyler = false;
break;
}
}
if (eyler == true)
{
temp_stk.Clear();
int V = 1;
int U = 0;
int n = 0;
flg = false;
temp_stk.Push(V);
while (temp_stk.Count != 0)
{
n = temp_stk.Peek();
for (int i = 0; i < list.CList.Count; i++)
if (matrix[n - 1, i] == 1)
{
flg = true;
break;
}
if (flg == true)
{
for (int i = 0; i < list.CList.Count; i++)
if (matrix[n - 1, i] == 1)
{
U = i + 1;
matrix[n - 1, i] = 0;
matrix[i, n - 1] = 0;
break;
}
temp_stk.Push(U);
flg = false;
}
else
{
U = temp_stk.Pop();
final_eyler_st.Push(U);
}
}
}
// вывод результата из f_stk
int nn = final_eyler_st.Count;
for (int i = nn; i > 0; i--)
{
int tmp = final_eyler_st.Pop();
textBox3.Text = textBox3.Text + tmp.ToString() + " ";
}
}
Оценка сложности
Вывод
В ходе лабораторной работы я познакомилась с такими понятиями как неориентированный граф, матрица смежности, стек, поиск в ширину. Также научилась применять их для решения задач.