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