Algorithmensammlung: Graphentheorie: Breitensuche

Algorithmus von Kruskal
Algorithmus von Prim
Breitensuche (BFS - breadth first search)
Dijkstra-Algorithmus
Tiefensuche (DFS - depth first search)

Breitensuche

Die Breitensuche ist ein Suchverfahren zum Auffinden von Knoten in Graphen. Es durchsucht dabei dem Startknoten näher gelegene Knoten vor weiter entfernten. Folglich lässt es sich, wenn man den bei der Suche gegangenen Weg speichert, auch zum Auffinden kürzester Pfade verwenden.

Für nähere Informationen siehe auch Breitensuche.

Java

public static int breitensuche(boolean[][] matrix, int[] nodelist, boolean[] nodelistvisited, int suche, int current){
    
    Queue<Integer> queue = new PriorityQueue<>(); // Warteschlange zur Verwaltung der Knotenreihenfolge
    
    // int current beinhaltet beim Aufruf der Methode den Startknoten
    queue.add(current); // Startknoten in die Warteschlange einreihen
	nodelistvisited[current] = true; // Startknoten als besucht markieren
    
	while (!queue.isEmpty()) {
		current = queue.remove(); // nächsten Knoten aus der Warteschlange nehmen
		
		if (nodelist[current] == suche) {
			return current; // Falls es der gesuchte Knoten ist, kann die Methode beendet werden
		}
	   
		for (int i = 0; i < nodelist.length; i++) {
			if (matrix[current][i]  && !nodelistvisited[i]) { // Wenn es noch Kanten zu unbesuchten Knoten gibt
			   
			   	queue.add(i); // Hinzufügen des nächsten Knotens in die Warteschlange
				nodelistvisited[i] = true; // Knoten in der Queue als besucht markieren
			}
		}
	}
}

Python

# Getestet mit Python 3.5, sollte aber unter allen Python-3.x-Versionen laufen 

import queue as q


def breitensuche(adj, start, suche):
    # adj ist die Adjazenzliste {knoten: [kanten]}
    # start ist der Index des Knoten, in dem die Suche beginnt
    # suche ist der gesuchte Knoten
    queue = q.Queue()
    queue.put(start)
    besucht = []
    while queue.qsize() > 0:
        aktiverKnoten = queue.get()
        besucht.append(aktiverKnoten)
        for andererKnoten in adj[aktiverKnoten]:
            if andererKnoten in besucht:
                continue
            if andererKnoten == suche:
                # Knoten gefunden
                return True
            queue.put(andererKnoten)
    return False