File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : r.depth_first_search(self, start, ignore_direction=False, distance=None, neighbors=None)
Docstring :
Return an iterator over the vertices in a depth-first ordering.
INPUT:
* "start" - vertex or list of vertices from which to start the
traversal
* "ignore_direction" - (default False) only applies to directed
graphs. If True, searches across edges in either direction.
* "distance" - Deprecated. Broken, do not use.
* "neighbors" - a function giving the neighbors of a vertex. The
function should take a vertex and return a list of vertices. For
a graph, "neighbors" is by default the "neighbors()" function of
the graph. For a digraph, the "neighbors" function defaults to
the "neighbor_out_iterator()" function of the graph.
See also:
* "breadth_first_search()"
* "breadth_first_search" -- breadth-first search for fast
compiled graphs.
* "depth_first_search" -- depth-first search for fast compiled
graphs.
EXAMPLES:
sage: G = Graph( { 0: [1], 1: [2], 2: [3], 3: [4], 4: [0]} )
sage: list(G.depth_first_search(0))
[0, 4, 3, 2, 1]
By default, the edge direction of a digraph is respected, but this
can be overridden by the "ignore_direction" parameter:
sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]})
sage: list(D.depth_first_search(0))
[0, 3, 6, 7, 2, 5, 1, 4]
sage: list(D.depth_first_search(0, ignore_direction=True))
[0, 7, 6, 3, 5, 2, 1, 4]
Multiple starting vertices can be specified in a list:
sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]})
sage: list(D.depth_first_search([0]))
[0, 3, 6, 7, 2, 5, 1, 4]
sage: list(D.depth_first_search([0,6]))
[0, 3, 6, 7, 2, 5, 1, 4]
More generally, you can specify a "neighbors" function. For
example, you can traverse the graph backwards by setting
"neighbors" to be the "neighbors_in()" function of the graph:
sage: D = digraphs.Path(10)
sage: D.add_path([22,23,24,5])
sage: D.add_path([5,33,34,35])
sage: list(D.depth_first_search(5, neighbors=D.neighbors_in))
[5, 4, 3, 2, 1, 0, 24, 23, 22]
sage: list(D.breadth_first_search(5, neighbors=D.neighbors_in))
[5, 24, 4, 23, 3, 22, 2, 1, 0]
sage: list(D.depth_first_search(5, neighbors=D.neighbors_out))
[5, 6, 7, 8, 9, 33, 34, 35]
sage: list(D.breadth_first_search(5, neighbors=D.neighbors_out))
[5, 33, 6, 34, 7, 35, 8, 9]