Test per un circuito durante l'implementazione dell'algoritmo di Kruskalls

Question

Sto provando a scrivere un programma che trovi l'albero di spanning minimo. Ma un problema che sto riscontrando con questo algoritmo è la verifica di un circuito. Quale sarebbe il modo migliore per farlo in java.

Ok Ecco il mio codice

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

L'algoritmo di Kruskall non esegue la ricerca dei cicli, perché non è efficiente dal punto di vista delle prestazioni; Ma prova a creare un componente che è albero e quindi collegarli tra loro. Come sai, se connetti due alberi diversi con un nuovo bordo, creerai un nuovo albero e non è necessario verificare i cicli.

Se si guarda alla wiki page algoritmo è il seguente:

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. 

Si dovrebbe usare Disjoint Set Data Structure per questo. ancora da wiki:

primo ordina i bordi in peso utilizzando un ordinamento per confronti a O (E E log) tempo; questo consente al passaggio "rimuovere un bordo con peso minimo da S" per operare in tempo costante. Successivamente, utilizziamo una struttura di dati disgiunti (Unione & Trova) per tenere traccia di quali vertici sono in cui i componenti . Dobbiamo eseguire operazioni O (E), due operazioni di "trova" e possibilmente una unione per ogni spigolo. Anche una semplice struttura di dati disgiunti come le foreste disgiunte con unione per grado può eseguire operazioni O (E) in tempo O (E log V). Quindi il tempo totale è O (E log E) = O (E log V).

---

Creazione disgiunti Foreste

Ora si può dare un'occhiata a Boost Graph Library-Incremental Components parte. È necessario implementare alcuni metodi: MakeSet, Trova, Unione, Dopo di che è possibile implementare l'algoritmo di kruskall. Tutto ciò che fai è lavorare con alcuni set, e il modo più semplice per farlo è usare la lista collegata.

Ogni set ha un elemento denominato elemento rappresentativo che è il primo elemento del set.

1- primo attrezzo MakeSet da liste concatenate:

Questo prepara la struttura di dati disgiunti-set per il incrementale algoritmo componenti collegati facendo ogni vertice nel grafico un membro propria componente (o impostare).

Si dovrebbe solo inizializzare ogni vertice (elemento) come elemento rappresentativo della nuova serie, si può fare questo impostandole come se stessi genitori:

function MakeSet(x) 
    x.parent := x 

2- Implementare Trova metodo:

Trova elemento rappresentativo del set che contiene vertici x:

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

La parte if controlla che l'elemento sia rappresentativo o meno. impostiamo tutti gli elementi rappresentativi degli insiemi come loro primo elemento impostandoli come se fossero i loro genitori.

3- E infine quando hai tutte le cose precedenti semplice parte sta attuando dell'Unione metodo:

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 

Ora come si dovrebbe eseguire Kruskall?

primo messo tutti i nodi n insiemi disgiunti da MakeSet metodo. In ogni passaggio dopo aver trovato il bordo desiderato (non controllato e uno minimo), trova i relativi set di vertici del punto finale per Trova metodo (i loro elementi rappresentativi), se sono uguali, rilascia questo margine perché questo bordo provoca un ciclo, ma Se sono in set diversi, utilizzare il metodo Unione per unire questi set. Poiché ogni insieme è l'unione degli alberi di loro è albero.

È possibile ottimizzare questo scegliendo una migliore struttura dati per set disgiunti, ma per ora penso sia sufficiente. Se sei interessato a strutture di dati più avanzate, puoi implementare il modo di livello, lo troverai in wiki, è facile ma non l'ho menzionato per evitare lo smarrimento.

Answer 2

Se i vertici sono etichettati in qualche modo, tutto quello che dovete fare è controllare se entrambi i vertici del bordo selezionato è stato visitato in precedenza che indicherà un ciclo.

Quindi se implementato con numeri interi è possibile utilizzare un array booleano per contrassegnare quali vertici sono stati selezionati.

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

O se i vertici sono etichettati come stringhe li potrebbe aggiungere ad una mappa, per esempio e verificare che non sono già stati aggiunti.

Answer 3

Per verificare la presenza di circuiti, è consigliabile utilizzare una struttura dati di ricerca unione. Il modo più semplice per farlo è solo con gli elenchi collegati, ma esistono implementazioni più efficienti. Questo link può aiutarti se vuoi implementarne uno tu stesso.

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

O qui è un link ad un'implementazione Java:

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

In sostanza, una struttura di dati union-find consente di tenere traccia insiemi disgiunti di elementi, e supporta due operazioni:

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 

Diciamo che la vostra serie di bordi che formeranno il MST è S.L'idea è che puoi creare un set, C, usando Union-Find, che tiene traccia dei vertici del grafico collegati dai bordi in S. Quando C contiene tutti i vertici nel grafico, hai finito e controlla se l'aggiunta di un bordo creerà un ciclo per verificare se i due vertici che collega si trovano già in C (utilizzando due operazioni Find).

Quindi, se E è l'insieme di tutti i bordi del grafico, l'operazione di aggiornamento può procedere in questo modo:

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 

E si interrompere l'aggiornamento una volta C contiene ogni vertice del grafico.

Answer 4

Se si verifica il ciclo, l'utilizzo di DFS sarà molto inefficiente. Ma puoi usare Disjoint Set. Durante la connessione, dovrai solo verificare se i tuoi nodi si trovano nello stesso componente connesso.

Si noti inoltre che è necessario verificare che l'originale sia connesso, in quanto l'algoritmo di Kruskall troverà la spanning forest e non uno spanning tree in quel caso.

Answer 5

Il metodo più potente se non il più comune per rilevare i cicli è tramite l'algoritmo di Tarjan SCC (Strongly Connected Components). In ogni caso, la questione è già stata risolta:

Finding all cycles in a directed graph