widthfirst.c

这个也是个数据结构的经典算法

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#define MAX 20
#define LEN sizeof(struct queue)
struct Lnode{//边（弧）结点的类型定义
	int  ver;   //边（弧）的另一顶点的在数组中的位置
	struct Lnode *link; //指下一条边（弧）结点的指针
};
struct Lnode adjlist[MAX];// 邻接点链表的头指针所对应的数组

struct queue{
	struct queue *next;
	int input;
};
int i=0;
struct queue *head;
struct queue *t;
struct queue *top=NULL;

void iniqueue(int input){
	t=(struct queue *)malloc(LEN);
	t->input=input;
	if(top==0) i=0;
	if(i==0){  head=t;i=1;t->next=t;top=t;}
	else{ top->next=t;t->next=head;}
	top=t;
}

int dlqueue(){
	int temp;
	struct queue *tmp;
	tmp=head;
	temp=tmp->input;
	head=head->next;
	free(tmp);
	return(temp);
}

int create(struct Lnode adjlist[]){
	int num,i,e,v1,v2;
	struct Lnode *p;
	printf("enter the number of vertex.\n");
	scanf("%d",&num);
	for(i=0; i<num; i++){
		adjlist[i].link=NULL;
		adjlist[i].ver=i;
	}
	adjlist[i].link=NULL;
	printf("enter the number of lines.\n");
	scanf("%d",&e);	
	for(i=0;i<e; i++){//E为边数
		printf("enter the vertex1 to vertex2.\n");
		scanf("%d %d",&v1,&v2);	//读入一条边
		if(v1<0 || v2<0) break;	// 数据输入的终止条件
		p=(struct Lnode *)malloc(sizeof(struct Lnode));
		p->ver=v2;
		p->link=adjlist[v1].link; adjlist[v1].link=p; //插入在链表首部
		p=(struct Lnode *)malloc(sizeof(struct Lnode));
		p->ver=v1;
		p->link=adjlist[v2].link;
		adjlist[v2].link=p;
    }
	return(num); // 返回图的结点数
}

void BFS (struct Lnode adjlist[], int v0){
	struct Lnode *p;
	if(adjlist[v0].ver==0){
		adjlist[v0].ver=1;
		printf("%d",v0);
		iniqueue(v0);
	}
    while(head!=top){
		v0=dlqueue();
		p=adjlist[v0].link;
		while(p!=NULL){
			if(adjlist[p->ver].ver==0){
				adjlist[p->ver].ver=1; 
				printf("%d",p->ver);
				iniqueue(p->ver);
	        }
			p=p->link;
		}
	}
} 

void main(){
	int num=0,i=0;
	num=create(adjlist);	
	for(i=0;i<num;i++)	adjlist[i].ver=0;
	for(i=0;i<num;i++) BFS(adjlist,i); // 调用对图G 深度优先搜索算法
}