邻接表的建立及深度优先搜索算法

#define MAX_VERTEX_NUM 20
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0
typedef int Status;
typedef char VertexType[20];
typedef char InfoType;
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
	InfoType *info;
}ArcNode;
typedef struct VNode
{
	VertexType data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
	AdjList vertices;
	int vexnum,arcnum;
	int kind;
}ALGraph;
int visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(ALGraph G,int v);
Status LocateVex(ALGraph G,char *v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(!strcmp(G.vertices[i].data,v))
			return i;
	return -1;
}
Status Create(ALGraph *G)
{
	int i,j,k;
	char v1[20],v2[20];
	ArcNode *p,*q;
	printf("请输入顶点数和边数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i=0;i<G->vexnum;i++)
	{
		scanf("%s",G->vertices[i].data);
		G->vertices[i].firstarc=NULL;
	}
	printf("\n请输入边依附的顶点：\n");
	for(k=0;k<G->arcnum;k++)
	{
		scanf("%s%s",v1,v2);
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->nextarc=G->vertices[i].firstarc;
		G->vertices[i].firstarc=p;
		p->adjvex=j;
		
		q=(ArcNode*)malloc(sizeof(ArcNode));
		q->nextarc=G->vertices[j].firstarc;
		G->vertices[j].firstarc=q;
		q->adjvex=i;
	}
}
int FirstAdjVex(ALGraph G,int v)
{
	ArcNode *p;
	if(p=G.vertices[v].firstarc)
		return p->adjvex;
	return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
	ArcNode *p;
	for(p=G.vertices[v].firstarc;p->adjvex!=w;p=p->nextarc);
		if(p=p->nextarc)
			return p->adjvex;
		else
			return -1;
}
void DFS(ALGraph G,int v)
{
	int w;
	visited[v]=TRUE;
	(*VisitFunc)(G,v);
	for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
		if(!visited[w])
			DFS(G,w);
}
void DFSTraverse(ALGraph G,Status (*visit)(ALGraph G,int v))
{
	int i;
	VisitFunc=visit;
	for(i=0;i<G.vexnum;i++)
		visited[i]=FALSE;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
			DFS(G,i);
}
Status func(ALGraph G,int v)
{
	printf("%s",G.vertices[v].data);
}
int main()
{
	ALGraph G;
	ArcNode *p;
	int i;
	Create(&G);
	printf("建立的邻接表为：\n");
	for(i=0;i<G.vexnum;i++)
	{
		printf("%s ",G.vertices[i].data);
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			printf("%s ",G.vertices[p->adjvex].data);
		printf("\n");
	}
	printf("深度优先搜索结果为：\n");
	DFSTraverse(G,func);
	return 0;
}