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))
Você está vendo a versão anterior da nova experiência da Alura que estamos preparando para você. Em breve, ela ganha uma identidade visual novinha totalmente pensada em potencializar seus estudos!
Solucionado
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))
Oi, Giovani, tudo bem?
Uma possível forma de para implementar o algoritmo de Kahn em Python seria:
algoritmo_kahn que recebe o grafo como parâmetro;ordenacao para armazenar a ordenação topológica dos vértices;grau_entrada para armazenar o grau de entrada de cada vértice do grafo;fila para armazenar os vértices com grau de entrada igual a zero;ordenacao;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.