我试图理解下面的代码,但 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 循环终止后回溯是如何发生的?我不明白
谢谢
最佳答案
嗯,这不是 DFS(深度优先搜索),因为没有搜索任何内容。 DFS 函数所做的就是遍历所有边,将它们的节点标记为已访问。完成后,您只知道这是否是一个连通图 - 如果有任何未访问过的边,则它们尚未被标记,因此无法从 G[0 到达]
。
关于c - 使用邻接表进行深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33583914/