• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Приклад

Оцінка складності.

До початку роботи алгоритму необхідно відсортувати ребра по вазі, це вимагає O(E × log(E)) часу. Після чого компоненти зв'язності зручно зберігати у вигляді системи великих кількостей, що не перетинаються. Усі операції у такому разі займуть O(E × α(E, V)), де α — функція, зворотна до функції Аккермана. Оскільки для будь-яких практичних завдань α(E, V) < 5, те можна прийняти її за константу, таким чином загальний час роботи алгоритму Крускала можна прийняти за O(E * log(E)).

Зображення	Опис
	Ребра ADі CE мають мінімальну вагу, рівну 5. Довільно вибирається ребро AD (виділено на малюнку).
	Тепер найменша вага, рівна 5, має ребро CE. Так додавання CE не утворює циклу, то вибираємо його як друге ребро.
	Аналогічно вибираємо ребро DF, вага якого дорівнює 6.
	Наступні ребра - AB і BE з вагою 7. Довільно вибирається ребро AB, виділене на малюнку. Ребро BD виділене червоним, так вже існує шлях (зелений) між B і D, тому, якби це ребро було вибране, то утворився б цикл ABD.
	Аналогічним чином вибирається ребро BE, вага якого дорівнює 7. На цьому етапі червоним виділено значно більше ребер: BC, тому що утворюється цикл BCE, DE, тому що створиться цикл DEBA, і FE, тому що сформується цикл FEBAD.
	Алгоритм завершується додаванням ребра EG з вагою 9. Мінімальне кістякове дерево побудоване.

Читайте також:

1. Абсолютні синоніми (наприклад, власне мовні й запозичені) в одному тексті ділового стилю вживати не рекомендується.
2. Алгоритм однофакторного дисперсійного аналізу за Фішером. Приклад
3. Базові та прикладні класифікації
4. В чому полягає явище тунелювання через потенціальний бар’єр, наведіть приклади.
5. Визначення і приклади
6. Врахування витраті втрат електроенергії. Приклад складання електробалансу.
7. Головною метою наукової діяльності в системі вищої освіти повинен стати розвиток фундаментальних та приклад­них досліджень.
8. Деякі приклади застосування ППП
9. Дієслова з префіксом дис-виражають значення ліквідації дії, названої безпрефіксним дієсловом, наприклад: гармонізувати – дисгармонізувати, асоціювати – дисасоціювати.
10. Для одиничного і дрібносерійного виробництва норма витрати визначається як укрупнена, наприклад, на 1000 станко-годин роботи даного виду роботи устаткування
11. Додаток И - Приклад виконання ремонтного креслення деталі
12. Етикет – (прикріплювати) установлений порядок поведінки в товаристві, певному оточенні, наприклад, придворний етикет, дипломатичний етикет.

Переглядів: 521