Общая реализация примитивов al go для графа из V вершин с использованием MSTset :
1. Create Min heap(H), Parent array(P) and Weight array(W) of size V
2. Push a vertex(preferably with smallest edge weight) to H
3. Until H is not empty do this:
- extract min weight vertex(u) from heap, add it to MSTset
- check every adjacent vertex(v) of u
- if the [weight of v is greater than the weight of u-v edge]
&& [<b><i>v is not included in MSTset</i></b>] ->
- update parent of v as u in P and weight as u-v edge's weight in W.
Использование MSTset связано с тем, что его реализация основана на сокращение в теории графов .
Мы используем MStset, чтобы вершины, которые уже были обработаны с минимальным весом, не обрабатывались снова.
Если мы используем эту реализацию без использования MSTset, тогда он может иметь более одного MST, поскольку край минимального веса имеет две конечные точки v1 и v2, поэтому, если мы обновим вес v1, чем позже, мы также сможем обновить вес v2 и подключить его снова на v1 (в сценарии, когда v2 не соединен ни с одной вершиной с меньшим весом).
Но поскольку у нас уже есть родительский массив (P), мы можем предотвратить такое поведение.
ОБНОВЛЕНО AL GO:
1. Create Min heap(H), Parent array(P) and Weight array(W) of size V
2. Push a vertex(preferably with smallest edge weight) to H
3. Until H is not empty do this:
- extract min weight vertex(u) from H
- check every adjacent vertex(v) of u
- if the [weight of v is greater than the weight of u-v edge]
&& [<b><i>parent of u is not v</i></b>] ->
- update parent of v as u in P and weight as u-v edge's weight in W.
Таким образом, нам не нужно использовать дополнительное пространство для MSTset, чтобы проверить, включен ли он уже в MST.
Обновлен Al go был протестирован с сертификатом В примерах ниже перечислены немногие:
введите описание изображения здесь