Автор работы: Пользователь скрыл имя, 17 Декабря 2013 в 11:14, курсовая работа
Появление компьютеров стало прорывом для всего человечества. В настоящее время с помощью них возможно производить расчёты с огромной скоростью. Они позволяют решать разнообразные задачи, одной из которых является поиск и составление путей от пункта А в пункт Б. Для таких задач наиболее применима теория графов.
Целью данной курсовой работы является разработка программного продукта для поиска максимально удалённых вершин в графе. Программный продукт должен иметь графический интерфейс и поддерживать любые типы графов.
1. Введение 3
2. Теория графов 4
2.1 Ориентированный граф 5
2.2 Смешанный граф 5
2.3 Изоморфные графы 6
2.4 Прочие связанные определения 6
2.5 Дополнительные характеристики графов 7
2.6 Обобщение понятия графа 8
2.7 Способы представления графа в информатике 9
3. Техническая реализация 11
3.1 Алгоритм поиска пути 11
3.2 Классы и диаграмма классов 11
3.3 Методы класса GraphEdge 13
3.4 Методы класса GraphNode 13
3.5 Функции класса Graph 14
3.6 Методы класса GraphMaxDistanceFinder 18
}3.7 Графический интерфейс 22
4. Заключение 25
5. Список литературы 26
break;
default:
g.DrawImage(graph.imgNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
}
g.DrawString((i + 1).ToString(), graph.font, Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);
}
}
}
3. Метод GraphMaxDistanceFinder ищет кратчайший путь между заданными вершинами и возвращает true если путь был найден и false если путь не существует:
class GraphMaxDistanceFinder
{
struct NodesDistanceEntry
{
public int node1, node2;
public int pathLength;
public NodesDistanceEntry(int n1, int n2, int length)
{
node1 = n1;
node2 = n2;
pathLength = length;
}
}
Graph graph;
GraphPathFinder pf;
Image imgFoundNode;
List<NodesDistanceEntry> distanceList;
int maxDistanceInd;
int maxDistanceLength;
public GraphMaxDistanceFinder(ref Graph _graph, string foundNodeImage)
{
graph = _graph;
imgFoundNode = Image.FromFile(foundNodeImage)
pf = new GraphPathFinder(ref graph, foundNodeImage);
distanceList = new List<NodesDistanceEntry>();
maxDistanceInd = -1;
maxDistanceLength = -1;
}
public bool FoundFarestNodes()
{
maxDistanceInd = -1;
maxDistanceLength = -1;
distanceList.Clear();
for (int i = 0; i < graph.nodes.Count - 1; i++)
{
for (int j = i + 1; j < graph.nodes.Count; j++)
{
if (pf.FindPath(i, j))
{
distanceList.Add(new NodesDistanceEntry(i, j, pf.GetPathLength()));
}
}
}
if (distanceList.Count == 0)
return false;
for (int i = 0; i < distanceList.Count; i++)
{
NodesDistanceEntry nde = distanceList[i];
if (maxDistanceLength < nde.pathLength)
{
maxDistanceLength = nde.pathLength;
maxDistanceInd = i;
}
}
return true;
}
public void Draw(ref Graphics g)
{
Pen pen = new Pen(Color.Black, 5);
for (int i = 0; i < graph.edges.Count; i++)
{
Point xFrom, xTo;
int node1, node2;
graph.edges[i].GetLinkedNodes(
xFrom = new Point(graph.nodes[node1].
xTo = new Point(graph.nodes[node2].
g.DrawLine(pen, xFrom, xTo);
}
for (int i = 0; i < graph.nodes.Count; i++)
{
GraphNode node = graph.nodes[i];
if (node.isExists())
{
NODE_TYPE nodeType = NODE_TYPE.NOT_CONNECTED; //0 - Not connected, 1 - OK node, 2 - Path node
if (maxDistanceInd != -1)
{
if (distanceList[maxDistanceInd].
foreach (GraphEdge edge in graph.edges)
{
}
else
nodeType = NODE_TYPE.FOUND;
}
else
{
foreach (GraphEdge edge in graph.edges)
{
int node1, node2;
edge.GetLinkedNodes(out node1, out node2);
if (node1 == i || node2 == i)
{
}
}
}
switch (nodeType)
{
case NODE_TYPE.NOT_CONNECTED:
g.DrawImage(graph.imgNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
case NODE_TYPE.OK:
g.DrawImage(graph.imgOkNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
case NODE_TYPE.FOUND:
g.DrawImage(imgFoundNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
default:
g.DrawImage(graph.imgNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);
break;
}
g.DrawString((i + 1).ToString(), graph.font, Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);
}
}
}
}
Для реализации графического интерфейса были использованы стандартные средства визуального проектирования интерфейса среды разработки Microsoft Visual Studio 2012. Графический интерфейс представляет собой форму (System.Windows.Forms.Form) на которой расположены строка меню и командная панель. На командной панели расположены элементы управления RadioButton для выбора режима редактирования графа и кнопки, необходимые для поиска пути.
Граф отображается на форме с помощью события Paint. Красным цветом обозначены вершины, не имеющие ни одного ребра (не связанные с другими вершинами). Зеленым цветом помечаются вершины, связанные хотя бы с одной другой вершиной. На командной панели имеется выбор различных режимов редактирования графа:
С помощью команд меню, расположенных в пункте меню "Файл" можно создать новый граф, сохранить текущий или загрузить граф из файла.
Результатом курсовой работы является приложение, позволяющее найти максимально удалённые вершины в графе. Программный продукт имеет графический интерфейс и имеет возможность сохранения и загрузки графов. Приложение реализовано с помощью языка программирования Microsoft Visual C#, с использованием среды разработки Microsoft Visual Studio 2012.
Информация о работе Разработка приложения для поиска максимально удалённых вершин в графе