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

Question

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

Ok вот мой код

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")); 

    } 
} 

Answer 1

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

Если посмотреть на wiki page алгоритм выглядит следующим образом:

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. 

Вы должны использовать Disjoint Set Data Structure для этого. снова из вики:

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

---

Создание Disjoint леса

Теперь вы посмотрите на Boost Graph Library-Incremental Components часть может. Вы должны реализовать некоторые методы: MakeSet, Найти, Союз, После этого вы можете реализовать алгоритм kruskall. Все, что вы делаете, работает с некоторыми наборами, и самый простой способ сделать это - использовать связанный список.

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

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 

Теперь, как вы должны запустить Крускали?

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

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

Answer 2

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

Итак, если его реализовать с целыми числами, вы можете использовать логический массив, чтобы отметить, какие вершины были выбраны.

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

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

Answer 3

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

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 содержит все вершины графа.

Answer 4

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

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

Answer 5

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

Finding all cycles in a directed graph