图(邻接表和深度遍历).cpp

实现了循环便利一棵树

#define Max_Vertex_Num 20
#define Status int
#define OVERFLOW -2
#define OK 1
#define FALSE 0
#define TRUE 1
#include <stdio.h>
#include <stdlib.h>
typedef  int VetexType;
typedef struct ArcNode  { int adjvex;
                          struct ArcNode *nextarc;
						} ArcNode;
typedef struct VNode    { VetexType data;
                          ArcNode *firstarc;
						} VNode, AdjList[Max_Vertex_Num];
typedef struct  { AdjList vertices;
                  int vexnum, arcnum;
				  int kind;
				} Graph ;
typedef int Boolean; /*FALSE、TRUE符号常量分别表示0、1*/
Boolean visited[Max_Vertex_Num];
Status (* VisitFunc)(int v);
int count=0;

void main()
{ Graph L;
  void CreateGraph(Graph &L);
  void DFSTraverse(Graph G, Status (* visit)(int v));
  void DFS(Graph G, int v);
  Status PrintE(VetexType e); 
  CreateGraph(L);
  DFSTraverse(L,PrintE);
}

Status PrintE(VetexType e) 
{ printf("%d\t", e); return OK; }

void CreateGraph(Graph &L)
{  int x,y=0,i,t;
   ArcNode *p,*s;
   printf("请输入有向图的顶点个数：");
   scanf("%d%*c",&x);
   L.vexnum=x; 
   L.kind=0;//图的种类(有向图0,有向网1,无向图2,无向网3)
   printf("\n注意，顶点信息采用整型值表达，若有4个顶点分别用1、2、3、4表述。\n按由小到大顺序输入邻接点数据，-1结束输入!\n\n");
   for(t=0;t<L.vexnum;t++) L.vertices[t].data=t+1;
   for(t=0;t<L.vexnum;t++) L.vertices[t].firstarc=NULL;
   for(t=0;t<L.vexnum;t++)
   { printf("请输入第%d个顶点的邻接点信息：",t+1);
	 scanf("%d%*c", &i);
	 while(i>=0)
	 { if(i>L.vexnum||i==0) 
		{  printf("\n邻接点数据不在正常值范围(注意若有4个顶点分别用1、2、3、4表达邻接点)。请重输！\n\n");
	       p=L.vertices[t].firstarc; L.vertices[t].firstarc=NULL;
		   while(p) { s=p->nextarc; free(p); p=s; } 
	       t--;
           while(i>=0) scanf("%d%*c", &i);
		   break;
		}
	   else
		{  if(!(s=(ArcNode*)malloc(sizeof(ArcNode))))
		      printf("分配空间失败\n"), exit(OVERFLOW);
		   y++;
	       p=L.vertices[t].firstarc;
		   s->adjvex=i-1;
		   s->nextarc=p;  
           L.vertices[t].firstarc=s;
		}
	   scanf("%d%*c", &i);
	 }	
   } 
   L.arcnum=y;
}

void DFSTraverse(Graph G, Status (* visit)(int v))
{  void DFS(Graph G, int v);
   int v;
   VisitFunc=visit;
   for(v=0; v<G.vexnum; ++v) visited[v]=FALSE;
   printf("\n深度优先遍历结果如下：\n");
   for(v=0; v<G.vexnum; ++v)
      if(!visited[v]) DFS(G, v);
   printf("\n\n");
}

void DFS(Graph G, int v)
{  int FirstAdjVex(Graph G, int v);
   int NextAdjVex(Graph G, int v,int w);
   int w;
   visited[v]=TRUE; 
   VisitFunc(G.vertices[v].data); count++;
   if(count!=G.vexnum)
     for(w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G,v,w))
        if(!visited[w]) DFS(G,w);
}

Status FirstAdjVex(Graph G, int v)
{  int a;
   if(G.vertices[v].firstarc!=NULL)
      a=G.vertices[v].firstarc->adjvex;
   else a=-1;
   return a;
}

Status NextAdjVex(Graph G, int v,int w)
{  int a;
   ArcNode *p;
   p=G.vertices[v].firstarc;
   if(p!=NULL)
   {  while(p->nextarc!=NULL)
	     if(p->adjvex==w) {a=p->nextarc->adjvex; break;}
	     else p=p->nextarc;
   }
   else a=-1;
   return a;
}