Iterative DFS algo doesn't match with recursive

Question

I am trying to find out if two nodes in a graph are connected by implementing a iterative DFS algorithm using a stack. However, to test the accuracy of my solution, I run it against a recursive algorithm that is used as the baseline. My algorithm matches the recursive solution at about 75 % but I cannot pinpoint why it is not getting the exact same results as it should.

struct Vertex {
    char label;
    int isVisited; // 0 if not yet visited, 1 if yes

    int numNeighbors;
    struct Vertex** neighbors; //list of neighbors of the vertex
};
typedef struct Vertex Vertex;

struct Graph {
    int numEdges;
    int numVertices;
    Vertex* vertexSet;
};
typedef struct Graph Graph;

struct DLink {
  TYPE value;
  struct DLink * next;
  struct DLink * prev;

};

struct cirListDeque {
  int size;
  struct DLink *last;
};

typedef struct cirListDeque cirListDeque;

Below is my attempt to implement a DFS search using the cirListDeque as a stack: (trying to find if a path exists between source and destination)

int DFS(Graph* g, Vertex* source, Vertex* destination)
{
    /*Need a stack for a depth-first search*/
    cirListDeque stack;
    TYPE vertexCurrent;

    initCirListDeque(&stack);
    addBackCirListDeque(&stack, source);

    while (!isEmptyCirListDeque(&stack))
    {
        //Pop top of the stack
        vertexCurrent = backCirListDeque(&stack);
        removeBackCirListDeque(&stack);


        if (vertexCurrent->label == destination->label)
            return 1;

        for (int i = 0; i < vertexCurrent->numNeighbors; i++)
        {
            if (vertexCurrent->neighbors[i]->label == destination->label)
                return 1;

            if (vertexCurrent->neighbors[i]->isVisited == 0)
            {
                addBackCirListDeque(&stack, vertexCurrent->neighbors[i]);
                vertexCurrent->neighbors[i]->isVisited = 1;
            }
        }
    }

    return 0;
}

I know there must be something wrong with it because I tested it against this recursive DFS algo and it didn't quite match up exactly. I know that the problem lies in my solution because they are working on the same graph.

int DFSRecursiveHelper(Graph* g, Vertex* currVert, Vertex* destination)
{
    int i;

    currVert->isVisited = 1;
    if(currVert == destination)
        return 1;
    for(i = 0; i < currVert->numNeighbors; ++i)
        if(!currVert->neighbors[i]->isVisited)
            if(DFSRecursiveHelper(g, currVert->neighbors[i], destination))
                return 1;
    return 0;
}
int DFSRecursive(Graph* g, Vertex* source, Vertex* destination)
{
    clearVisited(g);
    return DFSRecursiveHelper(g, source, destination);
}

Can anybody point me to my error? I have also tried not checking whether the neighbor's label matches the destination's label in the for loop and the accuracy went down.

Welcome to Stack Overflow. Please read the [About] page if you've not already done so. Can you show an example of a Graph you're working with where the recursive algorithm gives one answer and the iterative a different answer? Can you show the two answers you get, too, please. Think of this as an exercise in creating an MCVE ([How to create a Minimal, Complete, and Verifiable Example?](http://stackoverflow.com/help/mcve)) or SSCCE ([Short, Self-Contained, Correct Example](http://sscce.org/)) — two names and links for the same basic idea. — Jonathan Leffler, Jun 05 '15 at 05:34
I also observe that you've not specified `TYPE` in the code, but it seems to be a pointer to structure type. (See [Is it a good idea to `typedef` pointers?](http://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers) for a suggestion that `TYPE` should not be a pointer type.) That combined with a lack of sample data makes it hard to help you. —— The code compiles to object code with `typedef Vertex *TYPE;` added. Why does function `DFS()` not use the `Graph *g` parameter? How does it negotiate the graph without using it? — Jonathan Leffler, Jun 05 '15 at 05:48

score 0 · Answer 1 · answered Jun 05 '15 at 07:56

Can you be more specific in what does not work?

I see 2 changes in the visitation order:

The recursive algorithm visits neighbors in order 1...n, while the iterative pushes them to the stack an pops them in reverse order n..1.
The recursive algoritm marks the nodes as visited when it is pushed. The recursive variant marks it as visited later. Corresponding to the time when it would be popped.

Furthermore the recurse algorithm checks for node equality while the iterative compares labels.

vertexCurrent->label == destination->label

vs.

currVert == destination

Iterative DFS algo doesn't match with recursive

1 Answers1