РГР Сиакод новый
.docxФедеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Уфимский государственный авиационный технический университет»
Кафедра Вычислительной математики и кибернетики
Отчет по расчётно-графической работе
по дисциплине:
”Структуры и алгоритмы компьютерной обработки данных”
Вариант №11
Выполнил: студентка группы
Проверила:
Верхотурова Г.Н.
УФА 2020
1. Цель и постановка задачи
Цель работы: углубленное изучение структур данных и алгоритмов.
Постановка задачи: разработать алгоритм для определения двудольности графа
2. Теоретические основы
Графы являются обобщенными иерархическими структурами. Граф состоит из множества элементов данных, называемых вершинами, и множества ребер, соединяющих эти вершины попарно. Граф будем обозначать G = < V, E > , где V — множество вершин, E — множество ребер.
Рис.1 Граф
Двудольный граф — это граф, вершины которого можно разделить на два независимых множества U и V, так что каждое ребро (u, v) либо соединяет вершину из U в V, либо вершину из V в U. Другими словами, для каждого ребра (u, v) либо u принадлежит U, а v — V, либо u принадлежит V, а v — U. Можно также сказать, что не существует ребра, соединяющего вершины одного и того же набора.
Двухсторонний граф возможен, если раскраска графа возможна с использованием двух цветов, так что вершины в наборе окрашены в один и тот же цвет.
3.Идея алгоритма
Алгоритм, позволяющий определить, является ли данный граф двудольным или нет, используя поиск в ширину (BFS). 1. Присвойте КРАСНЫЙ цвет исходной вершине (поместив в набор U). 2. Раскрасьте всех соседей синим цветом (добавив в набор V). 3. Раскрасьте соседа всех соседей КРАСНЫМ цветом (добавив в набор U). 4. Таким образом, присвойте цвет всем вершинам так, чтобы он удовлетворял всем ограничениям задачи раскраски m-путей, где m = 2. 5. При назначении цветов, если мы найдем соседа, который окрашен в тот же цвет, что и текущая вершина, то график не может быть раскрашен двумя вершинами (или график не является двудольным)
4. Входные данные
Вершина является объектом класса Vertex, где находится информация о координатах вершины.
Ребро является объектом класса Edge, где находится информация о начальной и конечной вершине.
int[,] AMatrix -матрица смежности.
5. Промежуточные данные
class Vertex: Объектами этого класса являются вершины графа. Содержит конструктор с параметром.
class Vertex{
public int x, y; //координаты точки
public Vertex(int x, int y)
{
this.x = x;
this.y = y;
}}
class Edge: объектом класса является начальная и конечная вершина, которые соединены ребром. Аналогичен с классом Vertex.
class Edge
{
public int v1, v2;
public Edge(int v1, int v2)
{
this.v1 = v1;
this.v2 = v2;
}}
6. Выходные данные
Bool flag- переменная логического типа, в зависимости от ее значения выводится сообщение на экран двудольный граф или нет.
7. Основная программа
Функция заполнения матрицы смежности, параметры которой являются numberV – количество вершин, List<Edge> E -список ребер и сама матрица.
public void fillAdjacencyMatrix(int numberV, List<Edge> E, int[,] matrix)
{
for (int i = 0; i < numberV; i++)
for (int j = 0; j < numberV; j++)
matrix[i, j] = 0;
for (int i = 0; i < E.Count; i++)
{
matrix[E[i].v1, E[i].v2] = 1;
matrix[E[i].v2, E[i].v1] = 1;
}
}
Функция проверки на двудольность, параметры которой являются матрица смежности и номер вершины, с которой хотим начать. В данной программе обработка матрицы начинается с 0 вершины.
private bool isBipartite(int[,] Gr, int src)
{
int b = V.Count;
// Создаем массив цветов для хранения
// цвета назначены всем вершинам.
// Номер вершины используется в качестве индекса
// в этом массиве. Значение «-1»
// of colorArr [i] используется для указания
// что цвет не назначен
// для вершины 'i'. Значение 1
// используется для обозначения первого цвета
// назначено и значение 0 указывает
// второй цвет назначен.
int[] colorArr = new int[b];
for (int i = 0; i < b; ++i)
colorArr[i] = -1;
// Назначаем первый цвет источнику
colorArr[src] = 1;
// Создать очередь (FIFO) номеров вершин
// и ставим исходную вершину в очередь для обхода BFS
List<int> q = new List<int>();
q.Add(src);
// Выполнить, пока есть вершины
// в очереди (аналогично BFS)
while (q.Count != 0)
{
// Удаление вершины из очереди
int u = q[0];
q.RemoveAt(0);
// Возвращаем false, если есть цикл
if (Gr[u, u] == 1)
return false;
// Найти все неокрашенные смежные вершины
for (int v = 0; v < b; ++v)
{
// существует ребро от u до v
// и пункт назначения v не окрашен
if (Gr[u, v] == 1 && colorArr[v] == -1)
{
// Назначаем альтернативный цвет
// к этому соседнему v из вас
colorArr[v] = 1 - colorArr[u];
if (colorArr[v]==0)
G.drawSelectedVertex2(V[v].x, V[v].y, (v + 1).ToString()); //окрашивает в желтый
q.Add(v);
}
// существует ребро от u до v и
// место назначения v окрашено
// того же цвета, что и вы
else if (Gr[u, v] == 1 &&
colorArr[v] == colorArr[u]){
G.drawSelectedVertex1(V[v].x, V[v].y,(v+1).ToString());// окрашивает в розовый
return false;
}
}
}
// Если мы достигаем здесь, то все смежные вершины
// может быть окрашен альтернативным цветом
return true;
}
bool flag= isBipartite(AMatrix, 0);
if (flag)
{
MessageBox.Show("Граф двудольный!");
}
else
{
MessageBox.Show("Граф НЕ двудольный!");
}
8. Оценка сложности алгоритма
В описанном алгоритме, где используется поиск в ширину, посещение каждой вершины требует времени вычислений O(n). При добавлении вершины в список обработанных вершин для обнаружения смежных с ней вершин проверяется строка матрицы смежности. Каждая строка - это O(n), следовательно, общее время вычислений равно n *O(n)= O(n^2 ).
9. Работа программы
Пользователь нажимает значок для рисования вершин и рисует вершины графа кликом по PictureBox.
Пользователь нажимает кнопку рисования ребер и, выделяя кликом вершины, рисует ребро между вершинами, которые выбрал пользователь.
Когда граф отрисован, нажатием кнопки создания матрицы смежности создается матрица и выводится в таблицу.
Появляется сообщение о двудольности или НЕ двудольности графа.
Также пользователь может удалить вершины и ребра, нажав на кнопку удаления.
Также пользователь может стереть весь граф полностью.
Процесс и результат работы программы можно видеть на приложенных скринах.
Рис.1 Отрисовка графа
Рис.2 Вывод матрицы смежности
Рис.3 Результат работы программы
Рис.4 Результат работы программы