图的深度遍历.cpp

完成输入图

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define MAX_VERTEX_NUM 20
typedef enum{D,U}kind;
typedef struct ArcNode
{
   int adjvex;     //该弧指向的顶点的位置
   struct ArcNode *nextarc;    //指向下一条弧的指针
   int  *info;    //该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
	char data;   //顶点信息
	ArcNode *firstarc;   //指向第一条依附于该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct 
{
	AdjList vertices;
	int vexnum,arcnum;  //图的当前顶点数和弧数
    int kind;    //图的种类标志
}ALGraph;
int visited[MAX_VERTEX_NUM];
int vexnum,arcnum;
void CreateDG(ALGraph &G)    //采用邻接表存储表示，构造有向图
{
	ArcNode *p;
	printf("请输入当前图的顶点数！\n");
    scanf("%d",&G.vexnum);
	fflush(stdin);
    printf("请输入当前图的弧数！\n");
	scanf("%d",&G.arcnum);
	fflush(stdin);
	for(int i=0;i<G.vexnum;i++)
   {  
	   printf("请输入顶点\n");
	   scanf("%c",&G.vertices[i].data);
	   fflush(stdin);
	   G.vertices[i].firstarc=NULL;
   }
	for(int k=0;k<G.arcnum;++k)
    {
	   int i,j;
	   printf("请输入弧的信息!\n");
	   scanf("%d,%d",&i,&j);
	   p=(ArcNode*)malloc (sizeof(ArcNode));
	   p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;
    }
}
void print(ALGraph &G)
 {
	printf("请输出图中的结点\n");
	for(int i=0;i<G.vexnum;i++)
	{
		printf("%c\n",G.vertices[i].data);
	}
 }

int FirstAdjVex(ALGraph &G,int v)
{
	if(G.vertices[v].firstarc) 
	{
		return G.vertices[v].firstarc->adjvex;
	}
	else 
	{
		return -1;
	}
}
int NextAdjVex(ALGraph &G,int v,int w)
{
	w=G.vertices[v].firstarc->adjvex;
	if(G.vertices[w].firstarc) 
	{
		return G.vertices[w].firstarc->nextarc->adjvex;
	}
	else
	{
		return -1;
	}
}
void DFS(ALGraph &G,int v)
{   
	visited[v] = 1;
	
	printf("%c\n",G.vertices[v].data);
	int w=0;
    for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
	{
		if(visited[w]==0)
		{
			DFS(G,w);
		}
	}
}
void DFSTraverse(ALGraph &G)
{
	
	for(int v=0;v<G.vexnum;++v)
	{
		visited[v]=0;
	}
    for(v=0;v<G.vexnum;++v)
	{	
		if(visited[v]==0) 
		{
			DFS(G,v);
		}
	}
}



void main()
{
	ALGraph S;
	printf("请您输入要创建的图的种类！\n");
	char c;

    scanf("%c",&c);
	switch(c)
	{
	case 'D':  CreateDG(S);   //构造有向图D
	//case U: CreateUDG(S); break;;//构造无向图G
	}
	print(S);
    printf("进行深度优先探索:\n");
	printf("深度遍历结点为\n");
	DFSTraverse(S);
	printf("\n");

	

}