# How to use `bfs_tree` and `dfs_tree` from `LightGraphs.jl`

I’m trying to understand how to use `bfs_tree` and `dfs_tree` from `LightGraphs.jl` . They both return the same graph so I don’t know how to extract the actual order in which the nodes were visited.

``````using LightGraphs

g = double_binary_tree(4)

bfs = bfs_tree(g, 1)
dfs = dfs_tree(g, 1)

bfs == dfs
``````

Can somebody show me an example of how to use these two functions?

These functions seemingly only return the final BFS/DFS trees but not the order in which nodes were visited. Since your input graph is already a tree, you get the same output for `bfs` and `dfs`. For e.g., random graphs `g = SimpleGraph(20,100)` the functions will return different `bfs` and `dfs`.

I do not know if ` LightGraphs.jl` has something built-in to output the traversal order. But you could copy/paste the functions from the source code and adapt them (e.g., with print functions).

1 Like

Thanks for the answer. @GunnarFarneback came up with this solution in Slack:

It looks like you can get a dfs traversal order with

``````topological_sort_by_dfs(dfs_tree(g,1))
``````

For bfs I don’t see anything in the sources but from the output of `bfs_tree` it should be very easy to construct it. Maybe something like:

``````function bfs_traversal(g, s)
b = bfs_tree(g, s)
x = [s]
i = 1
while i <= length(x)
append!(x, neighbors(b, x[i]))
i += 1
end
return x
end
``````

Yes, and it works great! I was just looking if I could get rid of that dependency given that I’m using `LightGraphs.jl` for other stuff.

You mean `AbstractTrees.jl`?

Yeah, currently I’m using `AbstractTrees.jl`'s `PostOrderDFS` function. I was just wondering if I could get the same functionality from `LightGraphs.jl` to get rid of `AbstractTrees.jl`.

Oh sorry that I suggested something that you are already doing. Anyways lets see if someone from the LightGraphs community can be of more use.

I see that you also poster in slack #graph channel. Have you tried the #help-desk channel also?

Initially, my issue was that I didn’t understand how to use `bfs_tree()` and `dfs_tree()` functions. But the problem turned out to be that I didn’t understand what they are meant for. The conclusion is that `LightGraphs.jl` doesn’t provide DFS and BFS traversal functionality (in the form of iterators) like `AbstractTrees.jl` does. I’m happy with that response. @GunnarFarneback found a small hack of how to get these traversal orders using `LightGraphs.jl` (posted above). Another approach is to copy/paste `bfs_tree` and `dfs_tree` and adapt them to my needs, as suggested by @mike_k.

Thanks for the `AbstractTrees.jl` recommendation though. For now, I will keep this dependency in my code.

2 Likes