Graph/DepthFirstSearch/dfs.h File Reference

Defines the interface to Depth-First Search

Defines the interface to depth-first search. More...

#include <sstream>
#include "Graph.h"

Go to the source code of this file.

Classes

class  EdgeLabel
 Helper class for labeling edges. More...

Functions

void dfs_search (Graph const &graph, int s, vector< int > &d, vector< int > &f, vector< int > &pred, list< EdgeLabel > &labels)
 Perform Depth First Search starting from vertex s, and compute the values d[u] (when vertex u was first discovered), f[u] (when all vertices adjacent to u have been processed), pred[u] (the predecessor vertex to u in resulting depth-first search forest), and label edges according to their type.


Detailed Description

Defines the interface to Depth-First Search

Defines the interface to depth-first search.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void dfs_search ( Graph const &  graph,
int  s,
vector< int > &  d,
vector< int > &  f,
vector< int > &  pred,
list< EdgeLabel > &  labels 
)

Perform Depth First Search starting from vertex s, and compute the values d[u] (when vertex u was first discovered), f[u] (when all vertices adjacent to u have been processed), pred[u] (the predecessor vertex to u in resulting depth-first search forest), and label edges according to their type.

Parameters:
graph the graph being searched.
s the vertex to use as the source vertex.
d array of counter values when each vertex is discovered.
f array of counter values when each vertex is finished.
pred array of previous vertices in the depth-first search tree.
labels structure to store all edge labels.

Algorithm Development Kit 1.0