Python - algoritmos de gráfico

Os gráficos são estruturas de dados muito úteis na solução de muitos desafios matemáticos importantes. Por exemplo, topologia de rede de computadores ou análise de estruturas moleculares de compostos químicos. Eles também são usados ​​no tráfego da cidade ou planejamento de rotas e até mesmo em línguas humanas e sua gramática. Todas essas aplicações têm o desafio comum de percorrer o grafo usando suas arestas e garantir que todos os nós dos grafos sejam visitados. Existem dois métodos comuns estabelecidos para fazer este percurso, que é descrito abaixo.

Profundidade primeiro transversal:

Também chamado de primeira pesquisa em profundidade (DFS), esse algoritmo percorre um gráfico em um movimento em direção a profundidade e usa uma pilha para lembrar de obter o próximo vértice para iniciar uma pesquisa, quando um beco sem saída ocorre em qualquer iteração. Implementamos DFS para um gráfico em python usando os tipos de dados definidos, pois eles fornecem as funcionalidades necessárias para manter o controle de nós visitados e não 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')

Quando o código acima é executado, ele produz o seguinte resultado -

a b d e c

Largura Primeiro Traversal

Também chamado de pesquisa em largura (BFS), esse algoritmo percorre um movimento em direção à largura de um gráfico e usa uma fila para lembrar de obter o próximo vértice para iniciar uma pesquisa, quando um beco sem saída ocorre em qualquer iteração. Visite este link em nosso site para entender os detalhes das etapas do BFS para um gráfico.

Implementamos BFS para um gráfico em python usando a estrutura de dados de fila discutida anteriormente. Quando continuamos visitando os nós não visitados adjacentes e continuamos adicionando-os à fila. Em seguida, começamos a retirar da fila apenas o nó que ficou sem nós não visitados. Paramos o programa quando não há próximo nó adjacente a ser visitado.

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")

Quando o código acima é executado, ele produz o seguinte resultado -

a c b d e