图的深度优先遍历.doc

图的管理

 
图的深度优先遍历  
 

 
发表日期：2004年6月12日  出处：soosky拙作  作者：soosky  已经有1585位读者读过此文 
 


/* 这是一个图的的深度优先搜索，我参考清华大学 c 语言版 1997年 4月第一版
   教材中没有构图的函数CreatGraph(),FirstAdjVex()和NextAdjvex()，我在这里写出来了
。
   图的存储结构采用邻接表存储。不过构图时的输入比较复杂，请读者认真读以下说明
   说明：

   假设有顶点 a(1) b(2) c(3) d(4) e(5)
   图如下：
                 (1)
                 (a)
                 /|^ \
                / | \ \
               /  |  \ \
              /   |   \ \
             /    |    \ \
            \/    |     \\/
        (2)(b)----|----->(c)(3)
                  |       \ 
                 \/        \     
                 (e)------>(d)
                 (5)       (4)
   请注意输入时依次输入5个顶点a b c d e，结束输入请输入0，0然后在插入邻接点，邻接
点为插头操作。
   插入邻接点的操作如下：
                       1,5（逗号也输入）1,3       1,2
                       2,3
                       
                       4,1
                       5,4
                       0,0(表示结束输入)

   其的存储结构是：
        (0)[][NULL]
        (1)[a][]-->[2][]->[3][]-->[5][NULL]
        (2)[b][]-->[3][NULL]  
        (3)[c][NULL]
        (4)[d][]-->[1][NULL]
        (5)[e][]-->[5][]-->[4][NULL]
   遍历的顺序如下：
   假如从1号顶点开始遍历：a b c e d

*/
/* 我没有写结点访问函数，因为在这个程序中结点的访问是输出其值，如果你要一个访问函
数可以稍加修改*，我还是一个菜鸟，
   让高手见笑了
   这只是举一个例子，明白后你可以通过MAXVER ,注意要有5各顶点 MAXVER值应为6，依次
类推。的值构造任意个接点，
   在这里加一点我个人的看法：
   教材中给点的编号从0开始，我认为应该从1开始编号。
   如果那样的话教材的算法是有问题的。因为编号从0开始在判断某一顶点是否有邻接顶点
将会有错误(在我程序中是第ERR行
   w的表达式)如果用w>=0判断有邻接顶点那么在什么情况下不存在邻接顶点呢？,因为w>=0
这个表达式是永远成立的。
   
   顶点从0开始编号的算法我也写了出来，请参考：
   如果你认为我的理解有误还请不惜指教。 我的QQ：49186456 OR 358271030*/
#include"stdio.h"
#define OK 1
#define FALSE 0
#define TRUE 1
#define MAXVER 6
typedef struct ArcNode
{
  int adjvex;
  struct ArcNode *nextarc;
}ArcNode;
struct VNode
{
  char info[20];
  ArcNode *firstarc;
};
int CreatGraph(struct VNode *g)
{
  int i,j;
  struct VNode *p;
  ArcNode *q;
 for(p=g+1;p<g+MAXVER;p++)
  {
    printf("Please input the information of the DINGDIAN\n");
    scanf("%s",p->info);
    p->firstarc=NULL;
  }
  do
  {
    p=g;
    printf("(i,j)\n");
    scanf("%d,%d",&i,&j);
    q=(ArcNode *)malloc(sizeof(ArcNode));
    if(!p)
      return FALSE;
    else
      {
	q->adjvex=j;
	q->nextarc=(p+i)->firstarc;
	(p+i)->firstarc=q;
      }
  }while(i!=0&&j!=0);
}
int FirstAdjVex(struct VNode *g,int v)
{
  int w;
  g=g+v;
  w=g->firstarc->adjvex;
  return w;
}
int NextAdjVex(struct VNode *g,int v,int w)
{
   ArcNode *q;
   g=g+v;
   q=g->firstarc;
   while(q->adjvex!=w)
   {
     q=q->nextarc;
   }
   return q->nextarc->adjvex;
}
int visited[MAXVER];
void DFSTravers(struct VNode *g,int v)
{
  int w,time=0;
  for(w=1;w<MAXVER;w++)
     visited[v]=FALSE;
   do
  {
    if(!visited[v])
       DFS(g,v);
       if(v==MAXVER-1)
       {
	  v=1;
	  time++;
       }
       else
       {
	  v++;
	  time++;
       }
  }while(time<MAXVER);
  for(w=1;w<MAXVER;w++)
   visited[w]=FALSE;
}
int DFS(struct VNode *g,int v)
{
   int w;
   visited[v]=TRUE;
   printf("%s",(g+v)->info);
   printf("\n");
   for(w=FirstAdjVex(g,v);w>0;w=NextAdjVex(g,v,w))          /* ERR*/
      if(!visited[w])
	DFS(g,w);
}
main()
{
  int v;
  char Continue='y',Ch='y';
  struct VNode AdjList[MAXVER];
  do
  {
    clrscr();
    CreatGraph(AdjList);
    do
    {
      printf("Please input the start VERTEX ?\b");
      scanf("%d",&v);
      DFSTravers(AdjList,v);
      printf("Do you want choose another VERTEX Y/N ?\b");
      Ch=getchar();
      Ch=getchar();
    }while(Ch=='Y'||Ch=='y');
    printf("Do you want to Creat a new Graphics Y/N ?\b");
    Continue=getchar();
    Continue=getchar();
  }while(Continue=='Y'||Continue=='y');
}



/*下边是编号从0开始的算法：
还请注意，w的表达式写成w>=0会出现严重错误，w表达式写成w>0会出现当某个顶点的邻接顶
点为0号顶点时遍历了不从0号顶点开始
遍历顺序是时的错误（虽然遍历了但顺序不对）。这都是由于取编号从0开始的缘故（你可以
试一试遍历从1，2，3，4 开始看看）。
假如从1开始结果为b c d e a 正确的是：b c d a e
假如从2开始结果为c d e a b 正确的是：c d a b e
假如从3开始结果为d e a b c 正确的是：d a b c e
假如从4开始结果为e d a b c 正确的是：e d a b c
只有从0开始正确。
再次声明，这是我的理解，如果你认为我有错，还请指教，谢谢！
假设有顶点 a(0) b(1) c(2) d(3) e(4)
   图如下：
                 (0)
                 (a)
                 /|^ \
                / | \ \
               /  |  \ \
              /   |   \ \
             /    |    \ \
            \/    |     \\/
        (1)(b)----|----->(c)(2)
                  |       \ 
                 \/        \     
                 (e)----->(d)
                 (4)      (3)
   
  请注意输入时依次输入a b c d e结束输入请输入5，5
                       0,4（逗号也输入）0，2      0,1
                       1,2
                       
                       3,0
                       4,3
                       5,5(表示结束输入)

   其的存储结构是：
        (0)[a][]-->[1][]-->[2][]--[4][NULL]
        (1)[b][]-->[2][NULL]
        (2)[c][NULL]
        (3)[d][]-->[0][NULL]
        (4)[e][]-->[3][NULL]
   遍历的顺序如下：
   假如从0号顶点开始遍历：a b c e d

*/
#include"stdio.h"
#define OK 1
#define FALSE 0
#define TRUE 1
#define MAXVER 5
typedef struct ArcNode
{
  int adjvex;
  struct ArcNode *nextarc;
}ArcNode;
struct VNode
{
  char info[20];
  ArcNode *firstarc;
};
int CreatGraph(struct VNode *g)
{
  int i,j;
  struct VNode *p;
  ArcNode *q;
 for(p=g;p<g+MAXVER;p++)
  {
    printf("Please input the information of the DINGDIAN\n");
    scanf("%s",p->info);
    p->firstarc=NULL;
  }
  do
  {
    p=g;
    printf("(i,j)\n");
    scanf("%d,%d",&i,&j);
    q=(ArcNode *)malloc(sizeof(ArcNode));
    if(!p)
      return FALSE;
    else
      {
	q->adjvex=j;
	q->nextarc=(p+i)->firstarc;
	(p+i)->firstarc=q;
      }
  }while(i!=5&&j!=5);
}
int FirstAdjVex(struct VNode *g,int v)
{
  int w;
  g=g+v;
  w=g->firstarc->adjvex;
  return w;
}
int NextAdjVex(struct VNode *g,int v,int w)
{
   ArcNode *q;
   g=g+v;
   q=g->firstarc;
   while(q->adjvex!=w)
   {
     q=q->nextarc;
   }
   return q->nextarc->adjvex;
}
int visited[MAXVER];
void DFSTravers(struct VNode *g,int v)
{
  int w,time=0;
  for(w=0;w<MAXVER;w++)
     visited[w]=FALSE;
   do
  {
    if(!visited[v])
       DFS(g,v);
       if(v==MAXVER-1)
       {
	  v=0;
	  time++;
       }
       else
       {
	  v++;
	  time++;
       }
  }while(time<=MAXVER);
  for(w=0;w<MAXVER;w++)
    visited[w]=FALSE;
}
int DFS(struct VNode *g,int v)
{
   int w;
   visited[v]=TRUE;
   printf("%s",(g+v)->info);
   printf("\n");
   for(w=FirstAdjVex(g,v);w>0;w=NextAdjVex(g,v,w))          /* ERR*/
      if(!visited[w])
	DFS(g,w);
}
main()
{
  int v;
  char Continue='y',Ch='y';
  struct VNode AdjList[MAXVER];
  do
  {
    clrscr();
    CreatGraph(AdjList);
    do
    {
      printf("Please input the start VERTEX ?\b");
      scanf("%d",&v);
      DFSTravers(AdjList,v);
      printf("Do you want choose another VERTEX Y/N ?\b");
      Ch=getchar();
      Ch=getchar();
    }while(Ch=='Y'||Ch=='y');
    printf("Do you want to Creat a new Graphics Y/N ?\b");
    Continue=getchar();
    Continue=getchar();
  }while(Continue=='Y'||Continue=='y');
}