Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
854 B
0
Indexable
Never
def bfs(visited, to_build, queue, graph, pkg):
    visited.add(pkg)
    queue.append(pkg)
    while queue:
        i = queue.pop(0)
        to_build.insert(0, i)
        for dependency in graph[i]:
            if dependency in to_build:
                raise Exception(f"Circular dependency detected between {dependency} and {i}")
            if dependency not in visited:
                visited.add(dependency)
                queue.append(dependency)

visited_set = set()
to_build = []  # Stack of packages to build
queue = []  # Tracks dependencies of each evaluated package
package_graph = {
    "A": ["B"],
    "B": ["C", "D"],
    "C": ["D"],
    "D": ["F"],
    "E": ["D"],
    "F": []
}
pkg = "B"
if pkg not in package_graph:
    print("Package does not exist")
else:
    bfs(visited_set, to_build, queue, package_graph, pkg)
    print(to_build)
Leave a Comment