Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритми побудови дерев
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2015
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національній університет "Львівська політехніка"
/
Алгоритми побудови дерев
Звіт
до лабораторної роботи №1
з курсу "Дискретні моделі в САПР"
1.Мета роботи: вивчення алгоритмів рішення задач побудови остових дерев.
2.Короткі теоретичні відомості.
Для того, щоб розглянути алгоритми побудови дерев нагадаємо деякі основні положення теорії графів. Графом G називають скінчену множину V з нерефлексивним симетричним відношенням R на V. Визначим E як множину симетричних пар в R. Кожний елемент V називають вершиною. Кожний елемент Е називають ребром, а E множиною ребер G. Граф називається зв’язним, якщо в ньому для будь-якої пари вершин знайдеться ланцюг, який їх з’єднує, тобто, якщо по ребрах (дугах) можна попасти з будь-якої вершини в іншу. Цикл - це ланцюг, в якого початкова і кінцева точки співпадають. Дерево - це зв’язний граф без циклів.Лісом називається будь-яка сукупність дуг (ребер) інцидентних до вершин, які не містять циклів. Таким чином, ліс складається з одного або більше дерев. Остовним деревом графа називається будь-яке дерево, яке утворене
сукупністю дуг, які включають всі вершини графа. В графі, який показано на рис.1, сукупність дуг утворює остовне дерево, так як вона включає всі вершини даного графа а,b,c,d. Будь-який зв’язний граф має остовне дерево. Коренем орієнтованого дерева (прадерева) називається його вершина, в
яку не входить жодна з дуг. Орієнтований ліс визначається як звичайний, тільки складається не з
простих дерев, а орієнтованих. Остовним орієнтованим деревом називається орієнтоване дерево, яке одночасно є і остовим деревом. Остовним орієнтованим лісом називається орієнтований ліс, який включає всі вершини відповідного графа. Вага дерева - це сума ваг його ребер. Поставимо у відповідність кожній дузі (х,у) графа G вагу а(х,у). Вага орієнтованого лісу (або орієнтованого дерева) визначається як сума ваг дуг, що входять в даний ліс (дерево). Максимальним орієнтованим лісом графа G називається орієнтований ліс графа G з максимально можливою вагою. Максимальним орієнтованим деревом графа G називається орієнтоване дерево графа G з максимально можливою вагою. Мінімальні орієнтовані ліс і дерево визначаються аналогічним чином.
Алгоритм Борувки.
Це алгоритм знаходження мінімального остового дерева в графі. Вперше був опублікований в 1926 році Отакаром Борувкой, як метод знаходження оптимальної електричної мережі в Моравії. Робота алгоритму складається з декількох ітерацій, кожна з яких полягає в послідовному додаванні
ребер до остового лісу графа, до тих пір, поки ліс не перетвориться на дерево, тобто, ліс, що складається з однієї компоненти зв'язності. У псевдокоді, алгоритм можна описати так: Спочатку, нехай T - порожня множина ребер (представляє собою остовий ліс, до якого кожна вершина входить в якості окремого дерева). Поки T не є деревом (поки число ребер у T менше, ніж V-1, де V -кількість вершин у графі): Для кожної компоненти зв'язності (тобто, дерева в остовому лісі) в підпункті з ребрами T, знайдемо ребро найменшої ваги, що зв'язує цю компоненту з деякої іншої компонентою зв'язності. (Передбачається, що ваги ребер різні, або як-то додатково впорядковані так, щоб завжди можна було знайти єдине ребро з мінімальною вагою). Додамо всі знайдені ребра в множину T.Отримана множина ребер T є мінімальним остовим деревом вхідногографа.
3.Результати виконання.
Варіант 9. Алгоритм Борувки.
Рис.1. Початковий граф. Рис.2. Знаходження безпечних ребер для кожної вершини.
Рис.3. Додавання безпечних ребер до МОЛ. Рис.4. знаходження безпечних ребер для вершин.
/
Рис.5. МОД = 71.
Текст програми на мові Java: public class BoruvkaAlg { static int verA, verB, edgeWeight; //Вершина 1,2 і вага ребра між ними static int weightArray[][] ; //Масив для збереження ваг між static int passedVertices[]; //Пройдені вершини static int currentVertices[]; //Поточна вершина static int currentEdgeWeight[] ; //Вартість поточної вершини static int verticesCount, edgesCount; //Кількість вершин і ребер static int currentVer, totalVer, minWeight; public static void main(String args[]) throws IOException { BoruvkaAlg br = new BoruvkaAlg(); br.printHelp(); br.inputSizes(); br.initArrays(); br.inputData(); br.calculateMST(); br.printMST(); } /* Зчитування розмірів графа */ void inputSizes() { Scanner scan = new Scanner(System.in); System.out.print("Введіть кількість вершин і ребер через пробіл: "); verticesCount = scan.nextInt(); edgesCount = scan.nextInt(); System.out.println(); } /* Введення ваг графа */ void inputData() { Scanner in = new Scanner(System.in); for (int i = 1; i <= edgesCount; i++) { System.out.print("Введіть номери вершин і вагу ребра між ними через пробіл: "); verA=in.nextInt(); verB=in.nextInt(); edgeWeight =in.nextInt(); weightArray[verA][verB] = weightArray[verB][verA] = edgeWeight; } System.out.println(); } /* Обчислення МОД */ void calculateMST() { /* Стартові дані для початку роботи алгоритму */ currentVer = 0; currentEdgeWeight[currentVer] = 0; totalVer = 0; passedVertices[currentVer] = 1; while( totalVer != verticesCount) //Доки не пройдено всі вершини { /* Знаходження безпечних ребер */ for (int i = 1; i <= verticesCount; i++) { if ( weightArray[currentVer][i] != 0) { if( passedVertices[i] == 0) { if (currentEdgeWeight[i] > weightArray[currentVer][i]) { currentEdgeWeight[i] = weightArray[currentVer][i]; } } } } minWeight = Integer.MAX_VALUE; //Додвання ребер в МОЛ for (int i = 1 ; i <= verticesCount; i++) { if (passedVertices[i] == 0) { if (currentEdgeWeight[i] < minWeight) { minWeight = currentEdgeWeight[i]; } } } passedVertices[currentVer]=1;//1 - вершина відвідана,0 - невідвідана passedVertices[i] == 0 totalVer++; //Наступна вершина } //Обчислення кінцевої вваги minWeight =0; for(int i=1;i<= verticesCount;i++) minWeight = minWeight + currentEdgeWeight[i]; } /* Вивід результату */ void printMST() { System.out.println("Мінімальна вага становить: " + minWeight); System.out.println("Мінімальне остове дерево:"); for(int i=2; i<= verticesCount;i++) System.out.println("Вершина " + i + " з'єднана з вершиною " + currentVertices[i]); }}
Результат виконання:
***HELP***
1. Кількість вершин повинна бути >1!
2. Нумерація вершин починається з 1 з інкрементом в 1 (1,2,3...) !
3. Максимальна сума ваг повинна бути не більшою за розмір типу Integer = 2147483647!
Введіть кількість вершин і ребер через пробіл: 8 10
Введіть номери вершин і вагу ребра між ними через пробіл: 1 2 6
Введіть номери вершин і вагу ребра між ними через пробіл: 2 3 19
Введіть номери вершин і вагу ребра між ними через пробіл: 3 4 9
Введіть номери вершин і вагу ребра між ними через пробіл: 4 5 14
Введіть номери вершин і вагу ребра між ними через пробіл: 5 6 21
Введіть номери вершин і вагу ребра між ними через пробіл: 5 7 2
Введіть номери вершин і вагу ребра між ними через пробіл: 7 8 8
Введіть номери вершин і вагу ребра між ними через пробіл: 8 1 12
Введіть номери вершин і вагу ребра між ними через пробіл: 1 7 11
Введіть номери вершин і вагу ребра між ними через пробіл: 2 7 15
Мінімальна вага становить: 71
Мінімальне остове дерево:
Вершина 2 з'єднана з вершиною 1
Вершина 3 з'єднана з вершиною 4
Вершина 4 з'єднана з вершиною 5
Вершина 5 з'єднана з вершиною 7
Вершина 6 з'єднана з вершиною 5
Вершина 7 з'єднана з вершиною 1
Вершина 8 з'єднана з вершиною 7
Висновок: в процесі виконання лабораторної роботи я вивчив алгоритми рішення задач побудови остових дерев та написав програму для знаходження МОД з допомогою алгоритму Борувки.
14.05.2016 10:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора