Hi everyone I have a question about dfs using stacks.
I almost made the code but I think I missed control of finishing and printing the stack.
It is my code.
The result I want
0 2 6 7 5 4 1 3
A result of this code below
0 2 6 7 5 4 1 3 3 5 1
I think I made mistake when using function "iterative_dfs" but can not find it. Thank you!
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
struct node{
int vertex;
struct node *link;
};
typedef struct node *nodePointer;
nodePointer graph[MAX_VERTICES] ;
int visited[MAX_VERTICES];
struct stack{
int data;
struct stack *link ;
};
typedef struct stack *stackpointer;
stackpointer top= NULL;
void push(int data){
stackpointer temp = (stackpointer)malloc(sizeof(struct stack));
temp->data= data;
temp->link = top;
top= temp;
}
int pop(){
stackpointer temp ;
int value;
value= top->data;
temp= top ;
top= top->link;
free(temp);
return value;
}
void iterative_dfs(int v){
nodePointer w;
int vnext;
visited[v]=1;
push(v);
while(top){
vnext=pop();
visited[vnext]=1;
printf("%5d", vnext);
for(w=graph[vnext]; w; w=w->link){
if(!visited[w->vertex]){
push(w->vertex);
}
}
}
}
void main() {
nodePointer prev;
nodePointer np;
/* adjacency list for vertex 0 */
np = (nodePointer)malloc(sizeof(nodePointer)); np->vertex = 1; np->link = NULL; graph[0] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 2; np->link = NULL; prev->link = np;
/* adjacency list for vertex 1 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 0; np->link = NULL; graph[1] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 3; np->link = NULL; prev->link = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 4; np->link = NULL; prev->link = np;
/* adjacency list for vertex 2 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 0; np->link = NULL; graph[2] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 5; np->link = NULL; prev->link = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 6; np->link = NULL; prev->link = np;
/* adjacency list for vertex 3 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 1; np->link = NULL; graph[3] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 7; np->link = NULL; prev->link = np;
/* adjacency list for vertex 4 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 1; np->link = NULL; graph[4] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 7; np->link = NULL; prev->link = np;
/* adjacency list for vertex 5 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 2; np->link = NULL; graph[5] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 7; np->link = NULL; prev->link = np;
/* adjacency list for vertex 6 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 2; np->link = NULL; graph[6] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 7; np->link = NULL; prev->link = np;
/* adjacency list for vertex 7 */
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 3; np->link = NULL; graph[7] = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 4; np->link = NULL; prev->link = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 5; np->link = NULL; prev->link = np; prev = np;
np = (nodePointer)malloc(sizeof(struct node)); np->vertex = 6; np->link = NULL; prev->link = np;
for(int i=0; i<8; i++) visited[i] = 0;
iterative_dfs(0);
printf("\n");
}
The problem occurs when for example, 3 is not yet visited but it is encountered twice because it's a neighbor to two nodes and thus pushed twice. To avoid that, it must be ensured that some element which is already pushed, isn't pushed again.
Please see the changes done to push() function. Changes are marked as // CHANGE HERE comments.
Note: to use bool include stdbool.h
void iterative_dfs(int v) {
nodePointer w;
int vnext;
visited[v] = 1;
// CHANGE HERE: have a boolean array pushed which will store which elements
// are already pushed in the stack
bool pushed[8] = {0};
push(v);
// CHANGE HERE: update the pushed array after a push operation
pushed[v] = true;
while (top) {
vnext = pop();
visited[vnext] = 1;
printf("%5d", vnext);
for (w = graph[vnext]; w; w = w->link) {
// CHANGE HERE: check for both visited and pushed
if (!visited[w->vertex] && !pushed[w->vertex]) {
push(w->vertex);
// CHANGE HERE: update the pushed array after a push operation
pushed[w->vertex] = true;
}
}
}
}
See this link (code before I made changes): https://godbolt.org/z/5e71ehfWx You see how nodes are encountered and pushed into the stack. 5 is encountered twice and is pushed twice because of which you see 5 first in the result.
Now, see this link (code after I made changes): https://godbolt.org/z/xc38zbc36 Now, 5 is only pushed once when it is first encountered and thus you get a result (which is now correct) different from what you expected.
The below code gives the desired output: 0 2 6 7 5 4 1 3
I changed from checking to already pushed to checking already popped.
void iterative_dfs(int v) {
nodePointer w;
int vnext;
visited[v] = 1;
// CHANGE HERE: have a boolean array popped which will store which elements
// are already popped from the stack
bool popped[8] = {0};
push(v);
while (top) {
vnext = pop();
visited[vnext] = 1;
// CHANGE HERE: check for popped
// update the popped array if not already popped
if (popped[vnext])
continue;
popped[vnext] = true;
printf("%5d", vnext);
for (w = graph[vnext]; w; w = w->link) {
// CHANGE HERE: check for visited
if (!visited[w->vertex]) {
push(w->vertex);
}
}
}
}