深度搜索

#include <stdio.h>
#include <stdlib.h>
#define N 20
typedef struct link
{
	int data;//代表数据域
	struct link *next;//代表指针域,指向后继元素
}link;//link为节点名,每个节点都是一个link结构体

link *b[N];//头节点
//定义链队列的类型
typedef struct linkqueue{
	link *front;//队头指针
	link *rear;//队尾指针
}linkq;

linkq q;//定义一个链队列

//初始化链队列
void initqlink(){
	q.front=(link *)malloc(sizeof(link));
	if (!q.front)
		exit(0);
	q.front->next=NULL;
	q.rear=q.front;//空队列
}

//入队(插入)
void enqlink(int e){
	link *p;
	p=(link *)malloc(sizeof(link));
	if (!p)
		exit(0);
	p->data=e;
	p->next=NULL;
	q.rear->next=p;//连接作用
	q.rear=p;//修改队尾指针
}

//出队(删除)
int deqlink(){
	link *p;
	int x;
	if(q.rear==q.front){
		printf("空队列,不进行删除\n");
		exit(0);
	}
	p=q.front->next;
	x=p->data;
	q.front->next=p->next;
	if(p==q.rear)//如果队尾指针没有,空队列
		q.rear=q.front;
	free(p);
	return x;

}
//创建邻接链表
void creat(int n){
	int u,v;
	link *p;
	for(u=0;u<n;u++)
		b[u]=NULL;
	scanf("%d%d",&u,&v);
	while(u>=0)
	{
		p=(link*)malloc(sizeof(link));
		p->data=v;
		p->next=b[u];
		b[u]=p;
		scanf("%d%d",&u,&v);
	}
}
//遍历
void output(int n){
	link *p;
	int u;
	for(u=0;u<n;u++)
	 {
		printf("%5d",u);
		p=b[u];
		while(p)
		{
			printf("->");
			printf("%2d",p->data);
			p=p->next;
		}
		printf("\n");
	}
}
//深度优先搜索
int vst[N]={0};
void dfs(int u){
    link *p;
    int v;
    printf("%d ",u);
    vst[u]=1;       //已被访问

    p=b[u];
    while(p)
    {
        v=p->data;
        if(vst[v]==0)
            dfs(v);         //递归
        p=p->next;
    }

}
//广度优先搜索
int bvst[N]={0};
void bsf(int u){
    link *p;
    int v,x;
    printf("%d ",u);
    bvst[u]=1;
    enqlink(u);
    while(q.front!=q.rear){
    v=deqlink();
    p=b[v];
    while (p)
    {
    x=p->data;
    if(bvst[x]==0){
        printf("%d ",x);
        bvst[x]=1;
        enqlink(x);
    }
    p=p->next;
    }
    }
}
void main(){
	initqlink();
	creat(6);
	printf("邻接表为:\n");
	output(6);
	printf("深度优先搜索结果:");
    dfs(0);
    printf("\n");
    printf("广度优先搜索结果:");
    bsf(0);
}