next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Graphs :: depthFirstSearch

depthFirstSearch -- runs a depth first search on the digraph or digraph and returns the discovery time and finishing time for each vertex in the digraph

Synopsis

Description

A depth first search begins at the first vertex of a graph as a root and searches as far as possible along one branch from that root before backtracking to the next branch to the right. Discovery time denotes the order in which the vertex was searched first; finishing time denotes the time in which the vertex's descendents were all finished.

i1 : D = digraph ({{0,1},{1,3},{1,4},{4,7},{4,8},{0,2},{2,5},{2,6}},EntryMode=>"edges")

o1 = Digraph{0 => {1, 2}}
             1 => {3, 4}
             2 => {5, 6}
             3 => {}
             4 => {7, 8}
             5 => {}
             6 => {}
             7 => {}
             8 => {}

o1 : Digraph
i2 : dfs = depthFirstSearch D

o2 = HashTable{discoveryTime => HashTable{0 => 1 }}
                                          1 => 2
                                          2 => 12
                                          3 => 9
                                          4 => 3
                                          5 => 13
                                          6 => 15
                                          7 => 6
                                          8 => 4
               finishingTime => HashTable{0 => 18}
                                          1 => 11
                                          2 => 17
                                          3 => 10
                                          4 => 8
                                          5 => 14
                                          6 => 16
                                          7 => 7
                                          8 => 5

o2 : HashTable
i3 : G = cycleGraph 6

o3 = Graph{0 => {1, 5}}
           1 => {0, 2}
           2 => {1, 3}
           3 => {2, 4}
           4 => {3, 5}
           5 => {0, 4}

o3 : Graph
i4 : dfs = depthFirstSearch G

o4 = HashTable{discoveryTime => HashTable{0 => 1 }}
                                          1 => 10
                                          2 => 5
                                          3 => 4
                                          4 => 3
                                          5 => 2
               finishingTime => HashTable{0 => 12}
                                          1 => 11
                                          2 => 6
                                          3 => 7
                                          4 => 8
                                          5 => 9

o4 : HashTable

See also

Ways to use depthFirstSearch :

For the programmer

The object depthFirstSearch is a method function.