返回顶部

收藏

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

更多
    #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",&amp;L->num);  
     printf("请输入各顶点的信息(单个符号):");  
     for(i=0;i<L->num;i++)  
     {  
      fflush(stdin);  
      scanf("%c",&amp;L->vexs[i]);  
     }  
     printf("请输入边权矩阵的信息:");  
     for(i=0;i<L->num;i++)  
     {  
      for(j=0;j<L->num;j++)  
      {  
       scanf("%f",&amp;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&amp;&amp;mark[v1]==0)  
                DFS(g,v1,mark);  
         }  
    }  
    /***********************6。图的深度周游**********************/  
    void GraphDFS(GRAPH  g)  
    //深度优先周游图g中能访问的各个顶点  
    {  
     int qidian,v,v1,mark[maxsize];  
     printf("\n深度周游:");  
     printf("\n请输入起点的下标:");  
     scanf("%d",&amp;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,v1,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(&amp;q);   
         QueueIn(&amp;q,v);  
         mark[v]=1;  
         printf("%c   ",g.vexs[v]);  
         while(QueueIsEmpty(q)==0)    
         {   
              QueueFront(q,&amp;v1);  
              QueueOut(&amp;q);   
              for(v2=0;v2<g.num;v2++)  
              {  
                   if(g.arcs[v1][v2]!=0&amp;&amp;mark[v2]==0)  
                   {   
                        QueueIn(&amp;q,v2);  
                        mark[v2]=1;  
                        printf("%c   ",g.vexs[v2]);  
                   }  
                  }  
         }  
    }  
    /***********************8。图的广度周游**********************/  
    void GraphBFS(GRAPH  g)  
    //深度优先周游图g中能访问的各个顶点  
    {  
     int qidian,v,v1,mark[maxsize];  
     printf("\n广度周游:");  
     printf("\n请输入起点的下标:");  
     scanf("%d",&amp;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,v1,mark);  
     }  
    }  

    /***********************主函数**********************/  

    void main()  
    {  
     GRAPH tu;  
     GraphCreate(&amp;tu);  
     GraphOut(tu);  
     GraphDFS(tu);  
     GraphBFS(tu);  
    }  

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论