 |
Нахождение минимального остовного дерева
|
|
|
|
Имеется информация о расстояниях между парой домов в определённом населённом пункте. Для подключения всех домов к системе кабельного телевидения требуется найти схему прокладки кабеля. При которой общая протяженность всех участков будет минимальной. Эта задача является задачей нахождения минимального остовного дерева. В процессе решения будем последовательно отбирать рёбра графа для включения в искомое минимальное остовное дерево.
На предварительном этапе:
· составляем список всех ребер графа в порядке возрастания;
· формируем предварительный список ребер, составляющих минимальное остовное дерево (на начальном этапе этот список пуст).
Первый шаг алгоритма. Из списка всех ребер графа выбираем ребро с минимальной длиной.
Второй шаг. Если выбранное ребро образует цикл с какими-либо ребрами, включенными ранее в предварительный список ребер, которые составляют минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и снова переходим к первому шагу алгоритма.
Если выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, которые составляют минимальное остовное дерево, то включаем его в предварительный список ребер, составляющих минимальное остовное дерево, а также исключаем это ребро из общего списка ребер графа.
Третий шаг. Если число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, меньше числа (п – 1), то снова переходим к первому шагу алгоритма.
В противном случае заканчиваем работу алгоритма. Все ребра, входящие в предварительный список ребер, которые составляют минимальное остовное дерево, и составляют искомый подграф исходного графа.
|
|
|
Замечание. Если на каком-либо этапе работы алгоритма встречается несколько ребер, имеющих одинаковую длину, то в качестве кандидата на включение в предварительный список может быть выбрано любое из них.
Рассмотрим алгоритм нахождения минимального остовного дерева на примере. Расстояние между вершинами графа представим в таблице
Шаг 1. Из всех ребер графа минимальную длину, равную единице, имеет ребро (4,6).
Шаг 2. Поскольку выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, которые составляют минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и включаем его в предварительный список ребер, составляющих минимальное остовное дерево.
Предварительный список: {(4,6)}.
Шаг 3. Поскольку число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, равно единице (меньше числа 7-1=6), то снова переходим к первому шагу алгоритма.
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную двум, имеет ребро (3,4).
Шаг 2. Поскольку выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и включаем его в предварительный список ребер, составляющих минимальное остовное дерево.
Предварительный список: {(4,6), (3,4)}.
Шаг 3. Поскольку число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, равно двум (меньше числа 7-1=6), то снова переходим к первому шагу алгоритма.
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную двум, имеет ребро (3,6).
|
|
|
Шаг 2. Поскольку выбранное ребро образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа. Не включаем его в предварительный список ребер, составляющих минимальное остовное дерево. Переходим к шагу 1.
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную трём, имеет ребро (1,2).
Шаг 2. Поскольку выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и включаем его в предварительный список ребер, составляющих минимальное остовное дерево.
Предварительный список: {(4,6), (3,4), (1,2)}.
Шаг 3. Поскольку число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, равно трём (меньше числа 7-1=6), то снова переходим к первому шагу алгоритма.
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную трём, имеет ребро (2,5).
Шаг 2. Поскольку выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и включаем его в предварительный список ребер, составляющих минимальное остовное дерево.
Предварительный список: {(4,6), (3,4), (1,2), (2,5)}.
Шаг 3. Поскольку число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, равно четырём (меньше числа 7-1=6), то снова переходим к первому шагу алгоритма.
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную трём, имеет ребро (5,7).
Шаг 2. Поскольку выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и включаем его в предварительный список ребер, составляющих минимальное остовное дерево.
Предварительный список: {(4,6), (3,4), (1,2), (2,5), (5,7)}.
Шаг 3. Поскольку число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, равно пяти (меньше числа 7-1=6), то снова переходим к первому шагу алгоритма.
|
|
|
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную четырём, имеет ребро (1,5).
Шаг 2. Поскольку выбранное ребро образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа. Не включаем его в предварительный список ребер, составляющих минимальное остовное дерево. Переходим к шагу 1.
Шаг 1. Из всех оставшихся ребер графа минимальную длину, равную четырём, имеет ребро (1,3).
Шаг 2. Поскольку выбранное ребро не образует цикл с ребрами, включенными ранее в предварительный список ребер, составляющих минимальное остовное дерево, то исключаем это ребро из общего списка ребер графа и включаем его в предварительный список ребер, составляющих минимальное остовное дерево.
Предварительный список: {(4,6), (3,4), (1,2), (2,5), (5,7), (1,3)}.
Шаг 3. Поскольку число ребер в предварительном списке ребер, составляющих минимальное остовное дерево, равное шести равно 7-1, то минимальное остовное дерево найдено.
Задача о кратчайшем пути
Определённый товар должен быть доставлен из одного города в другой по имеющейся сети дорог, которые проходят через ряд городов. Информация о дорогах и расстояниях задана в виде графа. Необходимо найти маршрут доставки товара, имеющий наименьшую общую длину среди всех возможных маршрутов.
|
|
|
