Python Forum

graph = {
    'A' : ['B', 'C', 'E'],
    'B' : ['A', 'D', 'E'],
    'C' : ['A', 'F', 'G'],
    'D' : ['B'],
    'E' : ['A', 'B', 'D'],
    'F' : ['C'],
    'G' : ['C']
}

#visit all the nodes of a graph (connected components)
def bfs_connected_component(graph, start):
    #keep track of all visited nodes
    explored = []
    #keep track of nodes to be checked
    queue = [start]

    #keep looping until there are nodes still to be checked
    while queue:
        #pop shallowest node from queue
        node = queue.pop(0)
        if node not in explored:
            #add node to list of checked nodes
            explored.append(node)
            neighbours = graph[node]

            #add neighbours of node to queue
            for neighbour in neighbours:   
                queue.append(neighbour)
    return explored

bfs_connected_component(graph, 'A')

#find shortest path between 2 nodes of a graph
def bfs_shortest_path(graph,start,goal):
    #keep track of th explored nodes
    explored = []
    #keep track of all the paths to be checked
    queue = [[start]]

    #return path if start is goal
    if start == goal:
        return "Start = goal"
    
    #keeps looping until all possible paths have been found
    while queue:
        #pop the first path from the queue
        path = queue.pop(0)
        #get the last node from the path
        node = path[-1]

        if node not in explored:
            neighbours = graph[node]
            #go through all naighbour nodes, construct
            #ppush it into the queue
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                #return path if neighbour is goal
                if neighbour == goal:
                    return new_path
            
            #mark node as explored
            explored.append(node)
    return "Sorry, there is no connecting path between the selected nodes."

bfs_shortest_path(graph,'G','D')