Testing for a circuit when implementing Kruskalls algorithm

Question

I'm trying to write a program that would find the minimum spanning tree. But one problem I am having with this algorithm, is testing for a circuit. What would be the best way to do this in java.

Ok here is my code

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's algorithm doesn't searche for cycles, because it's not performance efficient; instead creates disjoint trees, and then connects them. Since connecting two distinct subtrees with a single edge creates a new tree, there is no need to check for cycles.

If you look at wiki page algorithm is as follow:

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.

You should use Disjoint Set Data Structure for this. again from wiki:

first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step "remove an edge with minimum weight from S" to operate in constant time. Next, we use a disjoint-set data structure (Union&Find) to keep track of which vertices are in which components. We need to perform O(E) operations, two 'find' operations and possibly one union for each edge. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(E) operations in O(E log V) time. Thus the total time is O(E log E) = O(E log V).

---

#Creating Disjoint Forests Now you can take a look at Boost Graph Library-Incremental Components part. You should implement some methods: MakeSet, Find, Union, After that you can implement Kruskall's algorithm. All you doing is working with sets, and simplest possible way to do so is using linked list.

Each set has one element named as representative element which is the first element in the set.

1- First implement MakeSet by linked lists:

This prepares the disjoint-sets data structure for the incremental connected components algorithm by making each vertex in the graph a member of its own component (or set).

Just initialize each vertex (element) as a representative element of new set, we can do this by setting them as themselves' parent:

 function MakeSet(x)
   x.parent := x

2- Implement Find method:

Find representative element of a set that contains a vertex x:

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

The if part checks the element is representative element or not. we set all representative elements of sets as their first element by setting them as themselves parent.

3- And finally when all previous steps are done, simple part is implementing the Union method:

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

Now how you should run Kruskall?

First put all nodes in n disjoint sets by MakeSet method. In each iteration after finding desired edge (not marked and minimal one), find related sets of its endpoint vertices by Find method (their representative elements), if they are the same, drop this edge out because this edge causes a cycle, but If they are in different sets, use Union method to merge these sets. Since each set is a tree their union is a tree.

You can optimize this by choosing better data structure for disjoint sets, but for now I think this is enough. If you are interested in more advanced data structures, you can implement rank base method, there is a good documentation about it in wiki, it's easy but I didn't mention it to prevent from bewilderment.

Answer 2

If the vertices are labelled in some way all you need to do is check if both vertices of the edge selected has been visited previously which will indicate a loop.

So if its implemented with integers you could use a boolean array to mark which vertices have been selected.

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

Or if the vertices are labelled as strings you could add them to a Map for instance and check they have not already been added.

Answer 3

To check for circuits, you'll want to use a union-find data structure. The easiest way to do it is just with linked lists, but there are more efficient implementations. This link can help you if you want to implement one yourself.

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

Or here's a link to a java implementation:

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

Basically, a union-find data structure allows you to track disjoint sets of elements, and supports two operations:

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

Let's say your array of edges that will form the MST is S. The idea is that you can make a set, C, using Union-Find, that tracks which vertices of the graph are connected by the edges in S. When C contains all the vertices in the graph, then you're finished, and checking to see if the addition of an edge will create a cycle amounts to checking whether the two vertices that it connects are already in C (by using two Find operations).

So if E is the set of all the edges in the graph, your update operation can proceed like so:

    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

And you stop the update once C contains every vertex of the graph.

Answer 4

The most powerful if not most common way to detect cycles is via Tarjan's SCC (Strongly Connected Components) algorithm. In any case, this question has already been answered:

Finding all cycles in a directed graph

Answer 5

If you check for cycle, using DFS it will be very inefficient. But you can use Disjoint Set. When connecting, you'll only need to check if your nodes are in same connected component.

Also note, that you have to check that your original is connected, because Kruskall algorithm will find spanning forest and not a spanning tree in that case.