Solucionado (ver solução)
Solucionado
(ver solução)
1
resposta

[Dúvida] Algoritmo de Kahn em Python

Como posso desenvolver uma função para o algoritmo de kahn que se encaixa nesse contexto abaixo?

def algoritmo_kahn(grafo):
    
grafo = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(algoritmo_kahn(grafo))
1 resposta
solução!

Oi, Giovani, tudo bem?

Uma possível forma de para implementar o algoritmo de Kahn em Python seria:

  1. Criar uma função chamada algoritmo_kahn que recebe o grafo como parâmetro;
  2. Inicializar uma lista vazia chamada ordenacao para armazenar a ordenação topológica dos vértices;
  3. Inicializar um dicionário chamado grau_entrada para armazenar o grau de entrada de cada vértice do grafo;
  4. Percorrer todos os vértices do grafo e inicialize o grau de entrada de cada vértice como zero;
  5. Percorrer todos os vértices do grafo novamente e atualize o grau de entrada de cada vértice, contando quantas arestas chegam nele;
  6. Inicializar uma fila vazia chamada fila para armazenar os vértices com grau de entrada igual a zero;
  7. Enquanto a fila não estiver vazia, realizar os seguintes passos:
    • Remover o primeiro vértice da fila e adicione-o à lista ordenacao;
    • Percorrer todos os vértices adjacentes ao vértice removido e atualize o grau de entrada de cada um, subtraindo 1;
    • Se o grau de entrada de algum vértice se tornar zero, adicioná-lo à fila.
  8. Verificar se todos os vértices foram adicionados à lista ordenacao. Em caso positivo, podemos retornar a lista. Caso contrário, devemos retornar uma mensagem de erro.

Deixo abaixo um exemplo de código que pode direcionar o desenvolvimento do seu projeto:

def algoritmo_kahn(grafo):
    ordenacao = []
    grau_entrada = {}

    for vertice in grafo:
        grau_entrada[vertice] = 0

    for vertice in grafo:
        for adjacente in grafo[vertice]:
            grau_entrada[adjacente] += 1

    fila = []
    for vertice in grafo:
        if grau_entrada[vertice] == 0:
            fila.append(vertice)

    while fila:
        vertice = fila.pop(0)
        ordenacao.append(vertice)

        for adjacente in grafo[vertice]:
            grau_entrada[adjacente] -= 1
            if grau_entrada[adjacente] == 0:
                fila.append(adjacente)

    if len(ordenacao) == len(grafo):
        return ordenacao
    else:
        return "O grafo contém um ciclo!"

grafo = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(algoritmo_kahn(grafo))

Todavia, vale ressaltar que como não tenho acesso ao cenário completo do projeto outros testes terão de ser feitos a fim de obter o resultado esperado, mas espero que esta resposta seja um bom ponto de partida para a resolução do seu problema.

Caso este post tenha lhe ajudado, por favor, marcar como solucionado ✓. Bons Estudos!