# How to use \`bfs\_tree\` and \`dfs\_tree\` from \`LightGraphs.jl\`

**URL:** <https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331>\
**Category:** Graphs\
**Tags:** lightgraphs\
**Created:** [August 13, 2021, 9:40am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331 "2021-08-13T09:40:20Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![mroavi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mroavi/32/8804_2.png) [@mroavi](https://discourse.julialang.org/u/mroavi)\
**Post date:** [August 13, 2021, 9:40am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/1 "2021-08-13T09:40:21Z")

</div>

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.

```julia
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?

---

<div class="post-metadata">

**Author:** ![mike\_k](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mike_k/32/211864_2.png) [@mike\_k](https://discourse.julialang.org/u/mike_k)\
**Post date:** [August 13, 2021, 12:10pm UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/2 "2021-08-13T12:10:33Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mroavi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mroavi/32/8804_2.png) [@mroavi](https://discourse.julialang.org/u/mroavi)\
**Post date:** [August 13, 2021, 12:17pm UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/3 "2021-08-13T12:17:54Z")

</div>

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

> It looks like you can get a dfs traversal order with
> 
> ```julia
> 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:
> 
> ```julia
> 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
> 
> ```

---

<div class="post-metadata">

**Author:** ![Storopoli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/storopoli/32/209278_2.png) [@Storopoli](https://discourse.julialang.org/u/Storopoli)\
**Post date:** [August 13, 2021, 4:06pm UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/4 "2021-08-13T16:06:58Z")

</div>

Have you tried [https://github.com/JuliaCollections/AbstractTrees.jl](https://github.com/JuliaCollections/AbstractTrees.jl) ?

---

<div class="post-metadata">

**Author:** ![mroavi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mroavi/32/8804_2.png) [@mroavi](https://discourse.julialang.org/u/mroavi)\
**Post date:** [August 16, 2021, 8:27am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/5 "2021-08-16T08:27:52Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Storopoli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/storopoli/32/209278_2.png) [@Storopoli](https://discourse.julialang.org/u/Storopoli)\
**Post date:** [August 16, 2021, 8:44am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/6 "2021-08-16T08:44:03Z")

</div>

You mean `AbstractTrees.jl`?

---

<div class="post-metadata">

**Author:** ![mroavi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mroavi/32/8804_2.png) [@mroavi](https://discourse.julialang.org/u/mroavi)\
**Post date:** [August 16, 2021, 8:46am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/7 "2021-08-16T08:46:16Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Storopoli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/storopoli/32/209278_2.png) [@Storopoli](https://discourse.julialang.org/u/Storopoli)\
**Post date:** [August 16, 2021, 8:48am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/8 "2021-08-16T08:48:20Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![mroavi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mroavi/32/8804_2.png) [@mroavi](https://discourse.julialang.org/u/mroavi)\
**Post date:** [August 16, 2021, 8:55am UTC](https://discourse.julialang.org/t/how-to-use-bfs-tree-and-dfs-tree-from-lightgraphs-jl/66331/9 "2021-08-16T08:55:19Z")

</div>

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.