[Java] Breitensuche im Residualgraph

bernd-das-brot · 3. Juni 2009

Breitensuche im Residualgraph

servus leute,
hab da irgendwie grad nen paar schwierigkeiten mit einer aufgabe in java. implementiert werden soll die breitensuche (bfs). hier mal ein paar genauere infos:

------------------------------------------------
Eingabe: Ein Residualgraph mit Kapazitäten für gerichtete Kanten
Ausgabe: Eine Map von Knoten zu ihren BFS-Eltern

Hinweise: Die Ausgabe beschreibt einen Baum mit den kürzesteten Pfaden der Knoten bis zurnQuelle. Jeder Eintrag mappt einen Knoten zu seinem Elternknoten im Baum. Kanten mit Kapazität = 0 sind nicht in der Ausgabe enthalten. Der Quellknoten erhält ein Mapping auf den Elternknoten null
------------------------------------------------

leider komme ich bei dem thema absolut nicht weiter und hoffe das die infos ausreichen, damit mir irgendjemand hier weiterhelfen kann. weiter unten mein bisheriger code. ich glaube mir fehlt nicht mehr viel, aber das letzte gewisse etwas bekomme ich einfach nicht raus. vielleicht entdeckt ja jemand wo mein fehler liegt ...

------------------------------------------------
public Map<String, String> BFS(Graph g, String source) {

Queue<String> queue = new LinkedList<String>();
Set<String> visited = new HashSet<String>();
Map<String, String> result = new HashMap<String, String>();
Map<String, String> temporary = new HashMap<String, String>();

queue.add(source);

while (!queue.isEmpty()) {
String s = queue.poll();
visited.add(s);
result.put(s, temporary.get(s));

for (String neighbor : g.get(s).keySet()) {
temporary.put(neighbor, s);

if (!visited.contains(neighbor) && !queue.contains(neighbor)){
queue.add(neighbor);
visited.add(neighbor);

}
}
}
return result;
}
------------------------------------------------

danke schonmal im vorraus,
bernd

Anzeige

Timer · 4. Juni 2009

AW: Breitensuche im Residualgraph

na immerhin mal etwas mehr als beim letzten mal

1. was verstehst du unter "das letzte gewisse etwas"
2. was für einen fehler hat das programm

irgendwie kommt es mir so vor, als hättest du das codefragment von irgendwoher und kannst damit überhaupt nichts anfangen...

dies ist auch nicht verwunderlich, da dein ( ) bisheriger code IMO nicht zur aufgabenstellung passt..

natürlich kann ich mich auch irren. in dem fall meine frage:
auf welche art wird der graph gespeichert? du übergibst der methode eine variable vom typ "Graph" wie sieht diese klasse aus?

bernd-das-brot · 4. Juni 2009

AW: Breitensuche im Residualgraph

hey,
diesmal täuscht du dich. habe ich sogar selbst gemacht. wir haben für die aufgabe spezielle tests, die jetzt sogar alle laufen. habe vergessen das ergebnis in result einzufügen und die if-abfrage ist unvollständig gewesen.

auf gut deutsch: nach langen nächten habe ich es endlich hinbekommen. vielen dank trotzdem für die mühe

gruß

pyro · 4. Juni 2009

AW: Breitensuche im Residualgraph

Damit ist ja alles erledigt.
Closed!

Nützliche Suchen

[Java] Breitensuche im Residualgraph

Videos zum Themenbereich