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

Различные алгоритмы, связанные с теорией графов.
--=GAMER=--
Фиолетовый бот
Фиолетовый бот
Аватара пользователя
 
Сообщения: 810
Зарегистрирован: 22.03.2004 (Пн) 11:29
Откуда: Владивосток

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

Сообщение --=GAMER=-- » 09.11.2008 (Вс) 15:00

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


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

Может у кого нибудь есть уже есть решённое?) Желаетльно без модулей и доп библ.
В темноте слепец — самый надежный проводник. В эпоху безумия пусть тебя ведет сумасшедший.

rRenderer Engine
VB Wiki

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

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

Сообщение tyomitch » 09.11.2008 (Вс) 15:51

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

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

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

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

--=GAMER=--
Фиолетовый бот
Фиолетовый бот
Аватара пользователя
 
Сообщения: 810
Зарегистрирован: 22.03.2004 (Пн) 11:29
Откуда: Владивосток

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

Сообщение --=GAMER=-- » 09.11.2008 (Вс) 16:09

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


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

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

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

rRenderer Engine
VB Wiki

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

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

Сообщение tyomitch » 09.11.2008 (Вс) 18:38

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

http://en.wikipedia.org/wiki/Kruskal%27 ... Pseudocode :?:
Изображение

--=GAMER=--
Фиолетовый бот
Фиолетовый бот
Аватара пользователя
 
Сообщения: 810
Зарегистрирован: 22.03.2004 (Пн) 11:29
Откуда: Владивосток

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

Сообщение --=GAMER=-- » 10.11.2008 (Пн) 0:30

В темноте слепец — самый надежный проводник. В эпоху безумия пусть тебя ведет сумасшедший.

rRenderer Engine
VB Wiki

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

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

Сообщение tyomitch » 10.11.2008 (Пн) 13:46

Батюшки, как всё сложно...
На вот, написал на коленке за двадцать минут:
Код: Выделить всё
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=--
Фиолетовый бот
Фиолетовый бот
Аватара пользователя
 
Сообщения: 810
Зарегистрирован: 22.03.2004 (Пн) 11:29
Откуда: Владивосток

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

Сообщение --=GAMER=-- » 10.11.2008 (Пн) 14:22

tyomitch писал(а):Батюшки, как всё сложно...


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

rRenderer Engine
VB Wiki

--=GAMER=--
Фиолетовый бот
Фиолетовый бот
Аватара пользователя
 
Сообщения: 810
Зарегистрирован: 22.03.2004 (Пн) 11:29
Откуда: Владивосток

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

Сообщение --=GAMER=-- » 25.12.2008 (Чт) 14:53

Кстати думаю стоит перенести в соотв. подфорум - "Графы" :wink:
В темноте слепец — самый надежный проводник. В эпоху безумия пусть тебя ведет сумасшедший.

rRenderer Engine
VB Wiki


Вернуться в Графы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList