Grafos
BFS, DFS, ordem topológica e Dijkstra — O(V + E) e O((V + E) log V), e o que cada um responde.
Um grafo é qualquer coisa que se conecta: ruas, dependências, amizades, tarefas. Quatro algoritmos respondem quase toda pergunta sobre eles, e o formato é o que um JSON já traz — um vault de listas.
dataforge
adopt Arcane.Algoritmos as Alg
// Sem peso: quem depende de quem.
tarefas := {
"cafe": ["xicara", "agua"],
"agua": ["ferver"],
"xicara": [],
"ferver": []}
ordem := Alg.ordem_topologica(tarefas)
assert ordem[0] is "cafe"
amigos := {"ana": ["bia"], "bia": ["caio"], "caio": ["davi"], "eva": []}
assert Alg.bfs(amigos, "ana")["davi"] is 3 // tres apertos de mao
assert Alg.dfs(amigos, "ana") is ["ana", "bia", "caio", "davi"]
// Com peso: o menor caminho.
mapa := {"centro": [["norte", 4], ["sul", 2]], "sul": [["norte", 1]], "norte": []}
r := Alg.dijkstra(mapa, "centro")
assert r["distancia"]["norte"] is 3
assert Alg.caminho(r, "norte") is ["centro", "sul", "norte"]
assert Alg.caminho(r, "lugar-nenhum") is void| Pergunta | Algoritmo | Custo |
|---|---|---|
| a menor distância em passos | bfs | O(V + E) |
| tudo que se alcança | dfs | O(V + E) |
| uma ordem que respeite as dependências | ordem_topologica | O(V + E) |
| o menor caminho com peso | dijkstra + caminho | O((V + E) log V) |
Os dois erros que ele recusa#
dataforge
adopt Arcane.Algoritmos as Alg
monitor:
Alg.ordem_topologica({"a": ["b"], "b": ["c"], "c": ["a"]})
assert no
handle Error as e:
out e.message // mostra o ciclo: a → b → c → a
monitor:
Alg.dijkstra({"a": [["b", -2]]}, "a")
assert no
handle Error as e:
out e.message // Dijkstra nao aceita peso negativo