图的拓扑排序，广度和深度优先搜索

图：邻接表表示方法 如下为无圈图

//函数接口

#ifndef _TOPSORT_H#define _TOPSORT_H#define MAX 20typedef struct EdgeNode{	int vex;	struct EdgeNode *next;}ENode;typedef struct VexNode{	char data;	ENode *first;}VNode;typedef struct graph{	int vexnum;	int edgenum;	VNode vexs[MAX];}Graph;void CreateGraph(Graph *g);int TopSort(Graph G);void Destroy(Graph *g);void DFSTraverse(Graph G);void BFSTraverse(Graph G);#endif
//接口函数定义
#include <stdio.h>#include <string.h>#include "topsort.h"#include <stdlib.h>#define MAX 20int visited[MAX];static void DFS(Graph G,int edge);int TopSort(Graph G){	int i,j;	int index=0; //统计拓扑排序过的总点数 最后判断有无圈	int head=0;  //队列头尾初始化	int rear=0;	int *queue;	int *indegree;	char *tops;	int num=G.vexnum;	ENode *node;	indegree=(int *)malloc(num*sizeof(int));	tops=(char *)malloc(num*sizeof(char));	queue=(int *)malloc(num*sizeof(int)); //用数组来建立队列	memset(indegree,0,num*sizeof(int));  //memset来初始化动态数组	memset(tops,0,num*sizeof(char));	memset(queue,0,num*sizeof(int));	for(i=0;i<num;i++)	{		node=G.vexs[i].first;		while(node!=NULL)		{			indegree[node->vex]++; //统计入度			node=node->next;		}	}	for(i=0;i<num;i++)	{		if(indegree[i]==0)			queue[rear++]=i; //i入队	}	while(head<rear)	{		j=queue[head++];  //j出队		tops[index++]=G.vexs[j].data;		node=G.vexs[j].first;		while(node!=NULL)		{			indegree[node->vex]--; //入度减1			if(indegree[node->vex]==0)				queue[rear++]=node->vex; //邻接点入队			node=node->next; //与node邻接的下个节点		}	}	if(index!=G.vexnum)	{			PRintf("Graph has a cycle!!");		free(indegree);	    free(tops);	    free(queue);		return 1;	}	else	{		printf("TopSort:/n");		for(i=0;i<num;i++)			printf("%2c",tops[i]);		printf("/n");	    free(indegree);	    free(tops);	    free(queue);		return 0;	}}void CreateGraph(Graph *g){	char ver;	int i=0;	int e=-1;	ENode *edge;	printf("Enter vexnum and edgenum:/n");	scanf("%d %d",&g->vexnum,&g->edgenum);	getchar();	printf("Enter the data of vertex:/n");	while('/n'!=(ver=getchar()))		g->vexs[i++].data=ver;	for(i=0;i<g->vexnum;i++)  //Graph初始化		g->vexs[i].first=NULL;	printf("Enter the edge table:/n");	for(i=0;i<g->vexnum;i++)	{		printf("%c:",g->vexs[i].data);		while(1)		{			scanf("%d",&e);			if(e!=-1)			{				edge=(ENode *)malloc(sizeof(ENode));			    edge->vex=e;			    edge->next=g->vexs[i].first;			    g->vexs[i].first=edge;			}			else  //用-1来退出循环				break;		}		printf("/n");	}}static void DFS(Graph G,int edge){	ENode *e;	visited[edge]=1; //将访问过的节点置为1	printf("%2c",G.vexs[edge].data);	e=G.vexs[edge].first;	while(e)	{		if(!visited[e->vex])			DFS(G,e->vex);		e=e->next;	}}void DFSTraverse(Graph G)  //深度优先搜索 递归实现{	int i;	for(i=0;i<G.vexnum;i++)		visited[i]=0; //标记数组初始化	for(i=0;i<G.vexnum;i++)	{		if(!visited[i])			DFS(G,i);	}}void BFSTraverse(Graph G) //广度优先搜索{	int i,tmp;	ENode *e;	int queue[MAX];	int rear,front;	rear=front=0;	for(i=0;i<=G.vexnum;i++)		visited[i]=0; //标记数组初始化	for(i=0;i<G.vexnum;i++)	{		if(!visited[i])		{			visited[i]=1;			printf("%2c",G.vexs[i].data);			queue[rear++]=i; //入队			while(front<rear)			{				tmp=queue[front++];//出队				e=G.vexs[tmp].first;				while(e)				{					if(!visited[e->vex])					{						visited[e->vex]=1;						printf("%2c",G.vexs[e->vex].data);						queue[rear++]=e->vex;					}					e=e->next;				}			}		}	}}void Destroy(Graph *g){	int i;	ENode *e,*tmp;	for(i=0;i<g->vexnum;i++)	{		e=g->vexs[i].first;		while(e!=NULL)		{			tmp=e;			e=e->next;			free(tmp);		}	}}
//main函数入口
#include <stdio.h>#include "topsort.h"int main(int argc, char **argv){	Graph G;	CreateGraph(&G);	TopSort(G);	printf("/nDFSTraverse/n");	DFSTraverse(G);	printf("/nBFSTraverse/n");	BFSTraverse(G);	Destroy(&G);	return 0;}
测试结果：