Frage zur Wegfindung

[wastl]

Hi,
ich habe das Problem das ich ein Tool geschrieben hat welches mir auf einen Graph den Kruskalalgorythmus anwendet. Soweit funktioniert es aber sobald es an die Überprüfung geht ob ein Ring entsteht spielt es verrückt es findet immer nur einen Ring obwohl sich mehrere bilden würden.

Der Graph liegt als zweidimensionales Array vor in dem die Verbindungen gespeichert sind.

matrix[ersterpunkt][zweiterpunkt] = Gewicht der Verbindung

Der Code für die Ringrutine folgt

public boolean check_ring(int beginn, int matrix2[][])
    {
        int matrix[][] = new int[matrix2.length][matrix2.length];
        
        for(int c = 0; c < matrix.length; c++)
        {
            for(int c2 = 0; c2 < matrix.length; c2++)
            {
                matrix[c][c2] = matrix2[c][c2];
            }
        }
        
        
        int position = beginn;
        boolean keinkreis = true;
        Vector weg = new Vector();
        int counter = 0;
        int check[] = new int[3];
        
        for(int i2 = 0; i2 < matrix.length*matrix.length; i2++)//((matrix.length*(matrix.length-1))/2)
        {
            ret:
            for(int i=0;i<matrix.length;i++) 
            {
                if(matrix[position][i]!=0)
                {
                    
                    weg.insertElementAt(new Integer(i), counter);
                   
                    counter++;
                    matrix[position][i] = 0;
                    matrix[i][position] = 0;
                    position = i;
                    if(position == beginn)
                    {
                        //keinkreis = false;
                        return false;
                    }
                    
                    break ret;
                }   
        }
    }
    return true;
    }

[/code]

 

[tuxedo]

Und wo ist jetzt die im Titel angesprochene Frage? *dummfrag*

 

[wastl]

Sry, vergessen bin bischen aufgered, weil ich net packe.

Die Frage ist ob jemand den Fehler sieht warum manche Kreise nicht gefunden werden.

 

[SlaterB]

ist es so schwer, z.B. noch einen Beispielgraphen mit > 1 Kreisen mitanzugeben, in welchem das Problem autfaucht?
also im Grunde noch eine main-Operation -> schon ist es ein vollständiges, kinderleicht auszuprobierendes Programm


und willst du auch keine Zeile auf den Inhalt des Codes verschwenden?
was verstehst du unter 'einen Kreis finden'? wie reagiert das Programm in diesem Fall/ was soll bei mehreren stattdessen anders passieren?

ganz grob gesehen scheint die Operation beim ersten Auftreffen eines Kreises false zurückzugeben,
dann ist die Operation beendet, klar dass dann nix weiter passiert..

 

[Marco13]

Ja, man mann sich schon manchmal fragen, ob es so schwer ist, ein KSKB zu bauen...

import java.util.*;

class KruskalTest
{
    public static void main(String args[])
    {
        int matrix[][];
        matrix = new int[][]{{0,1,1,1},{1,0,0,0},{1,0,1,0},{1,0,0,0}};
        System.out.println(containsCycle(matrix));
        matrix = new int[][]{{0,1,1,1},{1,0,0,0},{1,0,0,0},{1,0,0,0}};
        System.out.println(containsCycle(matrix));
    }


    static boolean containsCycle(int _[][]){for(int n=0;n<_.length;
    n++)if(____(n,new ArrayList<Integer>(),_))return true;return false;}
    static boolean ____(int __,ArrayList<Integer> ___,int _[][]){if
    (___.contains(__))return true;___.add(__);for(int i=0;i<_.length;
    i++)if(_[__][i]!=0&&(___.size()<=1||___.get(___.size()-2)!=i)&&
    ____(i,___,_))return true;___.remove(___.size()-1);return false;}

}

 

[tuxedo]

Na da hat sich der Autor ja alle mühe geben den Code unkenntlich zu machen ...