Probando un circuito al implementar el algoritmo de Kruskalls

Question

Estoy tratando de escribir un programa que encuentre el árbol de expansión mínimo. Pero un problema que estoy teniendo con este algoritmo es probar un circuito. ¿Cuál sería la mejor manera de hacer esto en Java?

autorización aquí es mi código

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

El algoritmo de Kruskall no buscará ciclos porque no es eficiente en el rendimiento; Pero intenta crear un componente que sea un árbol y luego conectarlos entre sí. Como sabe, si conecta dos árboles diferentes con un borde nuevo, creará un nuevo árbol y no es necesario verificar los ciclos.

Si nos fijamos en wiki page algoritmo es el siguiente:

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. 

Debe utilizar Disjoint Set Data Structure para esto. nuevamente desde el wiki:

primero ordene los bordes por peso usando una clasificación de comparación en O (E log E) hora; esto permite que el paso "eliminar un borde con un peso mínimo desde S" funcione en tiempo constante. A continuación, utilizamos una estructura de datos disjuntos (Unión & Buscar) para realizar un seguimiento de qué vértices están en qué componentes . Necesitamos realizar operaciones O (E), dos operaciones 'encontrar' y posiblemente una unión para cada borde. Incluso una estructura simple de datos inconexos , como bosques disjuntos con unión por rango, puede realizar operaciones O (E) en el tiempo O (E log V). Por lo tanto, el tiempo total es O (E log E) = O (E log V).

---

Creación disjuntos Bosques

Ahora se puede echar un vistazo a Boost Graph Library-Incremental Components parte. Debe implementar algunos métodos: MakeSet, Buscar, Unión, Después de eso puede implementar el algoritmo de kruskall. Todo lo que hace es trabajar con algunos conjuntos, y la forma más simple de hacerlo es usar la lista vinculada.

Cada conjunto tiene un elemento denominado como elemento representativo, que es el primer elemento del conjunto.

1- primer instrumento MakeSet por listas enlazadas:

Esto prepara la estructura de datos disjuntos-conjuntos para el incremental de algoritmo de componentes conectados haciendo cada vértice en el gráfico de un miembro de de su propio componente (o establecer).

Usted sólo debe inicializar cada vértice (elemento) como un elemento representativo de la nueva serie, se puede hacer esto mediante el establecimiento de ellos como ellos mismos padres:

function MakeSet(x) 
    x.parent := x 

2- Implementar encontrar el método:

Encuentra elemento representativo de conjunto que contiene vértice x:

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

La pieza if comprueba que el elemento sea representativo o no. establecemos todos los elementos representativos de los conjuntos como su primer elemento al configurarlos como padres.

3- Y por último cuando tienes todas las cosas anteriores simple parte está implementando Unión método:

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 

Ahora, ¿cómo se debe ejecutar Kruskall?

Primero ponga todos los nodos en n conjuntos disjuntos por método MakeSet. En cada paso después de encontrar el borde deseado (no marcado y uno mínimo), encuentre los conjuntos relacionados de sus vértices de punto final por Método Find (sus elementos representativos), si son iguales, suelte este borde porque este borde causa un ciclo, pero Si están en conjuntos diferentes, use Union método para fusionar estos conjuntos. Porque cada conjunto es una unión de árbol de ellos es un árbol.

Puede optimizar esto eligiendo una mejor estructura de datos para conjuntos disjuntos, pero por ahora creo que es suficiente. Si está interesado en estructuras de datos más avanzadas, puede implementar rango forma básica, lo encontrará en wiki, es fácil pero no lo mencioné para evitar el desconcierto.

Answer 2

Si los vértices están etiquetados de alguna manera todo lo que tiene que hacer es comprobar si los dos vértices de la arista seleccionada ha sido visitado previamente que indicará un bucle.

De modo que si se implementa con enteros, podría usar una matriz booleana para marcar qué vértices se han seleccionado.

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

O si los vértices están etiquetados como cadenas se podría añadir a un mapa, por ejemplo, y comprobar que ya no se han añadido.

Answer 3

Para verificar si hay circuitos, querrá utilizar una estructura de datos union-find. La forma más fácil de hacerlo es solo con listas vinculadas, pero hay implementaciones más eficientes. Este enlace puede ayudarte si quieres implementar uno tú mismo.

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

O aquí hay un enlace a una aplicación java:

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

Básicamente, una estructura de datos unión-permite realizar un seguimiento conjuntos disjuntos de los elementos, y soporta dos operaciones:

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 

Digamos que su conjunto de bordes que formarán el MST es S.La idea es que puedes crear un conjunto, C, usando Union-Find, que rastrea qué vértices del gráfico están conectados por los bordes en S. Cuando C contiene todos los vértices en el gráfico, entonces has terminado, y verificando si la adición de un borde creará un ciclo equivale a verificar si los dos vértices que conecta ya están en C (usando dos operaciones Find)

Así que si E es el conjunto de todos los bordes en el gráfico, su operación de actualización puede proceder de esta manera:

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 

y que deje la actualización una vez C contiene cada vértice de la gráfica.

Answer 4

Si marca el ciclo, usar DFS será muy ineficiente. Pero puede usar Disjoint Set. Al conectarse, solo necesitará verificar si sus nodos están en el mismo componente conectado.

También tenga en cuenta que debe comprobar que su original está conectado, ya que el algoritmo de Kruskall encontrará en este caso un bosque en expansión y no un árbol de expansión.

Answer 5

La forma más poderosa, si no la más común, para detectar ciclos es a través del algoritmo SCC (Strongly Connected Components) de Tarjan. En cualquier caso, esta cuestión ya ha sido contestada:

Finding all cycles in a directed graph