Tiefensuche

Einfache Sprache

Tiefensuche ist ein Suchalgorithmus für Knoten in Graphen.

Idee von Tiefensuche

Gegeben sei ein ungerichteter, zusammenhängender Graph $G = (V, E)$ mit $V = \{0, . . . , n − 1\}$. Die Tiefensuche geht wiefolgt vor: Zu beginn wähle einen Startknoten $a$ und besuche ihn. Dann besuche einen Nachbarknoten $b$ von $a$ aus. Dann einen von $b$ aus usw. Irgendwann erreichen wir einen Knoten, dessen Nachbarknoten schon alle besucht worden sind. Dann gehen wir zum vorherig besuchten Knoten zurück Backtracking und schauen dort ob es noch unbesuchte Nachbarn gibt. Breche ab falls der Startknoten $a$ wieder erreicht wird und alle seine Nachbarn besucht wurden.

Algorithmus

 1def dfs_directed(graph, start) -> None:
 2    """
 3    Performs Depth-First Search on an undirected graph.
 4    Args:
 5        graph: The directed Graph as a tuple, consisting of a tuple of sets of verticies and a set of edges of the form (from, to)
 6        start: Starting vertex for DFS traversal
 7    Returns:
 8        DFS Numbering and a parent for each vertex
 9    """
10    (V, E) = G
11    visited = set()  # DFS already procesed
12    parent = {v: None for v in V}  # Parent pointers
13    #dfs_exp[start] = True
14	Ls = [start]
15	while len(Ls) > 0:
16		x = Ls.pop()
17		visited.append(x)
18		for to in [v for (u,v) in E if u == x]:
19			if not dfs_num[to]:
20				parent[to] = x
21				Ls.append(to)   
22    return (visited, parent)

Home:

Type/Note