Python - Algoritmos de gráficos

Los gráficos son estructuras de datos muy útiles para resolver muchos desafíos matemáticos importantes. Por ejemplo, topología de redes informáticas o análisis de estructuras moleculares de compuestos químicos. También se utilizan en el tráfico urbano o en la planificación de rutas e incluso en lenguajes humanos y su gramática. Todas estas aplicaciones tienen el desafío común de atravesar el gráfico utilizando sus bordes y asegurarse de que se visiten todos los nodos de los gráficos. Hay dos métodos comunes establecidos para realizar este recorrido que se describen a continuación.

Profundidad primer recorrido:

También llamado búsqueda en profundidad primero (DFS), este algoritmo atraviesa un gráfico en un movimiento de sala de profundidad y utiliza una pila para recordar obtener el siguiente vértice para iniciar una búsqueda, cuando ocurre un callejón sin salida en cualquier iteración. Implementamos DFS para un gráfico en Python utilizando los tipos de datos establecidos, ya que proporcionan las funcionalidades necesarias para realizar un seguimiento de los nodos visitados y no visitados.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

Cuando se ejecuta el código anterior, produce el siguiente resultado:

a b d e c

Ancho primer recorrido

También llamado primera búsqueda de amplitud (BFS), este algoritmo atraviesa un movimiento de sala de amplitud de gráfico y utiliza una cola para recordar obtener el siguiente vértice para iniciar una búsqueda, cuando se produce un callejón sin salida en cualquier iteración. Visite este enlace en nuestro sitio web para comprender los detalles de los pasos de BFS para un gráfico.

Implementamos BFS para un gráfico en Python usando la estructura de datos de cola discutida anteriormente. Cuando seguimos visitando los nodos no visitados adyacentes y seguimos agregándolos a la cola. Luego, comenzamos a quitar de la cola solo el nodo que queda sin nodos no visitados. Paramos el programa cuando no hay un próximo nodo adyacente que visitar.

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Cuando se ejecuta el código anterior, produce el siguiente resultado:

a c b d e