图遍历应用

图遍历应用



#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,int num)
{
   graph newnode;                
   graph ptr;
   int from;                     
   int to;                       
   int i;

   for ( i = 0; i < num; i++ )   
   {
      from = node[i*2];          
      to = node[i*2+1];          
     
      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;          
}

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");
printf("如 果 有 不 足 之 处 敬 请 原 谅!\n\n");
printf("请 问 你 是 否 要 运 行 以 下 的 程序:\n\n");
printf("   图 的 深 度 遍历 和 广 度 遍 历? Y/N?\n");
c=getch();
if(c!='y'&&'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");
printf("1、图形的广度优先遍历请输入:'g'或'G'\n");
printf("2、图形的深度优先遍历请输入:'s'或'S'\n");
 c=getch();
  switch(c)
{
  case'g':case'G':
   printf("\n请 你 输 入 你需 要 的 起 始 顶 点:\n");
   scanf("%d",&i);
   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);
    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=getch();
if(a!='y'&&'Y')
exit(0);
}
}