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