depthfirst.c

这个程序是数据结构的经典算法的实现

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


int create(struct Lnode adjlist[]){
	int num,e,i,v1,v2;
	struct Lnode *p;
	printf("enter the number of vertex.\n");
	scanf("%d",&num);
	printf("enter the number of lines.\n");
	scanf("%d",&e);
	for(i=0;i<num;i++){
		adjlist[i].link=NULL;
		adjlist[i].ver=i;
	}
	printf("enter the vertex1 to vertex2.\n");
	for(i=0;i<e;i++){//E为边数
     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 depthfirst(struct Lnode adjlist[], int v0){
	struct Lnode *p;
	if(adjlist[v0].ver==0){
		adjlist[v0].ver=1;
		printf("%d\t",v0);
	}
	p=adjlist[v0].link;
	while(p!=NULL){
		if(adjlist[p->ver].ver==0)	depthfirst(adjlist,p->ver);	
		p=p->link;
	}
}


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