邻接表的深度优先遍历

#include<iostream>
using namespace std;
#define max 100
int i,j,m1,m2,n1,n2,w,visited[100];
typedef struct ArcNode {    //边结点
	int adjvex;               //该边所指向的顶点位置 
	struct ArcNode * nextarc;  //指向下一条边的指针 
	int otherthing;
} ArcNode,*Arclist;

typedef struct VNode {
	char data;
	ArcNode *firstarc;        //指向第一条依附该顶点的边的指针 (注意类型为ArcNode) 
} VNode,adjlist[max];

typedef struct {
	adjlist vertices;
	int vexnum,arcnum;
} ALGraph;

int location(ALGraph G,int n)
{
	for(i=0;i<G.vexnum;i++)
	if(G.vertices[i].data==n)return i;
}

void creatgraphal(ALGraph *G)
{
	int i,j,k;
	ArcNode *s;
	printf("请输入顶点数和边数:
");
	cin>>G->vexnum>>G->arcnum;
	printf("请输入顶点信息，每个顶点以回车作为结束:
");
	for(i=0;i<G->vexnum;i++)
	{
	scanf("
%c",&(G->vertices[i].data));
	G->vertices[i].firstarc=NULL;}
	printf("请输入边的信息(输入格式为:i,j)：
");
	for(k=0;k<G->arcnum;k++)
	{
		scanf("
%d,%d",&i,&j);//读入边<Vi,Vj>的顶点对应序号
		s=new ArcNode;
		s->adjvex=j;
		s->nextarc=G->vertices[i].firstarc;
		G->vertices[i].firstarc=s;
		s=new ArcNode;
		s->adjvex=i;
		s->nextarc=G->vertices[j].firstarc;
		G->vertices[j].firstarc=s;	
	}	
}
void DFS(ALGraph *G, int i){
    visited[i] = 1;  
    printf("%c ", G->vertices[i].data);  
    ArcNode *p;
    p = G->vertices[i].firstarc;
    while(p){
        if(!visited[p->adjvex]){
            DFS(G,p->adjvex); //递归深度遍历
        }
        p=p->nextarc;
    }
}


/**
 * 深度优先遍历
 */
void DFSTraverse(ALGraph *G){
    int i;  
    for (i=0; i<G->vexnum;++i){ 
        visited[i] = 0;  //初始化访问数组visited的元素值为false
    }
    for (i=0; i<G->vexnum; ++i){
        if(!visited[i]){ //节点尚未访问
            DFS(G,i);
        }
    }
}
void printfALGraph(ALGraph *G)
{
	Arclist p;
	printf("深度优先遍历结果："); 
	for(i=0;i<G->vexnum;i++)
	{
		p=new ArcNode;
		printf("顶点：%c",G->vertices[i].data);
		p=G->vertices[i].firstarc;
		while(p!=NULL)
		{
			printf("→:%d ",p->adjvex);
			p=p->nextarc;
		}
		printf("
");
	}
}
int main() {
	ALGraph G;
	creatgraphal(&G);
   DFSTraverse(&G);
    printfALGraph(&G);
}