图的深度和广度优先遍历（C语言）

要求：图用邻接表方式存储，输入一个无向图的信息并存储，实现图的深度优先遍历及广度优先遍历。（输入输出均使用文件的方式实现）

图的示例，该图为不连通图

 1.开始的准备工作如下

#include
#include

#define max 100

typedef struct Edgelink {		//边链表
	char Edge;
	struct Edgelink *next;
} Edge,*Elink;

typedef struct Vertexlink {		//顶点数组
	char Vertex;
	int visited;
	Elink next;
} Vertex[max];

typedef struct Graph {
	int Vnum;					//顶点数目
	Vertex List;
} Graph;

2.创建邻接表的过程如下

void CreateLink(Graph *T) {								//图的创建
	char ch;
	int i,j;
	FILE *fp;
	fp=fopen("shiyan6.txt","r");
	fscanf(fp,"%d",&T->Vnum);
	fscanf(fp,"%c",&ch);
	for(i=1; i<=T->Vnum; i++) {		//头结点
		fscanf(fp,"%c",&(T->List[i].Vertex));
		T->List[i].next=NULL;
		ch=T->List[i].Vertex;
		while(ch!='n') {			//边节点
			if(ch!=' ') {
				Elink p,q;
				p=(Edge*)malloc(sizeof(Edge));
				p->Edge=ch;
				p->next=NULL;
				if(T->List[i].next==NULL)
					T->List[i].next=p;
				else {
					q = T->List[i].next;
					while(q->next) {
						q=q->next;
					}
					q->next=p;
				}
				fscanf(fp,"%c",&ch);
			} else
				fscanf(fp,"%c",&ch);
		}
	}
	fclose(fp);
}

3.深度遍历（DFS）初始化

void DFS(Graph * T) {						//深度遍历初始化
	FILE*fe;
	fe=fopen("shiyan61.txt","w");
	int i;
	for(i=1; i<=T->Vnum; i++) {
		T->List[i].visited=0;
	}
	for(i=1; i<=T->Vnum; i++) {
		if(T->List[i].visited==0) {
			//	T->List[i].visited=1;
			DFS_Link(T,i,fe);
		}
	}
	fe=fopen("shiyan61.txt","a");
	fprintf(fe,"n");
	fclose(fe);
}

深度遍历（DFS）

void DFS_Link(Graph *T,int n,FILE*fe) {		//深度遍历
	int j;
	Elink q;
	T->List[n].visited = 1;
	fe=fopen("shiyan61.txt","a");
	fprintf(fe,"%c",T->List[n].Vertex);
	fclose(fe);
	//printf("%c",T->List[n].Vertex);
	q=T->List[n].next->next;
	while(q!=NULL) {
		if(T->List[q->Edge-'0'].visited!=1) {
			j=q->Edge-'0';
			DFS_Link(T,j,fe);
		}
		q=q->next;
	}
}

4.广度遍历（BFS）初始化

void BFS(Graph * T) {					//广度遍历初始化
	int i;
	for(i=1; i<=T->Vnum; i++) {
		T->List[i].visited=0;
	}
	BFS_Link(T,1);
}

广度遍历（BFS）

void BFS_Link(Graph *T,int t) {			//广度遍历
	Elink P;
	char v;
	char Queue[100];
	int front=0;		//队头
	int rear=0;			//队尾
	T->List[t].visited=1;
	//rear=(rear+1)%100;
	rear=rear+1;
	Queue[rear]=T->List[t].Vertex;
	FILE*fe;
	fe=fopen("shiyan61.txt","a");
	fprintf(fe,"%c",T->List[t].Vertex);
	fclose(fe);
	while(front!=rear||front<(T->Vnum)) {
		front=front+1;
		v=T->List[front].Vertex;
		P=T->List[v-'0'].next->next;
		while(P!=NULL) {
			if(T->List[P->Edge-'0'].visited==0) {
				FILE*fe;
				fe=fopen("shiyan61.txt","a");
				fprintf(fe,"%c",P->Edge);
				fclose(fe);
				T->List[P->Edge-'0'].visited=1;
				//rear=(rear+1)%100;
				rear=rear+1;
				Queue[rear]=P->Edge;
			}
			P=P->next;
		}
	}
}

总代码如下

#include
#include

#define max 100

typedef struct Edgelink {		//边链表
	char Edge;
	struct Edgelink *next;
} Edge,*Elink;

typedef struct Vertexlink {		//顶点数组
	char Vertex;
	int visited;
	Elink next;
} Vertex[max];

typedef struct Graph {
	int Vnum;					//顶点数目
	Vertex List;
} Graph;

void CreateLink(Graph *T);
void DFS(Graph * T);
void BFS(Graph * T);
void DFS_Link(Graph *T,int n,FILE*fe);
void BFS_Link(Graph *T,int t);

int main() {
	Graph *S;
	S = (Graph*)malloc(sizeof(Graph));
	CreateLink(S);
	DFS(S);
	BFS(S);
	return 0;
}

void CreateLink(Graph *T) {								//图的创建
	char ch;
	int i,j;
	FILE *fp;
	fp=fopen("shiyan6.txt","r");
	fscanf(fp,"%d",&T->Vnum);
	fscanf(fp,"%c",&ch);
	for(i=1; i<=T->Vnum; i++) {		//头结点
		fscanf(fp,"%c",&(T->List[i].Vertex));
		T->List[i].next=NULL;
		ch=T->List[i].Vertex;
		while(ch!='n') {			//边节点
			if(ch!=' ') {
				Elink p,q;
				p=(Edge*)malloc(sizeof(Edge));
				p->Edge=ch;
				p->next=NULL;
				if(T->List[i].next==NULL)
					T->List[i].next=p;
				else {
					q = T->List[i].next;
					while(q->next) {
						q=q->next;
					}
					q->next=p;
				}
				fscanf(fp,"%c",&ch);
			} else
				fscanf(fp,"%c",&ch);
		}
	}
	fclose(fp);
}

void DFS(Graph * T) {						//深度遍历初始化
	FILE*fe;
	fe=fopen("shiyan61.txt","w");
	int i;
	for(i=1; i<=T->Vnum; i++) {
		T->List[i].visited=0;
	}
	for(i=1; i<=T->Vnum; i++) {
		if(T->List[i].visited==0) {
			//	T->List[i].visited=1;
			DFS_Link(T,i,fe);
		}
	}
	fe=fopen("shiyan61.txt","a");
	fprintf(fe,"n");
	fclose(fe);
}

void DFS_Link(Graph *T,int n,FILE*fe) {		//深度遍历
	int j;
	Elink q;
	T->List[n].visited = 1;
	fe=fopen("shiyan61.txt","a");
	fprintf(fe,"%c",T->List[n].Vertex);
	fclose(fe);
	//printf("%c",T->List[n].Vertex);
	q=T->List[n].next->next;
	while(q!=NULL) {
		if(T->List[q->Edge-'0'].visited!=1) {
			j=q->Edge-'0';
			DFS_Link(T,j,fe);
		}
		q=q->next;
	}

}

void BFS(Graph * T) {					//广度遍历初始化
	int i;
	for(i=1; i<=T->Vnum; i++) {
		T->List[i].visited=0;
	}
	BFS_Link(T,1);
}

void BFS_Link(Graph *T,int t) {			//广度遍历
	Elink P;
	char v;
	char Queue[100];
	int front=0;		//队头
	int rear=0;			//队尾
	T->List[t].visited=1;
	//rear=(rear+1)%100;
	rear=rear+1;
	Queue[rear]=T->List[t].Vertex;
	FILE*fe;
	fe=fopen("shiyan61.txt","a");
	fprintf(fe,"%c",T->List[t].Vertex);
	fclose(fe);
	while(front!=rear||front<(T->Vnum)) {
		front=front+1;
		v=T->List[front].Vertex;
		P=T->List[v-'0'].next->next;
		while(P!=NULL) {
			if(T->List[P->Edge-'0'].visited==0) {
				FILE*fe;
				fe=fopen("shiyan61.txt","a");
				fprintf(fe,"%c",P->Edge);
				fclose(fe);
				T->List[P->Edge-'0'].visited=1;
				//rear=(rear+1)%100;
				rear=rear+1;
				Queue[rear]=P->Edge;
			}
			P=P->next;
		}
	}
}

输入样例

输出样例（上方为深度遍历结果，下方为广度遍历结果）