main.cpp

图的遍历算法的演示

 // ========================================  
 //              图形的遍历                   
 // ========================================  
#include<stdio.h>
#include <stdlib.h>
#define MAXQUEUE 70              // 伫列的最大容量        

struct node                        // 图形顶点结构宣告      
{
   int vertex;                     // 顶点资料              
   struct node *nextnode;          // 指下一顶点的指标      
};
typedef struct node *graph;        // 图形的结构新型态      
struct node head[61];               // 图形顶点结构数组      
int visited[61];                    // 遍历记录数组          

int queue[MAXQUEUE];               // 伫列的数组宣告        
int front = -1;                    // 伫列的前端            
int rear = -1;                     // 伫列的后端            

 // ----------------------------------------  
 //  建立图形                                 
 // ----------------------------------------  
void creategraph(int node[][2],int num)
{
   graph newnode;                  // 新顶点指标            
   graph ptr;
   int from;                       // 边线的起点            
   int to;                         // 边线的终点            
   int i;

   for ( i = 0; i < num; i++ )     // 读取边线的回路        
   {
      from =node[i][0];            // 边线的起点	  
      to = node[i][1];            // 边线的终点
	  //printf("[%d]->[%d]\n",from,to);	       
       // 建立新顶点记忆体  
      newnode = (graph ) malloc(sizeof(struct node));
      newnode->vertex = to;        // 建立顶点内容          
      newnode->nextnode = NULL;    // 设定指标初值          
      ptr =&(head[from]);         // 顶点位置              
       while ( ptr->nextnode != NULL )  // 遍历至链表尾 
         ptr = ptr->nextnode;          // 下一个顶点        
     ptr->nextnode = newnode;         // 插入结尾
	            
   }
  
   
}

 // ----------------------------------------  
 //  伫列资料的存入                           
 // ----------------------------------------  
int enqueue(int value)
{
   if ( rear >= MAXQUEUE )         // 检查伫列是否全满      
      return -1;                   // 无法存入              
   rear++;                         // 后端指标往前移        
   queue[rear] = value;            // 存入伫列              
   return 1;
}

 // ----------------------------------------  
 //  伫列资料的取出                           
 // ----------------------------------------  
int dequeue()
{
   if ( front  == rear )           // 检查伫列是否是空      
      return -1;                   // 无法取出              
   front++;                        // 前端指标往前移        
   return queue[front];            // 伫列取出              
}

 // ----------------------------------------  
 //  图形的广度优先搜寻法                     
 // ----------------------------------------  
void bfs(int current)
{
   graph ptr;

    // 处理第一个顶点  
   enqueue(current);               // 将顶点存入伫列        
   visited[current] = 1;           // 记录已遍历过          
   printf("[%d]     ",current);    // 印出遍历顶点值        
   while ( front != rear )         // 伫列是否是空的        
   {
      current = dequeue();         // 将顶点从伫列取出      
      ptr = head[current].nextnode;    // 顶点位置          
      while ( ptr != NULL )            // 遍历至链表尾      
      {
         if ( visited[ptr->vertex] == 0 )  // 如过没遍历过  
         {
            enqueue(ptr->vertex);      // 递回遍历呼叫      
            visited[ptr->vertex] = 1;  // 记录已遍历过      
             // 印出遍历顶点值  
			printf("[%d]    ",ptr->vertex);
         }
         ptr = ptr->nextnode;      // 下一个顶点            
      }

   }
   
}

 // ----------------------------------------  
 //  图形的深度优先搜寻法                     
 // ----------------------------------------  
void dfs(int current)
{
   graph ptr;

   visited[current] = 1;           // 记录已遍历过        
   printf("[%d]    ",current);    // 印出遍历顶点值      
   ptr = head[current].nextnode;   // 顶点位置            
   while ( ptr != NULL )           // 遍历至链表尾        
   {
      if ( visited[ptr->vertex] == 0 )   // 如过没遍历过  
         dfs(ptr->vertex);               // 递回遍历呼叫  
      ptr = ptr->nextnode;               // 下一个顶点  
	  
   }
}

 

 // ----------------------------------------  
 //  主程式: 建立图形后,将遍历内容印出.       
 // ----------------------------------------  
void main()
{//clrscr();

while(1)
{
   char c,a;
   graph ptr;
   int i;
   int node[60][2] = { {1, 10}, {10, 1},   // 边线数组        
         {2, 10}, {10, 2},
         {2, 3}, {3, 2},
         {3, 4}, {4, 3},
         {3, 12}, {12, 3},
         {4, 13}, {13, 4},
         {4, 5}, {5, 4},
         {5, 6}, {6, 5},
         {5, 7}, {7, 5},
         {7, 8}, {8, 7},
         {9, 10}, {10, 9},
         {10, 11}, {11, 10},
         {11, 14}, {14, 11},
         {11, 12}, {12, 11},
         {12, 15}, {15, 12},
         {12, 13}, {13, 12},
         {13, 16}, {16, 13},
         {14, 17}, {17, 14},
         {14, 18}, {18, 14},
         {15, 19}, {19, 15},
         {16, 20}, {20, 16},
         {17, 18}, {18, 17},
         {18, 23}, {23, 18},
         {18, 19}, {19, 18},
         {19, 23}, {23, 19},
         {19, 24}, {24, 19},
         {19, 20}, {20, 19},
         {20, 21}, {21, 20},
         {22, 23}, {23, 22},
         {24, 25}, {25,24}
         };
//clrscr();
printf("\n\n\n");
printf(" //------------------------------------------------------ \n");
printf(" //                 欢 迎 使 用 本 程 序                  \n");
printf(" //------------------------------------------------------ \n");
printf("      本 程 序 是 有 关 图 的 遍 历 的 算 法 演 示,\n\n");
printf("      因时间关系,如 果 有 不 足 之 处 敬 请 原 谅!\n\n");
printf("      请 问 你 是 否 要 运 行 以 下 的 程 序:\n\n");
printf("      图 的 深 度 遍 历 和 广 度 遍 历? Y/N?\n");
c=getchar();
getchar();
if(c!='y'&&c!='Y')
exit(0);
// clrscr();

printf("\n\n");
printf("请 注 意 以 下 为 各 城 市 的 代 码:\n\n");

printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");
printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");
printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");
printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");
printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");

   for (i=1;i<=25;i++ )
   {
	  
      head[i].vertex=i;          // 设定顶点值            
      head[i].nextnode=NULL;     // 清除图形指标          
      visited[i]=0;              // 设定遍历初值          
   }
   creategraph(node,60);           // 建立图形              
   printf("图 形 的 邻 接 链 表 内 容:\n");
   for (i=1;i<=25;i++)
   {  //if(i%3==0)printf("\n");
      printf("顶点%d=>",head[i].vertex);  // 顶点值        
      ptr=head[i].nextnode;              // 顶点位置      
      while(ptr!=NULL)        // 遍历至链表尾          
      {
		printf("%d  ",ptr->vertex);   // 印出顶点内容      
		ptr=ptr->nextnode;          // 下一个顶点        
      }
	  printf("\n\n");
   }
printf("\n\n");
printf("请 选 择 你 需 要 的 操 作\n");
printf("1、图形的广度优先遍历请输入:'g'或'G'\n");
printf("2、图形的深度优先遍历请输入:'s'或'S'\n");
 c=getchar();
 getchar();
  switch(c)
{
  case'g':case'G':
   printf("\n请 你 输 入 你 需 要 的 起 始 顶 点:\n");
   scanf("%d",&i);
   getchar();
   //clrscr();
   printf("\n\n");
   printf("请 注 意 以 下 为 各 城 市 的 代 码:\n\n");
   printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");
   printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");
   printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");
   printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");
   printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");

   printf("图  形  的  广  度  优  先  遍  历  的  顶  点  内  容:\n");
   bfs(i);                         // 印出遍历过程          
   printf("\n");      //     换行       
   break;
 case's':case'S':
    printf("\n请 输 入 你 需 要 的 起 始 顶 点:\n");
    scanf("%d",&i);
	getchar();
    //clrscr();
   printf("\n\n");
    printf("请 注 意 以 下 为 各 城 市 的 代 码:\n\n");
    printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");
    printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");
    printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");
    printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");
    printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");

    printf("图  形  的  深  度  优  先  遍  历  的  顶  点  内  容:\n");
    dfs(i);                         // 印出遍历过程        
    printf("\n");                   // 换行                
     break;
}
printf("\n请 问 你 是 否 要 继 续:y/n");
a=getchar();
printf("%c ",a);
getchar();
if(a!='y'&&'Y')exit(0);
}
}