Тестирование схемы при реализации алгоритма Краскалла

Я пытаюсь написать программу, которая найдет минимальное остовное дерево. Но одна проблема, с которой я столкнулся с этим алгоритмом, - это проверка схемы. Как лучше всего сделать это в java.

Хорошо, вот мой код

import java.io.*;
import java.util.*;

public class JungleRoads 
{
    public static int FindMinimumCost(ArrayList graph,int size)
    {
        int total = 0;
        int [] marked = new int[size];      //keeps track over integer in the mst

        //convert an arraylist to an array
        List<String> wrapper = graph;
        String[] arrayGraph = wrapper.toArray(new String[wrapper.size()]);
        String[] temp = new String[size];
        HashMap visited = new HashMap();


        for(int i = 0; i < size; i++)
        {
           // System.out.println(arrayGraph[i]);
            temp = arrayGraph[i].split(" ");

            //loop over connections of a current node
            for(int j =  2; j < Integer.parseInt(temp[1])*2+2; j++)
            {

                if(temp[j].matches("[0-9]+"))
                {
                    System.out.println(temp[j]);
                }
            }


        }


        graph.clear();
        return total;


    }


    public static void main(String[] args) throws IOException
    {

         FileReader fin = new FileReader("jungle.in");
        BufferedReader infile = new BufferedReader(fin);

        FileWriter fout = new FileWriter("jungle.out");
        BufferedWriter outfile = new BufferedWriter(fout);


        String line;
        line = infile.readLine();
        ArrayList graph = new ArrayList();

        do
        {

            int num = Integer.parseInt(line);
            if(num!= 0)
            {

                int size = Integer.parseInt(line)-1;

                for(int i=0; i < size; i++)
                {
                    line = infile.readLine(); 
                    graph.add(line);
                }

               outfile.write(FindMinimumCost(graph, size));
            }   


            line = infile.readLine();
        }while(!line.equals("0"));

    }
}

person Steffan Harris    schedule 27.02.2012    source источник
comment
Поправьте меня, если я ошибаюсь, но это дерево, поэтому каждый узел, кроме первого, будет иметь родительский узел. Вы рассматривали эту реализацию.   -  person    schedule 01.04.2012
comment
@Legend, В алгоритме Краскалла во время выполнения алгоритма у нас есть лес, а не дерево, поэтому ваше предположение неверно.   -  person Saeed Amiri    schedule 05.04.2012


Ответы (5)


Алгоритм Краскалла не будет искать циклы, потому что он неэффективен с точки зрения производительности; Но пытается создать компоненты в виде дерева, а затем соединить их друг с другом. Как вы знаете, если вы соедините два разных дерева одним новым ребром, вы создадите новое дерево, и нет необходимости проверять циклы.

Если вы посмотрите на страницу вики, алгоритм выглядит следующим образом:

1. create a forest F (a set of trees), where each vertex in the graph is a separate tree
2. create a set S containing all the edges in the graph
3. while S is nonempty and F is not yet spanning
    a. remove an edge with minimum weight from S
    b. if that edge connects two different trees, then add it to the forest, combining 
       two trees into a single tree
    c. otherwise discard that edge.

Для этого следует использовать несвязанную структуру данных набора. снова из вики:

сначала отсортируйте ребра по весу, используя сортировку сравнения за время O (E log E); это позволяет шагу «удалить край с минимальным весом из S» работать с постоянным временем. Затем мы используем структуру данных с непересекающимися наборами (Union & Find), чтобы отслеживать, какие вершины находятся в каких компонентах. Нам нужно выполнить O (E) операций, две операции поиска и, возможно, одно объединение для каждого ребра. Даже простая структура данных с непересекающимся множеством, такая как леса с непересекающимся множеством с объединением по рангу, может выполнять O (E) операций за время O (E log V). Таким образом, общее время O (E log E) = O (E log V).


Создание непересекающихся лесов

Теперь вы можете взглянуть на Дополнительные компоненты библиотеки графов ускорения часть. Вам следует реализовать несколько методов: MakeSet, Find, Union. После этого вы можете реализовать алгоритм Краскалла. Все, что вы делаете, это работаете с некоторыми наборами, и самый простой способ сделать это - использовать связанный список.

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

1- Сначала выполните MakeSet связанными списками:

Это подготавливает структуру данных непересекающихся наборов для алгоритма добавочных связанных компонентов, делая каждую вершину в графе членом своего собственного компонента (или набора).

Вам нужно просто инициализировать каждую вершину (элемент) как репрезентативный элемент нового набора, вы можете сделать это, установив их как родительские:

 function MakeSet(x)
   x.parent := x

2- Реализуйте метод Найти:

Найдите представительный элемент множества, который содержит вершину x:

 function Find(x)
 if x.parent == x
    return x
 else
    return Find(x.parent)

Часть if проверяет, является ли элемент репрезентативным или нет. мы устанавливаем все репрезентативные элементы множеств в качестве их первого элемента, устанавливая их как родительские.

3- И, наконец, когда у вас есть все предыдущие вещи, простая часть реализует метод Union:

function Union(x, y)
 xRoot := Find(x) // find representative element of first element(set)
 yRoot := Find(y) // find representative element of second element(set)
 xRoot.parent := yRoot // set representative element of first set 
                       // as same as representative element of second set

Как теперь запустить Kruskall?

Сначала поместите все узлы в n непересекающиеся наборы с помощью метода MakeSet. На каждом шаге после нахождения желаемого ребра (не отмеченного и минимального) найдите связанные наборы вершин его конечных точек с помощью метода Найти (их репрезентативные элементы), если они совпадают, отбросьте это ребро, потому что это ребро вызывает цикл, но если они находятся в разных наборах, используйте метод Union для объединения этих наборов. Поскольку каждый набор представляет собой дерево, их объединение является деревом.

Вы можете оптимизировать это, выбрав лучшую структуру данных для непересекающихся наборов, но пока я думаю, что этого достаточно. Если вас интересуют более продвинутые структуры данных, вы можете реализовать базовый способ rank, вы найдете его в вики. Это просто, но я не упомянул об этом, чтобы избежать недоумения.

person Saeed Amiri    schedule 31.03.2012

Если вершины каким-то образом помечены, все, что вам нужно сделать, это проверить, были ли ранее посещены обе вершины выбранного ребра, что укажет на цикл.

Поэтому, если он реализован с помощью целых чисел, вы можете использовать логический массив, чтобы отметить, какие вершины были выбраны.

boolean[] visited = new boolean[vertex-count-1];

Или, если вершины помечены как строки, вы можете добавить их, например, на карту и проверить, что они еще не были добавлены.

person Dan675    schedule 27.02.2012
comment
Это неверно. Алгоритм Краскала основывается на разработке отсоединенного подграфа, поэтому обычно требуется соединить отдельные компоненты, в которых обе вершины соединительного ребра уже были посещены. Например, см. здесь (пример шага 5, в котором добавлено ребро BE) . Однако это утверждение было бы верным для другого алгоритма, такого как Prim, который действительно вырастает связное дерево на каждом шаге (и, следовательно, его легче реализовать и доказать свою правильность). - person Daniel R. Collins; 31.05.2019

Чтобы проверить наличие цепей, вы захотите использовать структуру данных union-find. Самый простой способ сделать это - использовать связанные списки, но есть более эффективные реализации. Эта ссылка может помочь вам, если вы хотите реализовать ее самостоятельно.

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Или вот ссылка на реализацию java:

http://www.koders.com/java/fid125D835ECD1C1C701008C456A93A7179FA06D196.aspx

По сути, структура данных объединение-поиск позволяет отслеживать непересекающиеся наборы элементов и поддерживает две операции:

1) Find, which takes an element as an argument and tells you which set it is in
2) Union, which takes 2 disjoint sets and merges them

Допустим, ваш массив ребер, которые будут формировать MST, равен S. Идея состоит в том, что вы можете создать набор C, используя Union-Find, который отслеживает, какие вершины графа соединены ребрами в S. Когда C содержит все вершины в графе, тогда вы закончили, и проверка того, создаст ли добавление ребра цикла, сводится к проверке того, находятся ли две вершины, которые он соединяет, уже в C (с помощью двух операций Find ).

Итак, если E - это набор всех ребер в графе, ваша операция обновления может происходить следующим образом:

    Remove edge, e from E, with minimum weight (say that it connects vertices v1 and v2)
    Find(v1) and Find(v2)
    If v1 and v2 are both in C then continue
    Else, Union(C,{v1,v2}) and append e to S

И вы остановите обновление, как только C будет содержать каждую вершину графа.

person gwilkins    schedule 31.03.2012

Если вы проверяете цикл, использование DFS будет очень неэффективным. Но вы можете использовать Disjoint Set. При подключении вам нужно только проверить, находятся ли ваши узлы в одном подключенном компоненте.

Также обратите внимание, что вы должны проверить, что ваш оригинал подключен, потому что алгоритм Краскалла найдет связующий лес, а не связующее дерево в этом случае.

person kilotaras    schedule 03.04.2012

Самый мощный, если не самый распространенный способ обнаружения циклов - это алгоритм Tarjan SCC (Strongly Connected Components). Во всяком случае, на этот вопрос уже дан ответ:

Поиск всех циклов в ориентированном графе

person Garen    schedule 07.04.2012