# Understanding LightGraph's depth-first search

**URL:** <https://discourse.julialang.org/t/understanding-lightgraphs-depth-first-search/45785>\
**Category:** Graphs\
**Tags:** lightgraphs\
**Created:** [August 30, 2020, 9:28am UTC](https://discourse.julialang.org/t/understanding-lightgraphs-depth-first-search/45785 "2020-08-30T09:28:41Z")\
**Posts on this page:** 3\
**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 30, 2020, 9:28am UTC](https://discourse.julialang.org/t/understanding-lightgraphs-depth-first-search/45785/1 "2020-08-30T09:28:42Z")

</div>

Hello everyone,

I want to use the _depth-first search_ functionality offered by _LightGraphs.jl_. However, I don’t seem to understand the results given by the `dfs_parents` function.

I wrote a simple example

```julia
using LightGraphs, GraphPlot
g = double_binary_tree(3)
gplothtml(g, nodelabel=vertices(g))

```

 ![image](https://global.discourse-cdn.com/julialang/original/3X/6/c/6c122cfbfb621dd07e14fb00c50a31fe979f6d51.png)

```julia
julia> p = dfs_parents(g, 6)
14-element Array{Int64,1}:
  3
  1
  6
  2
  2
  6
  3
  1
  8
  8
  9
  9
 10
 10

```

I don’t understand this output or how to use it. I was actually expecting each node of the graph `g` to be visited once. Can somebody help me understand this result?

---

<div class="post-metadata">

**Author:** ![rayegun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rayegun/32/26729_2.png) [@rayegun](https://discourse.julialang.org/u/rayegun)\
**Post date:** [August 31, 2020, 4:09am UTC](https://discourse.julialang.org/t/understanding-lightgraphs-depth-first-search/45785/2 "2020-08-31T04:09:39Z")

</div>

This function is deprecated in favor of `LightGraphs.Traversals.parents`, but these are the parents of each vertex.

So the parent of vertex 1 on your graph is `p[1]` which is 3. The parent of vertex seven is `p[7]` which is 3. These are the parents relative to your starting vertex 6, of course. They would be different with a different second argument.

---

<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:** [September 2, 2020, 11:39am UTC](https://discourse.julialang.org/t/understanding-lightgraphs-depth-first-search/45785/3 "2020-09-02T11:39:33Z")

</div>

What I’m trying to do is to traverse the tree starting from the leaves and ending at a given node, e.g. 1 in the graph above. I found that this is called _postorder_ in the context of directed trees. I was hoping that LightGraph’s _depth-first search_ could help me accomplish this, but I haven’t figured out how. Do you know if there is a way to achieve this?

I managed to do this using the AbstractTrees.jl package using the `PostOrderDFS` function. This is the output i get:

```julia
julia> print_tree(root)
1
├─ 2
│ ├─ 4
│ └─ 5
├─ 3
│ ├─ 6
│ └─ 7
└─ 8
   ├─ 9
   │ ├─ 11
   │ └─ 12
   └─ 10
      ├─ 13
      └─ 14

julia> sched = [node.id for node in PostOrderDFS(root)]
14-element Array{Int64,1}:
  4
  5
  2
  6
  7
  3
 11
 12
  9
 13
 14
 10
  8
  1

```

Would this be possible to do with LightGraphs.jl?