考试遇难题，向各位求救！！！！！

yeteng6988

数据结构里面的图的周游，可以用邻接矩阵存储或邻接表存储。周游时可以选用广度优先和深度优先两种算法。谢谢各位了我急需啊。

zjwzjw

//========================================
//   图形的广度优先遍历               
// ========================================
#include <stdlib.h>
#define MAXQUEUE 10               // 遍历过程中存储结点队列的最大容量      
#define MAX 9
struct node                       // 图形顶点结构   
{
   int vertex;                    // 顶点信息         
   struct node *nextnode;         // 指下一顶点   
};
typedef struct node *graph;       // 图形的结构申明     
struct node head[9];              // 图形顶点结构数组     
int visited[9];                   // 遍历记录数组         

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;   //存入队列
   return ;
}


//  伫列资料的取出                          

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


//  图形的广度优先搜寻法                    

void bfs(int current)
{
   graph ptr;

   // 处理第一个顶点
   enqueue(current);              // 将顶点存入队列      
   visited[current] = 1;          //记录已遍历过         
   printf("Head[%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("Head[%d] ",ptr->vertex);
         }
         ptr = ptr->nextnode;     //下一个顶点         
      }
   }
}


void main()
{
   graph ptr;
   int node[20][2] = { {1, 2}, {2, 1},  //无向图的声明      
                       {1, 3}, {3, 1},
                       {2, 4}, {4, 2},
                       {2, 5}, {5, 2},
                       {3, 6}, {6, 3},
                       {3, 7}, {7, 3},
                       {4, 8}, {8, 4},
                       {5, 8}, {8, 5},
                       {6, 8}, {8, 6},
                       {7, 8}, {8, 7} };
   int i;

   for ( i = 1; i <= 8; i++ )
   {
      head[i].vertex = i;         // 设定顶点值           
      head[i].nextnode = NULL;    // 清除图形结点      
      visited[i] = 0;             // 设定遍历初值         
   }
   creategraph(node,20);          // 建立图形            
   printf("Graph Adjacency List:\n");    //图形的邻接链表内容
   for ( i = 1; i <= MAX-1; i++ )
   {
      printf("Head(%d) ->",head[i].vertex); // 顶点值      
      ptr = head[i].nextnode;             // 顶点位置     
      while ( ptr != NULL )       // 遍历至链表尾         
      {
         printf(" %d ",ptr->vertex);  // 打印出顶点内容   
         ptr = ptr->nextnode;         // 下一个顶点     
      }  
      printf("\n");                             
   }
   printf("Bfs Graph Treaver:\n");   //图形的广度优先遍历内容
   bfs(1);                           // 从存储的第一顶点广度遍历并打印出遍历过程      
   printf("\n");                 
}

zjwzjw

/* ======================================== */
/*              图形的遍历                  */
/* ======================================== */
#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;     /* 下一个顶点           */
      }
   }
}

zjwzjw

/* ======================================== */
/*              图形的遍历                  */
/* ======================================== */
#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;              /* 下一个顶点   */
   }
}

zjwzjw

/* ---------------------------------------- */
/*  主程式: 建立图形后,将遍历内容印出.      */
/* ---------------------------------------- */
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);
}
}

zjwzjw

以上程序仅供参考学习 ～～

squall_wl

这么长

wenbinjiao

zjwzjw 辛苦了！

yeteng6988

辛苦了，有单独深度优先的更简便的吗？最好是用邻接矩阵表示的。