Implementation of Depth First Search algorithm over a graph. More...
#include "dfs.h"
Functions | |
void | dfs_visit (Graph const &graph, int u, vector< int > &d, vector< int > &f, vector< int > &pred, vector< vertexColor > &color, int &ctr, list< EdgeLabel > &labels) |
Visit a vertex, u, in the graph and update information. | |
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. |
Implementation of Depth First Search algorithm over a graph.
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.
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. |
void dfs_visit | ( | Graph const & | graph, | |
int | u, | |||
vector< int > & | d, | |||
vector< int > & | f, | |||
vector< int > & | pred, | |||
vector< vertexColor > & | color, | |||
int & | ctr, | |||
list< EdgeLabel > & | labels | |||
) |
Visit a vertex, u, in the graph and update information.
graph | the graph being searched. | |
u | the vertex being visited. | |
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. | |
color | array of vertex colors in the depth-first search tree. | |
ctr | counter to use for assigning d[] and f[] values. | |
labels | structure to store all edge labels. |
Algorithm Development Kit 1.0