Skip to content

Instantly share code, notes, and snippets.

@johnmyleswhite
Last active February 3, 2022 19:29
Show Gist options
  • Save johnmyleswhite/5723773 to your computer and use it in GitHub Desktop.
Save johnmyleswhite/5723773 to your computer and use it in GitHub Desktop.
BFS and DFS for DAG's in Julia
function bfs(start_node::Any,
next_nodes::Function,
at_node::Function)
to_process = Array(Any, 0)
depths = Array(Int, 0)
push!(to_process, start_node)
push!(depths, 0)
while !isempty(to_process)
current_node = shift!(to_process)
depth = shift!(depths)
at_node(current_node, depth)
for child_node in next_nodes(current_node)
push!(to_process, child_node)
push!(depths, depth + 1)
end
end
end
function dfs(current_node::Any,
next_nodes::Function,
at_node::Function,
pre::Bool = true,
depth::Integer = 0)
if pre
at_node(current_node, depth)
end
for child_node in next_nodes(current_node)
dfs(child_node, next_nodes, at_node, pre, depth + 1)
end
if !pre
at_node(current_node, depth)
end
end
include("bfs_dfs.jl")
dag = {:a => [:b, :c, :d],
:b => [:e, :f, :g],
:c => [:h, :i, :j],
:e => [:k, :l]}
function printwithdepth(sym, depth)
@printf "%s%s\n" repeat(" ", depth) sym
end
bfs(:a, sym -> get(dag, sym, Symbol[]), printwithdepth)
dfs(:a, sym -> get(dag, sym, Symbol[]), printwithdepth, true)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment