Die Seite enthält einen Java Code als Beispiel
- Bestimme den Knoten, an dem die Suche beginnen soll, und speichere ihn in einer Warteschlange ab.
- Entnimm einen Knoten vom Beginn der Warteschlange und markiere ihn.
- Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere "gefunden" zurück.
- Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens ans Ende der Warteschlange an.
- Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere "gefunden" zurück.
- Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere "nicht gefunden" zurück.
- Wiederhole ab Schritt 2.
== Beispiel ==
Quellcode
- void breitensuche(Graph g, String node) {
- Map<String, Integer> abstand = new HashMap<String, Integer>();
- Queue<String> queue = new LinkedList<String>();
- abstand.put(node, 0);
- queue.add(node);
- while (!queue.isEmpty()) {
- String s = queue.poll();
- int d = abstand.get(s); // muss enthalten sein
- for (Iterator<String> it = g.edgeIterator(s); it.hasNext();) {
- String expanded = it.next();
- if (!abstand.containsKey(expanded)) {
- abstand.put(expanded, d+1);
- queue.add(expanded);
- }
- }
- action(s); // zum Beispiel Ausgabe
- }
- }
15.807 mal gelesen