Algorithm Depth-First Search (DFS) AND Breadth-First Search (BFS)

1. Objectives

Implement the BFS (Breadth-First Search) and DFS (Depth-First Search) algorithms in Python.
Verify that BFS calculates the path with the fewest edges between two vertices of the graph.
Verify that DFS allows finding all vertices accessible from a source vertex of the graph.

2. Introduction

BFS is a way to find all vertices accessible from a source vertex of a graph. The search resembles a wave that hits all vertices starting from node 1 (beginning). The FIFO queue Q is used to maintain the wavefront, and control is kept over nodes already included in the wave to prevent them from being revisited. BFS allows obtaining the shortest path from the source node to the other connected nodes. The efficiency of BFS is O(number of vertices + number of edges), commonly written as O(V + E) (V for the number of vertices, E for the number of edges). BFS is used to solve the following problems:

Testing if a graph is connected.
Calculating the spanning forest of the graph.
Calculating for each vertex in the graph, a path with the minimum number of edges between the initial vertex and the current vertex or informing that no such path exists.

DFS (Depth-First Search) is a systematic way of finding all vertices accessible from a source vertex. Like breadth-first search, DFS traverses a connected component of a given graph and defines a spanning tree. The basic idea of depth-first search is the following: it systematically explores each edge. We start over from different vertices as needed. As soon as we discover a vertex, DFS starts exploring from it (unlike BFS, which places a vertex in a queue to explore later), only backtracking when necessary (Muniswamy 2013). DFS is used to solve the following problems:

Testing if the graph is connected.
Calculating the spanning forest of the graph.
Calculating a path between two vertices of the graph or informing that no such path exists.
Calculating a cycle in the graph or informing that no such cycle exists.

3. Exercise 1

A. Problem Statement

Implement the BFS algorithm to answer the following questions: 1. Is there a path from CAB to BAT? 2. What is that path?

graph TD
    CAB  --> CAT 
    CAB  --> CAR
    CAR --> CAT
    CAR --> BAR
    CAT --> MAT
    CAT --> BAT
    MAT --> BAT
    BAR --> MAT

B. Implementation in Python

To implement the BFS algorithm in Python, a queue is used to enqueue the neighbor nodes of each source node. In the BFS function, two dictionaries are created: one called marked to mark nodes that have already been enqueued, and edgeto to assign each node its preceding node.

from collections import deque

def busqueda_BFS(name,graph):
    """
    busqueda_BFS Search Algorithm

    Args:
        start (str): The starting node.
        graph (dict): The graph represented as an adjacency list.

    Returns:
        edgeto (dict): A dictionary containing the parent nodes of the connected component.
    """
    ##############ESTRUCTURAS AUXILIARES 
    marked= dict.fromkeys(graph.keys(),False)
    marked[name]=True
    edgeto={name:"inicio"}
    edgeto.update(dict.fromkeys(graph[name],name))
    marked.update(dict.fromkeys(graph[name],True))
    ##############ESTRUCTURAS AUXILIARES 
    search_queue = deque()
    search_queue += graph[name] 
    searched = [] 
    while search_queue:
        person = search_queue.popleft() 
        if not person in searched: 
            comprueba=[ nodo  for nodo in graph[person] if marked[nodo]==False ]
            edgeto.update(dict.fromkeys(comprueba,person))
            marked.update(dict.fromkeys(comprueba,True))
            search_queue += graph[person] 
            searched.append(person)
    return edgeto

def ruta(busqueda,edgeto):
    """ Retorna ruta del componente conectado nodo inico
        Args:
            edgeto :(dict) diccionario que estan los nodos padres del componete conectado
            busqueda :(str) nodo buscar
        return:
            ruta list() : lista que contiene la ruta
    """
    ruta=[]
    if (busqueda in edgeto.keys()):
        while busqueda !="inicio":
            ruta.insert(0,busqueda)
            busqueda=edgeto[busqueda]   
    return ruta

C. Execution of the Algorithm

The graph is constructed using a Python dictionary where the key is the node, and the value is a list of the node’s neighbors. Note that the graph to be analyzed (Illustration) is directed, so only the target neighbors should be included.

graph = {}
graph["CAB"] = ["CAT", "CAR"]
graph["CAR"] = ["CAT", "BAR"]
graph["CAT"] = ["MAT","BAT"]
graph["MAT"] = ["BAT"]
graph["BAR"] = ["MAT"]
graph["BAT"] = []

edgeto=busqueda_BFS("CAB",graph)
edgeto

{'CAB': 'inicio',
 'CAT': 'CAB',
 'CAR': 'CAB',
 'MAT': 'CAT',
 'BAT': 'CAT',
 'BAR': 'CAR'}

ruta("BAT",edgeto)

['CAB', 'CAT', 'BAT']

graph TD
    CAB --> CAT
    CAT --> BAT

rutas={nodo:ruta(nodo,edgeto) for nodo in edgeto.keys()}
rutas

{'CAB': ['CAB'],
 'CAT': ['CAB', 'CAT'],
 'CAR': ['CAB', 'CAR'],
 'MAT': ['CAB', 'CAT', 'MAT'],
 'BAT': ['CAB', 'CAT', 'BAT'],
 'BAR': ['CAB', 'CAR', 'BAR']}

graph TD
    CAB --> CAT
    CAB --> CAR
    CAT --> MAT
    CAT --> BAT
    CAR --> BAR

4. Exercise 2

D. Problem Statement

What are the DFS Trees for the following graph G, given that the starting node is 0? Implement the DFS algorithm (using the recursive method) and use the necessary auxiliary structures.

graph TD
    0 <--> 2
    0 <--> 1
    0 <--> 5
    1 <--> 2
    2 <--> 3
    2 <--> 4
    3 <--> 5
    3 <--> 4
    6 <--> 7

def dfs( graph, node,visited=set()):
    """algortimo dfs
        Args:
            graph :(dict) diccionario que representa grafo
            node :(str) nodo fuente o raiz
            visited:control nodos visitados default set()
        return:
            ruta list() : lista que contiene la ruta
    """
    if node not in visited: ##comparacion si el nodo no se ha visitad
        print (node)##impresion de nodos visitados
        visited.add(node) ##agregando nodos visitados
        marked[node]=True##control de nodos visitados
        for neighbour in graph[node]:
            comprueba=[ nodo  for nodo in graph[node] if marked[nodo]==False ]##comprovacion
            edgeto.update(dict.fromkeys(comprueba,node))##llenado de edgeto
            dfs(graph, neighbour,visited)

def ruta_DFS(busqueda,edgeto):
    """ Retorna ruta del componente conectado nodo inico
        Args:
            edgeto :(dict) diccionario que estan los nodos padres del componete conectado
            busqueda :(str) nodo buscar
        return:
            ruta list() : lista que contiene la ruta
    """
    ruta=[]
    while busqueda !="":
        ruta.insert(0,busqueda)
        busqueda=edgeto[busqueda]
    return ruta

Execution of the Algorithm

Define the graph and the starting node 0 as input parameters.

#graph
graph = dict()
graph["0"] = ["2", "1","5"]
graph["1"] = ["0", "2"]
graph["2"] = ["0","1","3","4"]
graph["3"] = ["5","4","2"]
graph["4"] = ["3","2"]
graph["5"] = ["3","0"]
marked= dict.fromkeys(graph.keys(),False)
edgeto= dict.fromkeys(graph.keys(),"")

The execution of DFS provides the complete edgeto structure, which allows generating the route tree of the connected component, the DFS Tree.

dfs(graph,"0")

To obtain all the routes, the route function was executed with the edgeto obtained for each node, storing this result in the routes dictionary, which allows knowing the route from the origin to each node.

edgeto

{'0': '', '1': '2', '2': '0', '3': '2', '4': '3', '5': '3'}

rutas={nodo:ruta_DFS(nodo,edgeto) for nodo in edgeto.keys()}
rutas

{'0': ['0'],
 '1': ['0', '2', '1'],
 '2': ['0', '2'],
 '3': ['0', '2', '3'],
 '4': ['0', '2', '3', '4'],
 '5': ['0', '2', '3', '5']}

graph TD
 0 --> 2
 2 --> 1
 2 --> 3
 3 --> 4
 3 --> 5

References

Muniswamy, VV. 2013. Design and Analysis of Algorithms. IK International Pvt Ltd.