Sunday, July 4th 2010, 2:24pm
Tags
breitensuche,
breitensuche algorithmus,
breitensuche java,
tiefensuche
Abstract
Die Breitensuche ist eine uninformierte Suche, welche durch Expansion der einzelnen Level der Graphen ausgehend vom Startknoten den Graph in die Breite nach einem Element durchsucht.
Die Seite enthält einen Java Code als Beispiel
Article
- 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.
- Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere "nicht gefunden" zurück.
- Wiederhole ab Schritt 2.
|
Java Quellcode
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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
}
}
|
Request deletion
report critical content
