МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ
ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ П. О. СУХОГО
Факультет автоматизированных и информационных систем
Кафедра «Информационные технологии»
ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ № 2
по дисциплине «Конструирование программ и языки программирования»
на тему: «Алгоритмы обхода графа»
Выполнила: студентка гр. ИТ-32
Принял:
Дата сдачи отчета: _____________________
Дата допуска к защите: _____________________
Дата защиты: _____________________
Гомель 2013
Цель: Изучение основных алгоритмов обхода графа.
Задание:
1. Для неориентированного графа сохранить его в виде списка смежности.
2. Предусмотреть возможность добавления в граф связей, удаления ребер и вершин.
3. Построить алгоритмы обхода графа в глубину(DFS рекурсивный и нерекурсивный ) и в ширину (BFS). Для каждого из алгоритмов вывести порядок обхода графа.
Вариант 11,23.
Количество вершин 8 , количество связей 10.
3 -> 4
1 -> 5
2 -> 1
1 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Листинг программы:
Form1.cs :
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
}
private void button1_Click(object sender, EventArgs e)
{
if (GraphTravel.Valid(textBox1.Text) && GraphTravel.Valid(textBox2.Text))
{
GraphTravel.AddRoot(Convert.ToInt32(textBox1.Text), Convert.ToInt32(textBox2.Text));
MessageBox.Show("Добавлено", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Information);
}
else
MessageBox.Show("Введены некорректные данные", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Error);
textBox1.Text = "";
textBox2.Text = "";
}
private void button2_Click(object sender, EventArgs e)
{
if (GraphTravel.Valid(textBox3.Text))
if (GraphTravel.DelRoot(Convert.ToInt32(textBox3.Text)))
MessageBox.Show("Удалено", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Information);
else
MessageBox.Show("Узел не найден", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Error);
else
MessageBox.Show("Введены некорректные данные", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Error);
textBox3.Text = "";
}
private void button4_Click(object sender, EventArgs e)
{
if (comboBox1.SelectedIndex != -1)
{
richTextBox1.Text = "Резульат обхода графа\r\n--------------------------------\r\n\r\n";
}
switch (comboBox1.SelectedIndex)
{
case 0:
{
if (GraphTravel.Valid(textBox6.Text))
richTextBox1.Text += GraphTravel.TravelWide(Convert.ToInt32(textBox6.Text));
}
break;
case 1:
{
if (GraphTravel.Valid(textBox6.Text))
richTextBox1.Text += GraphTravel.TravelDeep(Convert.ToInt32(textBox6.Text));
}
break;
}
}
private void button3_Click(object sender, EventArgs e)
{
if (GraphTravel.Valid(textBox4.Text) && GraphTravel.Valid(textBox5.Text))
if (GraphTravel.DelLink(Convert.ToInt32(textBox4.Text), Convert.ToInt32(textBox5.Text)))
MessageBox.Show("Удалено", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Information);
else
MessageBox.Show("Связь не найдена", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Error);
else
MessageBox.Show("Введены некорректные данные", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Error);
textBox4.Text = "";
textBox5.Text = "";
}
}
GraphTravel :
class GraphTravel
{
/// <summary>
/// Список узлов графа
/// </summary>
public static List<Graph> CurentGraph = new List<Graph>();
/// <summary>
/// Очередь для обхода в ширину
/// </summary>
public static Queue<Graph> queue = new Queue<Graph>();
/// <summary>
/// Стек для обхода в глубину
/// </summary>
public static Stack<Graph> stack = new Stack<Graph>();
/// <summary>
/// Добавление узла графа или связи между узлами
/// </summary>
/// <param name="root"></param>
/// <param name="branch"></param>
/// <returns></returns>
public static bool AddRoot(int root, int branch)
{
bool result = false; // Результат добавления
Graph temp1 = new Graph(); // Первый временный узел графа
temp1.Root = root;
temp1.Branch.Add(branch);
temp1.Use = false;
Graph temp2 = new Graph(); // Второй временный узел графа
temp2.Root = branch;
temp2.Branch.Add(root);
temp2.Use = false;
bool isbranch1 = false; // Есть ли у узла root связь с узлом branch
bool isbranch2 = false; // Есть ли у узла branch связь с узлом root
bool isroot1 = false; // Есть ли узел root
bool isroot2 = false; // Есть ли узел branch
int i1 = -1, i2 = -1;
for (int i = 0; i < CurentGraph.Count; i++)
if (CurentGraph[i].Root == root) // Проверяем, есть ли узел root
{
i1 = i;
isroot1 = true;
for (int j = 0; j < CurentGraph[i].Branch.Count; j++)
if (CurentGraph[i].Branch[j] == branch) // Проверям есть ли у узла root связь с узлом branch
isbranch1 = true;
}
for (int i = 0; i < CurentGraph.Count; i++)
if (CurentGraph[i].Root == branch) // Проверяем, есть ли узел branch
{
i2 = i;
isroot2 = true;
for (int j = 0; j < CurentGraph[i].Branch.Count; j++)
if (CurentGraph[i].Branch[j] == root) // Проверям есть ли у узла branch связь с узлом root
isbranch2 = true;
}
if (isbranch1 && isbranch2) // Если есть узел root со связью с branch и узел branch со связью с root
result = false; // Данная связь или узел уже существуют
else
{
if (isroot1 && isroot2) // Если существуют узлы root и branch но у них нет связи друг с другом
{
CurentGraph[i1].Branch.Add(branch); // то добавляем связь с branch
CurentGraph[i2].Branch.Add(root); // то добавляем связь с root
}
if (isroot1 && !isroot2) // Если узел root существует а узел branch нет
{
CurentGraph[i1].Branch.Add(branch); // Добавляем связь с branch
CurentGraph.Add(temp2); // Создаём узел branch
result = true;
}
if (!isroot1 && isroot2) // Если узел branch существует а узел root нет
{
CurentGraph[i2].Branch.Add(root); // Добавляем связь с root
CurentGraph.Add(temp1); // Создаём узел root
result = true;
}
if (!isroot1 && !isroot2) // Если узлов branch и root не существует
{
CurentGraph.Add(temp1); // Создаём узел root
CurentGraph.Add(temp2); // Создаём узел branch
result = true;
}
}
return result;
}
/// <summary>
/// Удаление узла
/// </summary>
/// <param name="root"></param>
public static bool DelRoot(int root)
{
bool result = false;
for (int i = 0; i < CurentGraph.Count; i++)
if (CurentGraph[i].Root == root) // Ищем узел root и удаляем его
{
CurentGraph.RemoveAt(i);
result = true;
}
for (int i = 0; i < CurentGraph.Count; i++)
for (int j = 0; j < CurentGraph[i].Branch.Count; j++)
if (CurentGraph[i].Branch[j] == root) // Ищем связи с узлом root и удаляем их
{
CurentGraph[i].Branch.RemoveAt(j);
result = true;
}
return result;
}
/// <summary>
/// Удаление связи
/// </summary>
/// <param name="root">первый узел</param>
/// <param name="brench">второй узел</param>
public static bool DelLink(int root, int branch)
{
bool result = false;
for (int i = 0; i < CurentGraph.Count; i++)
{
if (CurentGraph[i].Root == root) // Ищем узел root и удаляем у него связь с branch
for (int j = 0; j < CurentGraph[i].Branch.Count; j++)
if (CurentGraph[i].Branch[j] == branch)
{
CurentGraph[i].Branch.RemoveAt(j);
result = true;
}
if (CurentGraph[i].Root == branch) // Ищем узел branch и удаляем у него связь с root
for (int j = 0; j < CurentGraph[i].Branch.Count; j++)
if (CurentGraph[i].Branch[j] == root)
{
CurentGraph[i].Branch.RemoveAt(j);
result = true;
}
}
return result;
}
/// <summary>
/// Обход в ширину
/// </summary>
/// <param name="root">начальный узел</param>
/// <returns></returns>
public static string TravelWide(int root)
{
for (int i = 0; i < CurentGraph.Count; i++)
CurentGraph[i].Use = false;
string way = "";
for (int i = 0; i < CurentGraph.Count; i++)
if (CurentGraph[i].Root == root)
{
queue.Enqueue(CurentGraph[i]);
break;
}
Wide(ref way);
return way;
}
/// <summary>
/// Проход по узлам в ширину
/// </summary>
/// <param name="way">путь прохождения</param>
public static void Wide(ref string way)
{
if (queue.Count != 0)
{
Graph temp = queue.Dequeue();
way += Convert.ToString(temp.Root) + "->";
for (int i = 0; i < CurentGraph.Count; i++)
{
for (int j = 0; j < temp.Branch.Count; j++)
if (CurentGraph[i].Root == temp.Branch[j] && CurentGraph[i].Use == false)
queue.Enqueue(CurentGraph[i]);
if (CurentGraph[i].Root == temp.Root)
CurentGraph[i].Use = true;
}
Wide(ref way);
}
}
/// <summary>
/// Обход в глубину
/// </summary>
/// <param name="root">начальный узел</param>
/// <returns></returns>
public static string TravelDeep(int root)
{
for (int i = 0; i < CurentGraph.Count; i++)
CurentGraph[i].Use = false;
string way = "";
for (int i = 0; i < CurentGraph.Count; i++)
if (CurentGraph[i].Root == root)
{
stack.Push(CurentGraph[i]);
break;
}
Deep(ref way);
return way;
}
/// <summary>
/// Проход по узлам в глубину
/// </summary>
/// <param name="way">путь прохождения</param>
public static void Deep(ref string way)
{
if (stack.Count != 0)
{
Graph temp = stack.Pop();
way += "->" + Convert.ToString(temp.Root);
for (int i = 0; i < CurentGraph.Count; i++)
{
for (int j = 0; j < temp.Branch.Count; j++)
if (CurentGraph[i].Root == temp.Branch[j] && CurentGraph[i].Use == false)
stack.Push(CurentGraph[i]);
if (CurentGraph[i].Root == temp.Root)
CurentGraph[i].Use = true;
}
Deep(ref way);
}
}
/// <summary>
/// Проверка номера узла на корректнось
/// </summary>
/// <param name="line">входная строка на проверку</param>
/// <returns></returns>
public static bool Valid(string line)
{
bool isStringCorrect = true;
int noumber = 0;
isStringCorrect = Int32.TryParse(line, out noumber);
if (line == "")
isStringCorrect = false;
if (noumber < 0)
isStringCorrect = false;
return isStringCorrect;
}
Graph :
class Graph
{
int _root;
public List<int> Branch = new List<int>();
bool _use;
public int Root
{
get { return _root; }
set { _root = value; }
}
public bool Use
{
get { return _use; }
set { _use = value; }
}
}
Результаты выполнения программы:
Рисунок 1 – Показано добавление новых узлов
Рисунок 2 – Показан обход в глубину
Рисунок 3 – Показан обход в ширину
Выводы: В ходе лабораторной работы мы изучили алгоритмы обхода графа
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.