Quantcast

Documentation Center

  • Trial Software
  • Product Updates

Contents

Graph::depthFirstSearch

Makes a depth first Search in a graph.

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

Graph::depthFirstSearch(G, <StartVertex = v>)

Description

Graph::depthFirstSearch traverses through a graph via depth first search. The output shows the first time of identification, the finishing time and the predecessor of each vertex. If a vertex is a single vertex with no predecessor its predecessor is infinity.

Graph::depthFirstSearch(G, StartVertex=v) traverses through a graph via depth first search starting from vertex v. The output shows the first time of identification, the finishing time and the predecessor of each vertex. If a vertex is a single vertex with no predecessor its predecessor is infinity.

Examples

Example 1

A typical tree is created and drawn for a better understanding of the algorithm.

G := Graph([a, b, c, d, e, f, g, h, i, j, k, l],
           [[a, b], [a, c], [b, d], [b, e], [c, f], [c, g],
            [d, h], [e, i], [e, j], [f, k], [g, l]], 
           Directed):
plot(
  Graph::plotGridGraph(G, VerticesPerLine = [12, 12, 12, 12],
    VertexOrder = [
  None, None, None, None, None, None, a,    None, None, None, None, None,
  None, None, b,    None, None, None, None, None, None, c,    None, None,
  None, d,    None, None, e,    None, None, f,    None, None, g,    None,
  h,    None, None, i,    None, j,    None, None, k,    None, None, l
    ]
  )
)

Now we call Graph::depthFirstSearch to find out the starting times, the finishing times and the predecessors of each vertex:

Graph::depthFirstSearch(G)

Vertex a is dicovered first, then vertex b and so on. The table in the middle shows the finishing times. h for example has the finishing time of 5, meaning that vertices a, b, c, d and h itself were visited before it was recognized that h is a leaf (finishing time = starting time + 1). The right table shows the predecessor of every vertex. The backtacking from a single vertex is therefore really simple. a as the first vertex discovered in its component can not be backtracked any further.

Example 2

What happens now, if there exist a vertex that has no connection to any other vertex. The upper example is taken and a single vertex is added without changing anything else. Then a depth first search is invoked on the graph:

G := Graph([a, b, c, d, e, f, g, h, i, j, k, l],
           [[a, b], [a, c], [b, d], [b, e], [c, f], [c, g],
            [d, h], [e, i], [e, j], [f, k], [g, l]], 
           Directed):
G2 := Graph::addVertices(G, [m]):
Graph::depthFirstSearch(G2, StartVertex = [a])

The newly inserted vertex m has no predecessor. The predecessor holds therefore the value infinity.

Example 3

If we start somewhere in the graph without knowing the root of the DAG, the results are of course different:

G := Graph([a, b, c, d, e, f, g, h, i, j, k, l],
           [[a, b], [a, c], [b, d], [b, e], [c, f], [c, g],
            [d, h], [e, i], [e, j], [f, k], [g, l]], 
           Directed):
Graph::depthFirstSearch(G, StartVertex = [c])

The predecessor of c is c, but if we look at the graph it should be a. This is nevertheless not quite correct. Breadth first search takes the given vertex and uses this as the root of the graph (no in-vertices!). This explains also why the next call shows a infinity as predecessor to l:

Graph::depthFirstSearch(G, StartVertex = [l])

Parameters

G

Graph

v

List containing one vertex.

Options

StartVertex

Defines a vertex from which to start the depth first traversal.

Return Values

List containing three tables. The first table holds the first identification timestamp of each vertex, the second the finishing timestamp and the third the predecessor vertex.

Was this topic helpful?