Nachbarschaftsbetrachtung

[dadom]

Hallo, ich habe ein Problem mit einer Nachbarschaftsbetrachtung:

und zwar geht es darum festzustellen, ob Punktuntermengen eines Graphen verbunden sind.

Also wenn wir jetzt zb den Graph mit den Knoten 1-20 haben will ich wissen, ob die Knoten 1, 2, 5 und 17 verbunden sind. Mein Problem ist nicht, dass ich nicht verstehe wie es gelöst werden soll, sondern einfach die Umsetzung ins Programmieren

Die Untermenge ist in einem String vorhanden, Die Nachbarschaftsinformation in einem zweidimensionalen String array Array.

Was ich jetzt schreiben will ist eine Methode, die die Untermengen auf Konnektivitäöt überprüft und falls diese nicht vorhanden ist die einzelnen verbundenen Untermengen zurückgibt

also grob gesagt:

private String[] CheckConnectivity(String currentSbList,String[][] neighbours) 
{
String[] connectedSubList;
//Konnektivitätsüberprüfung
return connectedSubList;
}

Wie gehe ich da am Besten vor?

 

[Marco13]

Erstmal ist die Darstellung natürlich extrem unhandlich. Wenn man eine richtige Graphenklasse verwenden würde, wäre das mit ein paar Zeilen erledigt. So wäre es eben Gefrickel.

Wenn man sowas hat wie
1-2-5
17

Soll die Methode dann [1,2,5] oder [17] zurückgeben?

 

[dadom]

ja, genau sowas nur sollten halt die einzelnen Knoten nur durch ein Leerzeichen getrennt sein also
[1 2 5] und [17]

 

[Marco13]

Erstmal sollte man sich eine Hilfsmethode machen

private static List<String> getNeighbors(String v, String neighbors[][])
{
....
}

die einem die Liste der Nachbarknoten von v zurückgibt

Dann kann man von einem der Knoten aus eine Breitensuche starten, und alle besuchten Knoten merken... Würde Pseudocode da helfen?

 

[dadom]

ja wäre sicher hilfreich

 

[Marco13]

Janaja, das wäre dann ganz grob sowas wie

Set<String> input = Die Menge der Strings, aus "currentSbList" rausgepfriemelt

Set<Set<String>> result = ... // Menge der Mengen der zusammenhängenden Knoten

while (input.size() > 0)
{
    Set<String> currentResult = new Set<String>();

    // Breitensuche, alle besuchten Knoten aus
    // dem input rausnehmen und in currentResult reintun
    String current = input.firstElement();
    Queue<String> queue = ...
    queue.add(current);
    while (queue.size() > 0)
    {
        current = queue.nextElement();
        input.remove(current);
        currentResult.add(current);
        for (all neighbors n of current)
        {
            queue.add(n);
        }
    }
    result.add(currentResult);
}

 

[dadom]

danke da kann ich mir jetzt shcon was darunter vorstellen, ich werds mal morgen probieren