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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef char InfoType;
typedef char VertexType [10];
typedef struct ArcCell
{
	VRType adj;
	InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
	GraphKind Kind;
}MGraph;
int visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(MGraph G,int v);
int LocateVex(MGraph G,VertexType v)
{
	int i;
	for(i=0;i<G.arcnum;i++)
		if(!strcmp(G.vexs[i],v))
			return i;
	return -1;
}
Status CreateUDN(MGraph *G)
{
	int i,j,k;
	char v1[20],v2[20];
	printf("请输入顶点和弧的个数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i=0;i<G->vexnum;i++)
		scanf("%s",G->vexs[i]);
	for(i=0;i<G->vexnum;i++)
		for(j=0;j<G->vexnum;j++)
		{
			G->arcs[i][j].adj=0;
			G->arcs[i][j].info=NULL;
		 }
		printf("\n请输入边依附的顶点：\n"); 
	for(k=0;k<G->arcnum;k++)
	{
		scanf("%s%s",&v1,&v2);
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);
		G->arcs[i][j].adj=G->arcs[j][i].adj=1;
	}
}
int FirstAdjVex(MGraph G,int v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[v][i].adj)
			return i;
	return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
	int k;
	if(!G.arcs[v][w].adj)
		return -1;
	for(k=w+1;k<G.vexnum;k++)
		if(G.arcs[v][k].adj)
			return k;
}
void DFS(MGraph 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(MGraph G,Status (*Visit)(MGraph G,int v))
{
	VisitFunc=Visit;
	int i;
	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(MGraph G,int v)
{
  printf("%s",G.vexs[v]);
}
int main()
{
	MGraph G;
	int i,j;
	CreateUDN(&G);
	printf("建立的邻接矩阵为：\n");
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			printf("%3d",G.arcs[i][j].adj);
		printf("\n");
	}
	printf("深度优先搜索结果为：\n");
	DFSTraverse(G,func);
	printf("\n");
}