图的广度、深度遍历

分手后的思念是犯贱 2022-08-29 04:21 180阅读 0赞

//广度优先：以接近起始节点的程度依次扩展节点，即对下一层节点搜索前，必须先搜索完本层所有节点（队列）
    //深度优先：首先扩展最新产生的节点，每层只对一个节点进行扩展，除非搜索失败或已达到预先约定的最大深度，才会退回去搜索原来忽略节点（栈）#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;
    /。创建图**********************/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("图已经创建完毕***********************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++) 
     {  //printf("v=%d   ",v);  
       v1=v%g.num;  if(mark[v1]==0)   
       DFS(g,v1,mark);
     }
    }typedef  int DATATYPE;    
     
    /***********************8。图的广度周游(改写)**********************/
    void GraphBFS(GRAPH g)//深度优先周游图g中能访问的各个顶点
    { int qidian,v,v1,mark[maxsize]; 
      int v1,v2;
      printf("\n广度周游："); 
      printf("\n请输入起点的下标："); 
      scanf("%d",&qidian); 
      for(v=0;v<g.num;v++) 
      { mark[v]=0; } 
      SEQQUEUE q; 
      QueueInit(&q); 
      mark[qidian]=0;
      QueueIn(&q,qidian);
     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]);
         } 
       }
     }
    }
    /***********************主函数**********************/
    
    void main()
    {
     GRAPH tu;
     GraphCreate(&tu);
     GraphOut(tu);
     GraphDFS(tu);
     GraphBFS(tu);
    }