і машини: матриця інцидентності, матриця суміжності, матриця списків суміжності та пов'язані списки суміжності. Вони розрізняються швидкістю виконання операцій над елементами уявлення та об'ємом займаної пам'яті.
Для вирішення поставленої задачі моделювання найбільше підходить уявлення графів в пам'яті машини у вигляді матриці суміжності, а саме матриця ваг.
Матриця суміжності - матриця розміром, елементи якої рівні 1, якщо i-а вершина суміжно з j-ой, і 0 у противному випадку.
Матриця суміжності є симетричною і досить просто може використовуватися для введення та обробки на ЕОМ. Для випадку зваженого графа замість 1 використовується значення вагової функції, і така матриця називається матрицею ваг. У поставленої завданню будемо використовувати матрицю ваг.
1.3 Алгоритм знаходження остова мінімального
ваги у зваженому графі
Для знаходження кістяка мінімальної ваги з допомогою методу Краскала потрібно виконати наступні кроки:
1.Помечают вершину початку побудови кістяка. Серед ребер, інцидентних поміченої вершині, знаходять ребро мінімальної ваги для кістяка. Позначають нову вершину, Інцидентне цьому ребру. Вершина нова, якщо до неї раніше не зверталися. p> 2.Смотрят, чи всі вершини помічені. Якщо так, то закінчують пошук, якщо ні, то переходять до кроку 3. p> 3.Среді ребер, інцидентних позначеним вершин, за винятком ребер остова і ребер, що утворюють в остові цикл, знаходять ребро мінімальної ваги для кістяка. Позначають нову вершину, Інцидентне цьому ребру, і переходять до кроку 2.
4.При зміну вершини початку конфігурація остова мінімального ваги не змінитися. Вона може змінитися за наявності в графі ребер однакового мінімальної ваги.
2 Інструментальні програмні засоби
2.1 Обгрунтування вибору інструментальних засобів
При виборі програмних засобів для розробки програми В«Пошук остова мінімальної ваги у зваженому графі В»необхідно враховувати можливості графічного відображення графа і остову в програмі, визначення модулів в програмі і зв'язки між ними, оцінки розвиненості апарату структур і типів даних, наявність спеціальних функцій здійснення обчислень, можливість збереження проміжних результатів. Крім того, програма повинна дозволяти користувачеві повертатися до попередніх етапів обчислень і зберігати вихідні дані на жорсткому диску.
Облік цих можливостей дозволить реалізувати основні функції розроблюваної програми, зробити її легкодоступною для використання, попередити виникнення логічних помилок, забезпечити надійність програмного забезпечення і його модифицируемость.
Вибір того чи іншого програмного засобу визначається як специфікою розробки програмного забезпечення та його популярністю, так і фінансовими можливостями розробника.
В даний час найбільш поширеною середовищем є Delphi.
Delphi - пакет засобів швидкої розробки додатків. До достої...
