Breitensuche

 1def bfs_directed(graph, start):
 2    """
 3    Performs Breath-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 BFS traversal
 7    Returns:
 8        visited vertices and a parent for each vertex
 9    """
10    (V, E) = G
11    visited = set()  # BFS already visited
12    parent = {v: None for v in V}  # Parent pointers
13
14	Ls = [start]
15	while len(Ls) > 0:
16		x = Ls.pop(0)
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)