Алгоритм Краскала - минимальное дерево

[--=GAMER=--]

Немного теории:

1.Сортируем ребра графа по возрастанию весов.
2.Полагаем что каждая вершина относится к своей компоненте связности.
3.Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем: а)если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву б)если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения.
4.Если есть еще нерассмотренные ребра и не все компоненты связности объеденены в одну, то переходим к шагу 3, иначе выход.

Собственно вопросы возникают по пункту 3. Во первых каким образом определить создаётся ли цикл или нет?
В гугле я нашёл довольно тривиальное решение : обозначать вершины свойствами - неиспользовано,использовано в построении ребра (или хар-ка связности 0/1) . если хар-ка связанности точек x1,x2 равна 0,0 или 0,1 то ребро добавляется к дереву + x1=x2=1.. но в некоторых графах проявляется такая гадость что все точки получили 1, а дерево построить не получилось.
Второе решение: нафигачить поочерёдно n-1 ребёр где n кол-во вершин. но тогда смысл использования алгоритма для меня теряется.

Может у кого нибудь есть уже есть решённое?) Желаетльно без модулей и доп библ.

[tyomitch]

Если верить http://algolist.manual.ru/maths/graphs/span.php , то процитированное описание имеет мало общего с алгоритмом Краскала.

Едит: процитированное верно, алголист гонит

Самое простое, что приходит в голову мне: массив C[V] для номеров компонент каждой вершины. Инициализируется C[v] -> v, при каждом добавлении ребра (v,w) все C(w) в массиве заменяем на C(v). Не повлияет ли это на сложность, с ходу не могу сказать.

Едит 2: только что получил от магистра компьютерных наук ( ) подтверждение, что в учебнике так же.

[--=GAMER=--]

Самое простое, что приходит в голову мне: массив C[V] для номеров компонент каждой вершины. Инициализируется C[v] -> v, при каждом добавлении ребра (v,w) все C(w) в массиве заменяем на C(v). Не повлияет ли это на сложность, с ходу не могу сказать.

чота я сходу ничего не понял

upd: разобрался. чтото мне в этом не нравится. пока не понял что)

upd2: вопрос про исходники открыт. Наличие их на VB не обязательно, с pascal или c++ переведу сам.

[tyomitch]

upd2: вопрос про исходники открыт. Наличие их на VB не обязательно, с pascal или c++ переведу сам.

http://en.wikipedia.org/wiki/Kruskal%27 ... Pseudocode

[--=GAMER=--]

Может кто нить перевести с Явы?

http://students.ceid.upatras.gr/~papage ... ruskal.htm
Сурсы:
http://www-b2.is.tokushima-u.ac.jp/~ike ... uskal.java
http://www-b2.is.tokushima-u.ac.jp/~ike ... Krsub.java

[tyomitch]

Батюшки, как всё сложно...
На вот, написал на коленке за двадцать минут:

Код: Выделить всё

Option Explicit

Const V = 7, E = 11

Type Edge
    a As Integer
    b As Integer
    w As Integer
End Type

Dim Edges(1 To E) As Edge
Dim C(V) As Integer

Sub Main()
' 1. init
    Edges(1).a = 1: Edges(1).b = 2: Edges(1).w = 7
    Edges(2).a = 2: Edges(2).b = 3: Edges(2).w = 8
    Edges(3).a = 1: Edges(3).b = 4: Edges(3).w = 5
    Edges(4).a = 2: Edges(4).b = 4: Edges(4).w = 9
    Edges(5).a = 2: Edges(5).b = 5: Edges(5).w = 7
    Edges(6).a = 3: Edges(6).b = 5: Edges(6).w = 5
    Edges(7).a = 4: Edges(7).b = 5: Edges(7).w = 15
    Edges(8).a = 4: Edges(8).b = 6: Edges(8).w = 6
    Edges(9).a = 5: Edges(9).b = 6: Edges(9).w = 8
    Edges(10).a = 6: Edges(10).b = 7: Edges(10).w = 11
    Edges(11).a = 5: Edges(11).b = 7: Edges(11).w = 9
   
    Dim i As Integer
    For i = 1 To V: C(i) = i: Next
   
' 2. sort
    Dim j As Integer, x As Edge
    For i = 1 To E - 1
        For j = i + 1 To E
            If Edges(i).w > Edges(j).w Then
                x = Edges(i): Edges(i) = Edges(j): Edges(j) = x
            End If
        Next
    Next

' 3. main run
    Dim Pick As Edge
    j = 1
    For i = 1 To V - 1
        Do
            Pick = Edges(j)
            j = j + 1
        Loop Until C(Pick.a) <> C(Pick.b)
        Debug.Print "adding (" & Pick.a & "," & Pick.b & ")"
        Dim k As Integer
        For k = 1 To V
            If C(k) = C(Pick.b) Then C(k) = C(Pick.a)
        Next
    Next
End Sub


Пример графа -- из викистатьи.

[--=GAMER=--]

Батюшки, как всё сложно...

Фиг бы когда додумался что это всё можно легко организовать ... в голове уже много строк крутилось... ))
Меня заглючило на организации прохода по точкам. И хранения структуры.
Моей Ошибкой было в своём Type хранить не ребро а точку, а потом связывать с остальными.

[--=GAMER=--]

Кстати думаю стоит перенести в соотв. подфорум - "Графы"