Навигация
Трассировка по алгоритму Краскала
20569
знаков
8
таблиц
4
изображения
3.2 Трассировка по алгоритму Краскала
Алгоритм Краскала заключается в следующей последовательности:
1) Выписываем все возможные рёбра.
2) Упорядочиваем получившийся список рёбер по длинне.
3) Проводим связь первого ребра из списка.
4) Из списка рёбер выбираем следующее по очереди ребро.
5) Если обе вершины выбраного ребра уже есть в списке проведённых ребер, вычёркиваем это ребро из списка и возвращаемся к п. 4.
Если же одна (и только одна!) из вершин выбраного ребра уже участвует в связи (присутствует как вершина в списке проведённых рёбер), то проводим это ребро, иначе возвращаемся к п. 4.
6) Повторяем пункты 4-5 до тех пор, пока список рёбер не опустеет.
Проведём трассировку цепи питания +5В.
Выпишем список всех возможных рёбер, сразу откидывая ребро, если в списке уже есть ребро с такими же вершинами.
1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9 1-10 1-11 1-12 1-13 1-14
2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10 2-11 2-12 2-13 2-14
3-4 3-5 3-6 3-7 3-8 3-9 3-10 3-11 3-12 3-13 3-14
4-5 4-6 4-7 4-8 4-9 4-10 4-11 4-12 4-13 4-14
5-6 5-7 5-8 5-9 5-10 5-11 5-12 5-13 5-14
6-7 6-8 6-9 6-10 6-11 6-12 6-13 6-14
7-8 7-9 7-10 7-11 7-12 7-13 7-14
8-9 8-10 8-11 8-12 8-13 8-14
9-10 9-11 9-12 9-13 9-14
10-11 10-12 10-13 10-14
11-12 11-13 11-14
12-13 12-14
13-14
Упорядочим этот список в порядке увеличения длинны рёбер. Полученый список запишем построчно:
5-6 6-11 11-12 4-7 7-10 10-13 3-8 8-9 9-14 1-2 2-3 3-4 4-5
7-8 6-7 9-10 10-11 12-13 13-14 5-11 6-12 4-7 7-13 3-9 8-14 2-4
3-5 6-8 9-11 12-14 1-8 1-9 1-14 3-7 5-7 4-6 4-8 6-10 7-11
9-7 8-10 11-13 10-12 10-14 9-13 2-8 2-7 3-6 5-8 8-11 6-9 9-12
11-14 5-10 6-13 4-9 7-14 7-12 4-11 3-10 8-13 2-9 2-14 3-13 4-14
4-12 5-13 1-4 1-7 1-10 1-13 1-5 1-6 2-13 3-11 5-9 8-12 6-14
2-5 2-6 2-11 3-12 5-14 2-12
Проводим первую связь 5-6. Следующее ребро имеющее общую точку – 6-11. Проводим и его. Проводим следующее ребро 11-12.
Следующее проведённое нами ребро 4-5, затем 4-7, 7-10 и 10-13. Теперь 3-4 и 3-8, 8-9 и 9-14.
Затем проводим рёбро 2-3 и наконец 1-8.
Цепь разведена, поскольку все возможные вершины уже присутствуют в списке проведённых рёбер. Рисунок проведённых дорожек приведёна на рис.3.2.
| Å | 5 | Å | Å | 6 | Å | Å | 11 | Å | Å | 12 | Å | ||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | DD10 | Å | Å | DD11 | Å | Å | DD13 | Å | Å | DD12 | Å | ||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | 4 | Å | Å | 7 | Å | Å | 10 | Å | Å | 13 | Å | ||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | DD9 | Å | Å | DD8 | Å | Å | DD6 | Å | Å | DD7 | Å | ||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | 3 | Å | Å | 8 | Å | Å | 9 | Å | Å | 14 | Å | ||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | DD5 | Å | Å | DD2 | Å | Å | DD3 | Å | Å | DD4 | Å | ||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||||||||
| Å | 2 | Å | |||||||||||||||||||||||||||||||
| Å | Å | ||||||||||||||||||||||||||||||||
| Å | Å | ||||||||||||||||||||||||||||||||
| Å | DD1 | Å | |||||||||||||||||||||||||||||||
| Å | Å | ||||||||||||||||||||||||||||||||
| Å | Å | ||||||||||||||||||||||||||||||||
| Å | Å | ||||||||||||||||||||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | ||||||||||||||||||||
Похожие работы
... либо в позициях, указанных разработчиком; 5) максимум числа цепей простой конфигурации. Наибольшее распространение в алгоритмах размещения получил первый критерий, что объясняется следующими причинами: уменьшение длин соединений улучшает электрические характеристики устройства, упрощает трассировку печатных плат; кроме того, он сравнительно прост в реализации. В зависимости от конструкции ...
... - Text Style (Текстовый стиль). В этом диалоговом окне установки такие же, как в программе Symbol Editor. 4 РАЗРАБОТАТЬ КОНТАКТНЫЕ ПЛОЩАДКИ Во всех системах автоматизированного проектирования печатных плат информация о графике контактных площадок содержится отдельно от графики корпуса компонента. Это связано с тем, что при изготовлении фотошаблона требуется обеспечить сопряжение программных ...
... 0 0 0 0 11-12 Разработка электрической схемы пульта проверки 4 5 100 50 12-13 Выбор вариантов конструкции 5 6 100 50 13-14 Расчет параметров конструкции 2 3 70 50 14-15 Разработка печатной платы пульта проверки 7 8 200 180 15-16 Объединение конструкции и платы 7 9 200 150 16-17 Выполнение графической части 8 9 210 170 17-18 Подготовка основной ...
... R2 детали от станка Ст1 к станку Ст2. Но по условию задания система загружена одной деталью. Задание 3. Методы постановки задач и алгоритмы автоматизированного проектирования средств вычислительной техники 3.1 Выбрать схему электрическую принципиальную Выбираем схему Рис.2. Принципиальная электрическая схема устройства 3.2 Провести формализацию и, используя два алгоритма ( ...
0 комментариев