DFS深度优先搜索（非递归）求改错
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define VEXNUM 6
typedef struct ArcNode{
int adjvex;
struct ArcNode*nextarc;
}ArcNode;
typedef struct VNode{
int data;
ArcNode*firstarc;
}VNode;
int visited[VEXNUM];
void CreateGraph(VNode G[],int n){
int i,e;
ArcNode*p,*r;
printf("请输入顶点：");
for(i=0;i<n;i++){
scanf("%d",&G[i].data);
G[i].firstarc=NULL;
}
for(i=0;i<n;i++){
printf("请输入与顶点%d相邻的顶点：",i);
scanf("%d",&e);
while(e!=-1){
p=(ArcNode*)malloc(sizeof(ArcNode));
p->nextarc=NULL;
p->adjvex=e;
if(G[i].firstarc==NULL){
G[i].firstarc=p;
}else{
r->nextarc=p;
}
r=p;
scanf("%d",&e);
}
}
}
int FirstAdj(VNode G[],int v){
if(G[v].firstarc){
return (G[v].firstarc)->adjvex;
}
return -1;
}
int NextAdj(VNode G[],int v){
ArcNode*p;
p=G[v].firstarc;
while(p){
if(visited[p->adjvex]){
p=p->nextarc;
}else{
return p->adjvex;
}
}
return -1;
}
void DFS(VNode G[],int v){
int w;
printf("%d ",G[v].data);
visited[v]=1;
for(w=FirstAdj(G,v);w!=-1;w=NextAdj(G,v)){
if(!visited[w]){
DFS(G,w);
}
}
}
void DFS_2(VNode G[],int v){
int S[VEXNUM];
int top=-1;
int w,k;
visited[v]=1;
S[++top]=v;
while(top!=-1){
k=S[top--];
printf("%d ",G[k].data);
for(w=FirstAdj(G,k);w!=-1;w=NextAdj(G,k)){
if(!visited[w]){
visited[w]=1;
S[++top]=w;
}
}
}
}
void BFS(VNode G[],int v){
int Q[VEXNUM];
int front=-1,rear=-1;
int w;
printf("%d ",G[v].data);
visited[v]=1;
Q[++rear]=v;
while(front<rear){
v=Q[++front];
for(w=FirstAdj(G,v);w!=-1;w=NextAdj(G,v)){
if(!visited[w]){
printf("%d ",G[w].data);
visited[w]=1;
Q[++rear]=w;
}
}
}
}
void main(){
int i;
VNode G[VEXNUM];
CreateGraph(G,VEXNUM);
printf("深度优先搜索(递归)：");
for(i=0;i<VEXNUM;i++){
visited[i]=0;
}
for(i=0;i<VEXNUM;i++){
if(visited[i]==0){
DFS(G,i);
}
}
printf("\n深度优先搜索(非递归)：");
for(i=0;i<VEXNUM;i++){
visited[i]=0;
}
for(i=0;i<VEXNUM;i++){
if(visited[i]==0){
DFS_2(G,i);
}
}
printf("\n广度优先搜索：");
for(i=0;i<VEXNUM;i++){
visited[i]=0;
}
for(i=0;i<VEXNUM;i++){
if(visited[i]==0){
BFS(G,i);
}
}
}
