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.

Answer 1

Can you be more specific in what does not work?

I see 2 changes in the visitation order:

1. 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.

2. 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