search.py

graph = {
    1: {2:1,5:1},
    2: {1:1,3:1,5:1},
    3: {2:1,4:1},
    4: {3:1,5:1,6:1},
    5: {1:1,2:1,4:1},
    6: {4:1}
}

time = 0

def dfs(graph):
    nodes_prop = {}
    for u in graph.keys():
        nodes_prop[u] = {
            "color":"white",
            "parent": None
        }
    global time
    time = 0
    for u in graph.keys():
        if nodes_prop[u]["color"] == "white":
            nodes_prop = dfs_visit(graph, nodes_prop, u)
    return nodes_prop

def dfs_visit(graph, nodes_prop, u):
    global time
    time = time + 1
    nodes_prop[u]["distance"] = time
    nodes_prop[u]["color"] = "gray"
    for v in graph[u]:
        if nodes_prop[v]["color"] == "white":
            nodes_prop[v]["parent"] = u
            nodes_prop = dfs_visit(graph, nodes_prop, v)
    nodes_prop[u]["color"] = "black"
    time = time + 1
    nodes_prop[u]["finish"] = time
    return nodes_prop


def initialize(graph, start = None):
    nodes_prop = {}

    for node in graph.keys():
        nodes_prop[node] = {
            "color": "white",
            "distance": float('inf'),
            "parent":None
        }

    nodes_prop[start] = {
        "color":"gray",
        "distance": 0,
        "parent": None,
    }

    Q = [start]

    return nodes_prop, Q


def bfs(graph, start):
    nodes, queue = initialize(graph, start)

    while queue:
        u = queue.pop(0)
        for v in graph[u]:
            if nodes[v]["color"] == "white":
                nodes[v] = {
                    "color":"gray",
                    "distance": nodes[u]["distance"] + 1,
                    "parent": u
                }
                queue.append(v)
        nodes[u]["color"] = "black"
    return nodes


def getPath(nodes, targetNode):
    current = targetNode
    path = []
    while nodes[current]["parent"]:
        path.append(nodes[current]["parent"])
        current = nodes[current]["parent"]
    return path

nodes_bfs = bfs(graph, 1)

print(nodes_bfs)
print(getPath(nodes_bfs,3))

nodes_dfs = dfs(graph)
print(nodes_dfs)
print(graph)