Tiefensuche in Graph

A

Antonine

Gast
Hallo,

ich möchte in einem Graphen-Programm mit gerichteten Graphen gern eine Tiefensuche durchführen. Dazu habe ich Methoden geschrieben, die zunächst alle funktionieren. Sobald ich den Graph jedoch in einer Datei abspeichere und anschließend wieder lade, wird mir in einigen Fällen angezeigt, dass zwischen 2 Knoten kein Weg vorhanden ist, obwohl es diesen gibt. Leider sehe ich den Fehler nicht, vielleicht könnt ihr mir da weiterhelfen?

Java:
	/**
	 * Führt eine Tiefensuche von einem Start- zu einem Zielknoten durch. Dabei wird
	 * zunächst geprüft, ob die Knoten gleich sind, da in diesem Fall kein Weg vorhanden
	 * sein kann. Ansonsten wird der jeweils kürzeste Weg zurückgegeben bzw. angegeben,
	 * dass kein Weg existiert.
	 * @param from - Startknoten
	 * @param to - Endknoten
	 * @return Knoten gleich, kein Weg gefunden oder Weg gefunden
	 */
	public boolean deepSearch(Node from, Node to) {
		if (from.equals(to)) {
			JOptionPane.showMessageDialog(null, "Start- und Zielknoten sind gleich.");
			return false;
		}
		Stack<String> path = new Stack<String>();
		Stack<String> foundPath = new Stack<String>();
		helpDeepSearch(from, to, path, foundPath);
		
		if(foundPath.size() == 0) {
			JOptionPane.showMessageDialog(null, "Zwischen den Knoten ist kein Weg vorhanden.");
			return false;
		}

		ArrayList<String> list = new ArrayList<String>();
		list.add(from.getValue().toString());
		list.addAll(foundPath);
		JOptionPane.showMessageDialog(null, "Kürzester Weg von Knoten " + from.getValue().toString() + " zu Knoten " + to.getValue().toString() + "\nist: " + list + ".");
		return true; 	
	}
	
	/**
	 * Hilfsmethode für die Tiefensuche, die den jeweils kürzesten Weg von einem
	 * Start- zu einem Zielknoten ermittelt.
	 * @param current - aktueller Knoten
	 * @param to - Zielknoten
	 * @param path - Weg
	 * @param foundPath - Ergebnisweg
	 */
	private void helpDeepSearch(Node current, Node to, Stack<String> path, Stack<String> foundPath) {
		if(current.equals(to)) {
			if(foundPath.isEmpty() || path.size() < foundPath.size()) {
				foundPath.clear();
				foundPath.addAll(path);
			}
		}	
		HashSet<Node> nodes = getSuccNodes(current);
		for (Node node : nodes) {
			path.push(node.getValue().toString());
			helpDeepSearch(node, to, path, foundPath);
			path.pop();
		}
	}

Vielen Dank für eure Hilfe!! :)
 
S

SlaterB

Gast
was soll man an einem Code erkennen, der in gewissen Fällen sogar schon funktioniert?
das Speichern/ Laden + der interne Aufbau des Graphen dürften auch wichtig sein,

aber das kannst du bestimmt auch alles selber rausfinden,
logge/ debugge jeden einzelnen Schritt, es wird doch sicher immer auf denselben Weg gesucht,
irgendwenn kommst du an eine Stelle x (notfalls beide Abläufe Schritt für Schritt vergleichen),
wo im einen Fall was gefunden wird, im anderen nicht,
an dieser Stelle gib die beteiligten Knoten/ deren Verbindungen usw. im Detail aus,

wenn du siehst was fehlt, dann schaue dir wiederum im Detail an, wie die jeweiligen Dinge initial aufgebaut werden
und vor allem was bei Speichen + Laden an diesen Stellen ganz genau passiert

je kleiner der Graph ist, desto weniger Nebenlogs hast du,
zur eindeutigen Suche bietet sich an, die Knoten bei Erzeugung exakt durchzunummerieren
usw.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Luk10 Frage zu Graph Tiefensuche Java Basics - Anfänger-Themen 4
U Best Practice Graphen Tiefensuche Klassifizierung von Kanten "B","C","F" Java Basics - Anfänger-Themen 2
4 Stack over flow bei rekursiver Tiefensuche Java Basics - Anfänger-Themen 5
E Erste Schritte brauche hilfe zum verstehen einer Klasse(Tiefensuche) Java Basics - Anfänger-Themen 17
Luk10 Frage zur Tiefensuche Java Basics - Anfänger-Themen 20
kirchrath Wegpunkt wird nicht zur History einer Tiefensuche hinzugefügt Java Basics - Anfänger-Themen 2
K Tiefensuche Java Basics - Anfänger-Themen 2
S Tiefensuche Probleme - Der "Rücksprung" Java Basics - Anfänger-Themen 4
H Tiefensuche im binären Baum Java Basics - Anfänger-Themen 2
G Mit der Tiefensuche alle Wege finden Java Basics - Anfänger-Themen 2
S [EDIT] Tiefensuche / Depth-First-Search / Greedy Algorithmus Java Basics - Anfänger-Themen 6
M Graphen (Tiefensuche) Java Basics - Anfänger-Themen 2
M Untersuchen ob ein Graph nach entfernen einer Kante immer noch zusammenhängend ist Java Basics - Anfänger-Themen 70
O ADT Graph nach größe Abfragen Java Basics - Anfänger-Themen 42
N gerichteter Graph aus einer Datei einlesen Java Basics - Anfänger-Themen 21
Z Graph einlesen Java Basics - Anfänger-Themen 2
S Ungerichteter Graph in Java Java Basics - Anfänger-Themen 1
M int double int double Graph Java Basics - Anfänger-Themen 3
N gerichteten Graph abspeichern Java Basics - Anfänger-Themen 2
S Methoden Wegsuche in einem Graph Java Basics - Anfänger-Themen 6
F Zusammenhängend Komponente suchen(Graph) Java Basics - Anfänger-Themen 4
F Kanten in Graph Java Basics - Anfänger-Themen 3
M Wth? übernimmt nichtübergebenen Wert (Graph) Java Basics - Anfänger-Themen 4
T Wie kann ich einem Graph in nem JPanel eine fixe Größe geben? Java Basics - Anfänger-Themen 6
H gerichteter Graph Java Basics - Anfänger-Themen 9
B Graph aus 2dim-Array Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Anzeige

Neue Themen


Oben