хід в глибину буде обчислювати довжину найдовшого шляху, в якій дана вершина є «переломною» (і запам'ятовувати найбільшу знайдене значення в деякій глобальної змінної). Потрібно знайти два піддерева з найбільшими довжинами найбільших шляхів, підсумувати ці довжини і додати до них 2 (ребра відданої вершини до вершин, де починаються ці дерева). На наведеному малюнку «переломною» для найдовшого шляху буде вершина, позначена зірочкою, а довжина найдовшого шляху дорівнює 4 + 5 + 2. Складність алгоритму дорівнює складності обходу в глибину і при зберіганні графа списком ребер, що виходять з кожної вершини, досягає O ( N + M), а в дереві, як відомо, M=N? 1, і, тим самим, складність дорівнює O (N).
Недоліком цього методу є те, що шлях можна обчислити тільки від тієї вершини, за яку підвішений граф. Тому для виконання завдання був розглянутий і використаний другий алгоритм.
) Для початку необхідно запустити процедуру обходу графа в глибину. Після виконання цієї дії ми має довжину шляху від кожної однієї вершини до кожної іншої. Потім порівнюємо шляху між усіма парами вершин між собою і знаходимо максимально довгий шлях між двома вершинами.
Переваги алгоритму укладає у швидкості роботи і універсальність його роботи для різних типів графів. Однак, програма вимагає порівняно більше оперативної пам'яті, ніж при використанні першого алгоритму.
2.2 Класи і Діаграма класів
При розробці програмного продукту, були реалізовані наступні класи: GraphNode - реалізує вершину графа;
· GraphEdge - реалізує ребро графа;
· Graph - реалізує роботу з графом (створення/видалення вершин і ребер, отримання інформації про них, графічне відображення графа, його збереження у файл і завантаження з файлу);
· GraphPathFinder - реалізує пошук найкоротшого шляху в графі і графічне відображення графа зі знайденим шляхом.
Діаграма класів:
2.3 Методи класу GraphEdge
. У конструктор класу передаються індекси вершин, пов'язаних даними руба:
public GraphEdge (int n1, int n2)
node1=n1;
node2=n2;
2. GetLinkedNodes - встановлює значення переданих в метод параметрів, відповідно до індексів вершин, пов'язаних даними руба:
public void GetLinkedNodes (out int n1, out int n2)
{
n1=node1;
n2=node2;
}
2.4 Методи класу GraphNode
. У конструктор класу передаються координати вершини, по?? оторая дана вершина буде відображатися на формі, а також, необов'язковий параметр, що відповідає за видимість вершини на формі (за замовчуванням, вершина буде видимою):
public GraphNode (int _x, int _y, bool _isValide=true)
{
x=_x;
y=_y;
isValide=_isValide;
}
. Методи GetPostionX і GetPositionY повертають X і Y координати вершини відповідно:
public int GetPositionX ()
{
return x;
} int GetPositionY ()
{
return y;
}
. Метод IsExists повертає видимість вершини:
public bool isExists ()
{
return isValide;
}
. Метод Remove видаляє вершину (встановлює координати рівними - 1, а також встановлює видимість вершини в false):
public void Remove ()
{
x=- 1;
y=- 1;
isValide=false;
}
2.5 Функції класу Graph
. У конструктор класу передаються імена файлів зображень для вершин. Конструктор ініціалізує списки з вершин і ребер, потім викликається функція LoadResources:
public Graph (string nodeImage, string nodeOkImage)
{
nodes=new List lt; GraphNode gt; ();
edges=new List lt; GraphEdge gt; ();
LoadResources (nodeImage, nodeOkImage);
}
. Метод Clear відповідає за очищенн...
