c - 使用邻接表进行深度优先搜索

Question

我试图理解下面的代码，但 DFS 函数中有一些不清楚的地方

在此输入代码

#include<stdio.h>  

typedef struct node
{
    struct node *next;
    int vertex;
}node;

node *G[20];  

int visited[20];
int n;
void read_graph();
void insert(int,int); 
void DFS(int);

void main()
{
    int i;
    read_graph();
    //initialised visited to 0

    for(i=0;i<n;i++)
        visited[i]=0;

    DFS(0);
}

void DFS(int i)
{
    node *p;

    printf("\n%d",i);
    p=G[i];
    visited[i]=1;
    while(p!=NULL)
    {
        i=p->vertex;
        if(!visited[i])
            DFS(i);
        p=p->next;
    }
}

void read_graph()
{
    int i,vi,vj,no_of_edges;
    printf("Enter number of vertices:");

    scanf("%d",&n);

    //initialise G[] with a null

    for(i=0;i<n;i++)
    {
        G[i]=NULL;
        //read edges and insert them in G[]

        printf("Enter number of edges:");
        scanf("%d",&no_of_edges);

        for(i=0;i<no_of_edges;i++)
        {
            printf("Enter an edge(u,v):");
            scanf("%d%d",&vi,&vj);
            insert(vi,vj);
        }
    }
}

void insert(int vi,int vj)
{
    node *p,*q;

    //acquire memory for the new node
    q=(node*)malloc(sizeof(node));
    q->vertex=vj;
    q->next=NULL;

    //insert the node in the linked list number vi
    if(G[vi]==NULL)
        G[vi]=q;
    else
    {
        //go to end of the linked list
        p=G[vi];

        while(p->next!=NULL)
            p=p->next;
        p->next=q;
    }
}

函数 DFS() 中的 while 循环终止后回溯是如何发生的？我不明白

谢谢

Answer 1

嗯，这不是 DFS(深度优先搜索)，因为没有搜索任何内容。 DFS 函数所做的就是遍历所有边，将它们的节点标记为已访问。完成后，您只知道这是否是一个连通图 - 如果有任何未访问过的边，则它们尚未被标记，因此无法从 G[0 到达]。