Tiefensuche in Graph

[Antonine]

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?

	/**
	 * 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!! 🙂

 

[SlaterB]

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.

 

[The_S]

das Speichern/ Laden + der interne Aufbau des Graphen dürften auch wichtig sein,

Wenn es vor dem Speichern funktioniert (so wie ich das jetzt rauslese), nach dem Speichern und Neuladen aber nicht mehr, dann ist da auch der Fehler zu vermuten und nicht in deinem Code.

 

[SlaterB]

danke, Echo 😉

 

[The_S]

danke, Echo 😉

Nicht ganz. Du schreibst "wäre auch interessant". Ich gehe einen Schritt weiter und behaupte, dass da der Fehler liegt und nicht nur, dass es auch interessant wäre 😉 .