经典算法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",&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,v1,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,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(&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,v,v1,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,v1,mark);  
     }  
    }  
      
    /***********************主函数**********************/  
      
    void main()  
    {  
     GRAPH tu;  
     GraphCreate(&tu);  
     GraphOut(tu);  
     GraphDFS(tu);  
     GraphBFS(tu);  
    }  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。