在 C 中使用堆栈链表的迭代 dfs

Question

大家好，我有一个关于使用堆栈的 dfs 的问题。
我几乎完成了代码，但我想我错过了完成和打印堆栈的控制。这是我的代码。

我想要的结果
0 2 6 7 5 4 1 3
下面这段代码的结果
0 2 6 7 5 4 1 3 3 5 1

我想我在使用函数“iterative_dfs”时犯了错误，但找不到它。谢谢！

#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");
    
    
}

Answer 1

例如，当 3 尚未访问但遇到两次时会出现问题，因为它是两个节点的邻居，因此被推送了两次。为避免这种情况，必须确保已推送的某些元素不会再次推送。

请查看对 push() 函数所做的更改。更改标记为 // CHANGE HERE 条评论。

注意：要使用 bool 包括 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;
      }
    }
  }
}

看到这个link（我修改之前的代码）：https://godbolt.org/z/5e71ehfWx 您会看到如何遇到节点并将其推入堆栈。 5 遇到两次并被推送两次，因此您首先在结果中看到 5。

现在，看这个link（我修改后的代码）：https://godbolt.org/z/xc38zbc36 现在，5 只在第一次遇到时被压入一次，因此你得到的结果（现在是正确的）与你预期的不同。

编辑

下面的代码给出了所需的输出：0 2 6 7 5 4 1 3

我从checking to already pushed 改为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);
      }
    }
  }
}

在 C 中使用堆栈链表的迭代 dfs

Iterative dfs using stack linked list in C

c

stack

depth-first-search

编辑