经典算法8：检索与周游之广度和深度优先遍历图

概述经典算法8：检索与周游之广度和深度优先遍历图

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

    #include <stdio.h>      typedef  int  datatype;   /*假定线性表元素的类型为整型*/      #define  maxsize  1024    /*假定线性表的最大长度为1024*/      # define n 100            /* 图的顶点最大个数 */      typedef char VEXTYPE;  /* 顶点的数据类型 */      typedef float ADJTYPE;  /* 权值类型 */      typedef struct      {           VEXTYPE vexs[n] ;  /* 顶点信息数组 */          ADJTYPE arcs[n][n] ; /* 边权数组 */          int num ;    /* 顶点的实际个数 */      }GRAPH;            /***********************1。置空图**********************/      voID GraphInit(GRAPH  *L)      {       L->num=0;      }            /***********************2。求结点数**********************/      int GraphVexs(GRAPH  *L)      {       return(L->num);      }            /***********************3。创建图**********************/      voID GraphCreate(GRAPH  *L)      {       int i,j;       GraphInit(L);       printf("请输入顶点数目：");       scanf("%d",&L->num);       printf("请输入各顶点的信息(单个符号）：");       for(i=0;i<L->num;i++)       {        fflush(stdin);        scanf("%c",&L->vexs[i]);       }       printf("请输入边权矩阵的信息：");       for(i=0;i<L->num;i++)       {        for(j=0;j<L->num;j++)        {         scanf("%f",&L->arcs[i][j]);        }       }       printf("图已经创建完毕！");      }            /***********************4。图的输出**********************/      voID GraphOut(GRAPH  L)      {           int i,j;           printf("\n图的顶点数目为：%d",L.num);           printf("\n图的各顶点的信息为：\n");           for(i=0;i<L.num;i++)              printf("%c  ",L.vexs[i]);           printf("\n图的边权矩阵的信息为：\n");           for(i=0;i<L.num;i++)           {                for(j=0;j<L.num;j++)                {                   printf("%6.2f ",L.arcs[i][j]);                }                printf("\n");           }           printf("图已经输出完毕！");      }            /***********************5。图的深度周游**********************/      voID DFS(GRAPH  g,int qIDian,int mark[])      //从第qIDian个点出发深度优先周游图g中能访问的各个顶点      {           int v1;           mark[qIDian]=1;           printf("%c   ",g.vexs[qIDian]);           for(v1=0;v1<g.num;v1++)           {               if(g.arcs[qIDian][v1]!=0&&mark[v1]==0)                  DFS(g,v1,mark);           }      }      /***********************6。图的深度周游**********************/      voID GraphDFS(GRAPH  g)      //深度优先周游图g中能访问的各个顶点      {       int qIDian,v,mark[maxsize];       printf("\n深度周游：");       printf("\n请输入起点的下标：");       scanf("%d",&qIDian);       for(v=0;v<g.num;v++)       {        mark[v]=0;       }       for(v=qIDian;v<g.num+qIDian;v++)       {        v1=v%g.num;        if(mark[v1]==0)         DFS(g,mark);       }      }      typedef  int DATATYPE;     //队列元素的数据类型      typedef  struct      {         DATATYPE data[maxsize]; //队中元素         int front,rear;   //队头元素下标、队尾元素后面位置的下标      } SEQQUEUE;      /*****************************************************************************/      voID QueueInit(SEQQUEUE *sq)      //将顺序循环队列sq置空（初始化）      {         sq->front=0;         sq->rear=0;      }      /*****************************************************************************/      int QueueIsEmpty(SEQQUEUE sq)      //如果顺序循环队列sq为空，成功返回1，否则返回0      {         if (sq.rear==sq.front)             return(1);         else            return(0);      }       /*****************************************************************************/      int QueueFront(SEQQUEUE sq,DATATYPE *e)      //将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0      {       if (QueueIsEmpty(sq))           { printf("queue is empty!\n");return 0;}          else          { *e=sq.data[(sq.front)]; return 1;}      }      /*****************************************************************************/      int QueueIn (SEQQUEUE *sq,DATATYPE x)      //将元素x入队列sq的队尾，成功返回1，失败返回0      {        if (sq->front==(sq->rear+1)%maxsize)       {          printf("queue is full!\n");        return 0;       }       else       {           sq->data[sq->rear]=x;        sq->rear=(sq->rear+1)%maxsize;        return(1);       }      }      /*****************************************************************************/      int QueueOut(SEQQUEUE *sq)      //将队列sq队首元素出队列，成功返回1,失败返回0      {          if (QueueIsEmpty(*sq))          {          printf("queue is empty!\n");        return 0;       }          else          {                sq->front=(sq->front+1)%maxsize;        return  1;          }      }      /***********************7。图的广度周游**********************/      voID BFS(GRAPH g,int v,int mark[])      //从v出发广度优先周游图g中能访问的各个顶点      {            int v1,v2;           SEQQUEUE q;           QueueInit(&q);            QueueIn(&q,v);           mark[v]=1;           printf("%c   ",g.vexs[v]);           while(QueueIsEmpty(q)==0)             {                 QueueFront(q,&v1);                QueueOut(&q);                 for(v2=0;v2<g.num;v2++)                {                     if(g.arcs[v1][v2]!=0&&mark[v2]==0)                     {                           QueueIn(&q,v2);                          mark[v2]=1;                          printf("%c   ",g.vexs[v2]);                     }                    }           }      }      /***********************8。图的广度周游**********************/      voID GraphBFS(GRAPH  g)      //深度优先周游图g中能访问的各个顶点      {       int qIDian,mark[maxsize];       printf("\n广度周游：");       printf("\n请输入起点的下标：");       scanf("%d",&qIDian);       for(v=0;v<g.num;v++)       {        mark[v]=0;       }       for(v=qIDian;v<g.num+qIDian;v++)       {        v1=v%g.num;        if(mark[v1]==0)         BFS(g,mark);       }      }            /***********************主函数**********************/            voID main()      {       GRAPH tu;       GraphCreate(&tu);       GraphOut(tu);       GraphDFS(tu);       GraphBFS(tu);      }  

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的经典算法8：检索与周游之广度和深度优先遍历图全部内容，希望文章能够帮你解决经典算法8：检索与周游之广度和深度优先遍历图所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。