Работа с графами, C#

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Цели и задачи

Цель: научиться работать с графами, научиться представлять их в неграфическом виде и проводить операции с ними.

Задача: написать программу, позволяющую задавать в ней произвольный граф, вводить его описание с клавиатуры, отображать граф на экране и в файле, реализовать один из алгоритмов при работе с графом и решить прикладную задачу, связанную с графами.

Для каждого пункта («Реализация отображения и задачи графа», «Реализация алгоритма работы с графом», «Решение прикладной задачи») имеются листинг программы и результаты работы программы. Они находятся в соответствующих разделах.

Реализация отображения и задачи графа

Сама программа была написана на языке C# с использованием стандартных библиотек языка.

Граф задавался вводимым количеством вершин и последующим заданием дуг. Задавая количество вершин, в компоненте dataGridView создавалась матрица размером nЧn, где n - это количество вершин. Эта матрица является матрицей смежности создаваемого графа. При задаче дуги можно выбрать с помощью компонентов comboBox номера существующих вершин, определить вес дуги, а так же выбрать, однонаправленной дуга будет или двунаправленной. Как только дуга была создана, в матрице смежности отмечалась связь вершин в определенной ее ячейке. Так же в двух компонентах listBox выводилось представление графа в виде пар вершин и списков вершин: (номер_исх_верш, номер_кон_верш, вес) направленность_дуги и номер_исх_верш: (номер_кон1, вес), (номер_кон2, вес)…

В программе предусмотрено сохранение описание графа и его загрузка. Для этого в меню, задаваемом компонентой menuStrip, существуют соответствующие кнопки. При сохранении используется диалог saveFileDialog, в котором задается имя и расположение файла, который посредством потока FileStream открывается и в который потоком StreamWriter записывается описание графа. Сначала записывается количество вершин графа. После чего описание дуг считывается из компонента listBox, в котором граф представлен в виде пар вершин.

При загрузке происходит схожая процедура: используется openFileDialog, потоки FileStream и StreamReader. Количество вершин, считанное из файла, заносится в соответствующее поле, после чего активируется кнопка «Создать новый граф», задаются его вершины. При задаче дуг, номера исходных и конечных вершин, а так же вес дуги, считанные из файла, вносятся в соответствующие поля, и на основании значения параметра направленность_дуги строится либо однонаправленная, либо двунаправленная дуга.

Реализация алгоритма работы с графом

Я выбрал для разработки и реализации алгоритм проверки двудольности Двудомльный граф или биграмф -- это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. графа. Для этого я проводил поиск в глубину из каждой вершины, начиная с нулевой. Чтоб осуществить поиск в глубину, я пользовался поиском по матрице смежности графа: я шел по строке i, и если находил ячейку [i , j] со значением «1» (то есть между вершинами i и j существует дуга), я смотрел, к какой доле отнесена вершина j. Если она не находится ни в какой доле, я относил ее к доле, отличной от доли i и рекурсивно начинал поиск из нее, то есть начинал идти по строке j и так далее. Если вершина j отнесена к доле, отличной от доли i, то это значит, что эту вершину я уже проходил и я пропускал ее. Если вершина j отнесена к той же доле, что и вершина i, то это означало, что вершины i и j связаны дугой, что противоречит определению двудольности, из чего следовало, что граф не двудольный и поиск прекращался.

Для отметки, в какой доле находится вершина, был создан массив int[] cell. Отметка выглядела как cell[номер_верш] = доля.

Решение прикладной задачи

Для решения я выбрал задачу №7. Ее условия:

В некотором городе есть метро, состоящее из N станций и M линий, соединяющих их. Каждая линия обеспечивает проезд между какими-то двумя станциями в обе стороны. Между любой парой станций проведено не более одной линии. Сеть метро построена таким образом, чтобы от каждой станции можно было проехать на каждую (возможно, через промежуточные станции). назовем это свойство связностью метро.

Из-за изобретения принципиально нового вида транспорта метро стало убыточным, и его работу решили прекратить. На заседании мэрии города было постановлено закрывать каждый год по одной станции, но так, чтобы связность метро каждый раз сохранялась. При закрытии какой-либо станции линии, ведущие из этой станции в другие, естественно тоже перестают функционировать.

Напишите программу, которая по введенной информации о сети метро разработает порядок закрытия станций, при котором метро всегда будет оставаться связным. программа граф файл экран

Для решения задачи я проводил все тот же поиск в глубину из каждой вершины графа. Граф по умолчанию был связным и все его дуги - двунаправленными. Мы использовали матрицу смежности графа: мы шли по строке i и если находили [i , j] со значением «1», то отмечали, что вершина j уже была просмотрена, заносили ее в очередь на удаление и начинали рекурсивный поиск из нее. Так происходило, пока не будут просмотрены все вершины по всем дугам. После поиска в специальный отдельный компонент listBox выводились в порядке очереди станции на закрытие. Для удобности понимания, они выводились с порядковым номером перед номером станции.

Для отметки того, что вершина (станция) пройдена, использовался массив bool[] check. Отмечалось следующим образом: check[номер_станции] = true/false. Для задачи и сохранения порядка удаления станций использовалась структура стек: Stack<int> del. В него операцией del.Push(i) при поиске вносились номера станций, а после, при составлении списка listBox, операцией del.Pop() станции извлекались. На структуру стек выбор пал из-за его LIFO-свойств, которые в данном случае очень удобны.

Листинг программы

1. Отображение и задача графа.

public Form1()

{

InitializeComponent();

}

ЗАДАНИЕ КОЛИЧЕСТВА ВЕРШИН

private void button1_Click(object sender, EventArgs e)

{

int a = Convert.ToInt32(textBox1.Text);

dataGridView1.Columns.Clear();

listBox1.Items.Clear();

listBox2.Items.Clear();

comboBox1.Items.Clear();

comboBox2.Items.Clear();

listBox3.Items.Clear();

groupBox1.Enabled = true;

button4.Enabled = true;

button5.Enabled = true;

for (int i = 0; i < a; i++)

{

dataGridView1.Columns.Add(Convert.ToString(i),Convert.ToString(i));

dataGridView1.Rows.Add();

dataGridView1.Rows[i].HeaderCell.Value = Convert.ToString(i);

comboBox1.Items.Add(i);

comboBox2.Items.Add(i);

}

for (int i = 0; i < a; i++)

{

for (int j = 0; j < a; j++)

{

dataGridView1[i, j].Value = 0;

}

}

dataGridView1.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells;

}

СОЗДАНИЕ ДВУНАПРАВЛЕННОЙ ДУГИ

private void button2_Click(object sender, EventArgs e)

{

if (textBox2.Text != "")

{

int x = Convert.ToInt32(comboBox1.SelectedItem);

int y = Convert.ToInt32(comboBox2.SelectedItem);

int val = Convert.ToInt32(textBox2.Text);

int cellval = (int)(dataGridView1[x, y].Value);

if (cellval == 0 && x != y)

{

dataGridView1[x, y].Value = 1;

dataGridView1[y, x].Value = 1;

dataGridView1[x, y].Style.BackColor = Color.LightSteelBlue;

dataGridView1[y, x].Style.BackColor = Color.LightSteelBlue;

listBox1.Items.Add((string)("(" + x + "," + y + "," + val + ")"+2));

int check_indexx = listBox2.FindString(comboBox1.SelectedItem + ":");

int check_indexy = listBox2.FindString(comboBox2.SelectedItem + ":");

if (check_indexx == -1)

{

listBox2.Items.Add((string)(x + ":(" + y + "," + val + ")"));

}

else

{

listBox2.Items[check_indexx] = listBox2.Items[check_indexx] + (string)(",(" + y + "," + val + ")");

}

if (check_indexy == -1)

{

listBox2.Items.Add((string)(y + ":(" + x + "," + val + ")"));

}

else

{

listBox2.Items[check_indexy] = listBox2.Items[check_indexy] + (string)(",(" + x + "," + val + ")");

}

}

}

}

Создание однонаправленной дуги (из х в у)

private void button3_Click(object sender, EventArgs e)

{

if (textBox2.Text != "")

{

int x = Convert.ToInt32(comboBox1.SelectedItem);

int y = Convert.ToInt32(comboBox2.SelectedItem);

int val = Convert.ToInt32(textBox2.Text);

int cellval = (int)(dataGridView1[x, y].Value);

if (cellval == 0 && x != y)

{

dataGridView1[x, y].Value = 1;

dataGridView1[x, y].Style.BackColor = Color.LightSteelBlue;

listBox1.Items.Add((string)("(" + x + "," + y + "," + val + ")"+1));

int check_index = listBox2.FindString(comboBox1.SelectedItem + ":");

if (check_index == -1)

{

listBox2.Items.Add((string)(x + ":(" + y + "," + val + ")"));

}

else

{

listBox2.Items[check_index] = listBox2.Items[check_index] + (string)(",(" + y + "," + val + ")");

}

}

}

}

СОХРАНЕНИЕ

private void сохранитьToolStripMenuItem_Click(object sender, EventArgs e)

{

saveFileDialog1.Title = "Сохранить описание графа";

saveFileDialog1.Filter = "Текстовые файлы (*.txt)|*.txt";

if (saveFileDialog1.ShowDialog() == DialogResult.OK)

{

string safname = saveFileDialog1.FileName;

FileStream saveas = new FileStream(saveFileDialog1.FileName, FileMode.OpenOrCreate);

StreamWriter writer = new StreamWriter(saveas, Encoding.Default);

writer.WriteLine(textBox1.Text);

for (int i = 0; i < listBox1.Items.Count; i++)

{

writer.WriteLine(listBox1.Items[i]);

}

writer.Close();

}

}

ЗАГРУЗКА

private void открытьToolStripMenuItem_Click(object sender, EventArgs e)

{

openFileDialog1.Title = "Загрузить описание графа";

openFileDialog1.Filter = "Текстовые файлы (*.txt)|*.txt";

if (openFileDialog1.ShowDialog() == DialogResult.OK)

{

listBox1.Items.Clear();

listBox2.Items.Clear();

comboBox1.Items.Clear();

comboBox2.Items.Clear();

dataGridView1.Columns.Clear();

FileStream load = new FileStream(openFileDialog1.FileName, FileMode.Open);

StreamReader reader = new StreamReader(load, Encoding.Default);

string line;

string[] readchars;

textBox1.Text = reader.ReadLine();

button1_Click(sender, e);

while ((line = reader.ReadLine()) != null)

{

readchars = line.Split('(',',',')');

comboBox1.Text = readchars[1];

comboBox2.Text = readchars[2];

textBox2.Text = readchars[3];

string way = readchars[4];

if (way == "1")

{

button3_Click(sender, e);

}

else

{

if (way == "2")

{

button2_Click(sender, e);

}

}

}

reader.Close();

}

}

2. Реализация алгоритма работы с графом

//Функция проверки графа на двудольность

void twopartcheck(int j, int s, int a, int[] cell)

{

for (int i = 0; i < a; i++)

{

//Поиск в глубину вершины, соединенной с исходной. Если она не отнесена ни к одной доле

if ((int)(dataGridView1[i, j].Value) == 1 && cell[i] == 0)

{

cell[i] = s; //Относим ее к доле, отличной от исходной

s = s * (-1); //Для дальнейшего вызова функции меняем долю

twopartcheck(i, s, a, cell); //Рекурсивный вызов функции из новой вершины, где новая доля - исходная

}

else

{ //Если новая вершина в одной доле с исходной, то граф не двудольный

if ((int)(dataGridView1[i, j].Value) == 1 && cell[i] == s * (-1))

{

//Граф НЕ двудольный

flag = false;

break;

}

}

}

}

Проверка на двудольность

private void button4_Click(object sender, EventArgs e)

{

int a = Convert.ToInt32(textBox1.Text);

int[] cell = new int[a]; //массив принадлежности ячеек к долям

cell[0] = 1; //Нулевая вершина всегда в первой доле

int j = 0; //Исходная вершина всегда нулевая, то есть всегда начинаем с нулевой вершины

int s = -1; //Отметка для отнесения следующей вершины ко второй доле

twopartcheck(j, s, a, cell);

if (flag == true)

{

MessageBox.Show("Граф двудольный!");

}

else

{

MessageBox.Show("Граф НЕ двудольный!");

}

flag = true;

}

3. Решение прикладной задачи

//Функция удаления вершин (станций), учитывающая сохранение связности.

void metrocheck(int k, int a, bool[] check, Stack<int> del)

{

for (int i = 0; i < a; i++) //Идет поиск в глубину и удаление последних найденных элементов

{

if ((int)(dataGridView1[i, k].Value) == 1 && check[i] == false)

{

check[i] = true; //Отмечается, что станция проверена

del.Push(i); //Станции в порядке удаления вносятся в стек

metrocheck(i, a, check, del); //Рекурсивный вызов функции для поиска в глубину

}

}

}

Решение прикладной задачи

private void button5_Click(object sender, EventArgs e)

{

listBox3.Items.Clear();

int a = Convert.ToInt32(textBox1.Text);

bool[] check = new bool[a]; //Для отметок пройденности станций создается массив

Stack<int> del = new Stack<int>(a); //Для создания списка станций на удаление создается стек

int k = 0;

check[0] = true;

del.Push(0);

metrocheck(k, a, check, del);

for (int i = 0; i < a; i++)

{

listBox3.Items.Add(i+1+") "+del.Pop());

}

del.Clear(); //Очистка стека

}



Выводы

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

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



Приложение. Результаты работы программы

Рис. 1.

Рис. 2.

Рис. 3.

Размещено на Allbest.ru