c++ directed graph depth first search

Question

I am attempting to write a method DFS method for a directed graph. Right now I am running into a segmentation fault, and I am really unsure as to where it is. From what I understand of directed graphs I believe that my logic is right... but a fresh set of eyes would be a very nice help.

Here is my function:

void wdigraph::depth_first (int v) const {

static int fVertex = -1;
static bool* visited = NULL;

if( fVertex == -1 ) {
   fVertex = v;
   visited = new bool[size];
   for( int x = 0; x < size; x++ ) {
      visited[x] = false;
   }
}

cout << label[v];
visited[v] = true;

for (int v = 0; v < adj_matrix.size(); v++) {
   for( int x = 0; x < adj_matrix.size(); x++) {
     if( adj_matrix[v][x] != 0 && visited[x] != false ) {
        cout << " -> ";
        depth_first(x);
     }
     if ( v == fVertex ) {
        fVertex = -1;
        delete [] visited;
        visited = NULL;
     }
   }
}
}

class definition:

class wdigraph {
public:
wdigraph(int =NO_NODES);          // default constructor
~wdigraph() {};                   // destructor
int get_size() { return size; }   // returns size of digraph

void depth_first(int) const;// traverses graph using depth-first search
void print_graph() const;   // prints adjacency matrix of digraph

private:
int size;                         // size of digraph
vector<char> label;               // node labels
vector< vector<int> > adj_matrix; // adjacency matrix
};

thanks!

Answer 1

There are a few things you might want to consider. The first is that function level static variables are not usually a good idea, you can probably redesign and make those either regular variables (at the cost of extra allocations) or instance members and keep them alive.

The function assumes that the adjacency matrix is square, but the initialization code is not shown, so it should be checked. The assumption can be removed by making the inner loop condition adj_matrix[v].size() (given a node v) or else if that is an invariant, add an assert before that inner loop: assert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" ); --the same goes for the member size and the size of the adj_matrix it self.

The whole algorithm seems more complex than it should, a DFS starting at node v has the general shape of:

dfs( v )
   set visited[ v ]
   operate on node (print node label...)
   for each node reachable from v:
      if not visited[ node ]:
         dfs( node )

Your algorithm seems to be (incorrectly by the way) transversing the graph in the opposite direction. You set the given node as visited, and then try to locate any node that is the start point of an edge to that node. That is, instead of following nodes reachable from v, you are trying to get nodes for which v is reachable. If that is the case (i.e. if the objective is printing all paths that converge in v) then you must be careful not to hit the same edge twice or you will end up in an infinite loop -> stackoverflow.

To see that you will end with stackoverlow, consider this example. The start node is 1. You create the visited vector and mark position 1 as visited. You find that there is an edge (0,1) in the tree, and that triggers the if: adj_matrix[0][1] != 0 && visited[1], so you enter recursively with start node being 1 again. This time you don't construct the auxiliary data, but remark visited[1], enter the loop, find the same edge and call recursively...

Answer 2

You are deleting visited before the end of the program. Coming back to the starting vertex doesn't mean you finished. For example, for the graph of V = {1,2,3}, E={(1,2),(2,1),(1,3)}.

Also, notice you are using v as the input parameter and also as the for-loop variable.

Answer 3

I see a couple of problems:

The following line

 if( adj_matrix[v][x] != 0 && visited[x] != false ) {

should be changed to

 if( adj_matrix[v][x] != 0 && visited[x] == false ) {

(You want to recurse only on vertices that have not been visited already.)

Also, you're creating a new variable v in the for loop that hides the parameter v: that's legal C++, but it's almost always a terrible idea.