close

Вход

Забыли?

вход по аккаунту

?

20Фадеев

код для вставкиСкачать
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ им. Р.Е.АЛЕКСЕЕВА
Курсовая работа
по дисциплине
"Информационные технологии"
20 вариант
Выполнил:
студент гр. 27-АСВ
Фадеев А.
Проверил:
Пашковский А.И.
Нижний Новгород
2011
Теория графов
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Ориентированный граф
Ориентированный граф (сокращённо орграф, рис. 3.6) G - это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
* V это непустое множество вершин или узлов,
* A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга - это упорядоченная пара вершин (v, w), где вершину v называют началом, а w - концом дуги. Можно сказать, что дуга ведёт от вершины v к вершине w.
Смешанный граф
Смешанный граф G - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного.
Изоморфный граф
Граф G называется изоморфным графу H, если существует биекция f из множества вершин графа G в множество вершин графа H, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот - если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины f − 1(A) в вершину f − 1(B). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.
Прочие связанные определения
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Ориентированным путём в орграфе называют конечную последовательность вершин vi , для которой все пары (vi,vi + 1) являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких "вырожденных" случаев, вводят следующие понятия.
Архитектура учебного приложения
Архитектура приложения, основана на поведенческом шаблоне MVC. При реализации шаблона MVC обычно используются следующие компоненты.
Model. Этот компонент содержит один или более классов и интерфейсов, отвечающих за обслуживание модели данных. Состояние модели сохраняется в атрибутах и реализации методов. В программе реализован классом MyModel.
View. Классы и интерфейсы представления обеспечивают презентацию данных, хранящихся в компоненте-модели. В программе реализован классом MyView.
Controller. Этот компонент управляет изменениями модели. Он хранит ссылку на компонент-модель, который отвечает за осуществление изменений, и сам в свою очередь отвечает за вызов одного или нескольких методов обновления. Запрос на изменения может поступать от компонента-представления. В программе контроллер реализован классом MyController.
Внутреннее представление графа в программе
В программе граф хранится в виде двух отдельных структур, хранящих информацию о вершинах и ребрах графа.
Для хранения вершин используется java-коллекция HashSet. Такая структура хранит не повторяющиеся элементы данных, поиск и выборка элементов происходят по значению хеш-функции, что позволяет минимизировать время выборки элемента и сделать его независимым от размерности множества. Хеш-функция вычисляется на основе идентификационного номера вершины, причем алгоритм создания вершины обеспечивает уникальность идентификационного номера. Для хранения ребер графа использована java-коллекция ArrayList. Время доступа к элементу такой структуры линейно зависит от размерности, как и редактирование списка. Структура списка позволяет хранить повторяющиеся элементы, что позволяет оперировать мульти-графами.
Задание
Найти в дереве самое высокое поддерево, имеющее заданное число листьев.
Листинг программы
public class FindSubTreeClass {
private MyEdge mEdge;
LinkedList <MyEdge> edges = MyModel.getModel().getEdges();
LinkedList <MyNode> nodes = MyModel.getModel().getNodes();
public ArrayList <MyNode> findSubTree(int CountList){
ArrayList <MyNode> resultTree;
list<MyNode> list = new LinkedList();
int i=0;
for(MyNode item: nodes)
{
if (nodesNo.find(item)==false)
{
list.add(item);
i++;
mEdge = findEdgeByIdFrom(item.getId());
recursion();
}
}
If (CountList==i)
resultTree = List;
return resultTree;
}
private MyEdge findEdgeByIdFrom(int idFrom){
for(MyEdge item:MyModel.getModel().getEdges()){
if(false == item.isChecked()){
if(item.getOvalFrom().getId() == idFrom){
return item;
}
}
}
return null;
}
private MyEdge findNextEdge(MyEdge edge){
for(MyEdge item:MyModel.getModel().getEdges()){
if(false == item.isChecked()){
if(edge.getOvalTo().equals(item.getOvalFrom())){
if(false == item.isSorted()){
return item;
}
}
}
}
return null;
}
}
private void recursion(){
if(mResult == true){
return;
}
System.out.println(Arrays.toString(mList.toArray()));
MyEdge edge = findEdgeByIdFrom(mList.get(mList.size()-1).getOvalTo().getId());
if(null == edge){
if(mList.size()>1){
MyEdge deleted = mList.removeLast();
deleted.setChecked(true);
recursion();
} else {
return;
}
} else {
if(edge.getOvalTo().getId() == mEdge.getOvalFrom().getId()){
mList.addLast(edge);
mResult = true;
return;
} else{
mList.addLast(edge);
recursion();
}
}
}
}
Документ
Категория
Рефераты
Просмотров
14
Размер файла
55 Кб
Теги
20фадеев
1/--страниц
Пожаловаться на содержимое документа