C语言数据结构邻接矩阵的深度优先搜索-DFS

以你之姓@ 2022-01-22 04:37 249阅读 0赞

//邻接矩阵的深度优先搜索-DFS

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define VERTEXNUM 100 //最大顶点数
    #define MAXSIZE 1024
    typedef char*VertexType;//顶点数据的类型
    #define OK 1
    #define ERROR 0
    typedef int  ArcType;//边的数据类型  权重的数据类型
    typedef struct matrixgraph
    {
        VertexType vexs[VERTEXNUM];//顶点数int
        ArcType arcs[VERTEXNUM][VERTEXNUM];//权重的二维数组
        int n,e;//边数和顶点数
    }MatricGraph;//邻接矩阵的结构体
    typedef struct queue{
    
        int data[MAXSIZE];//数组
          int rear,front;//头指针和尾指针
    }Seq_Queue;//循环队列的结构体
    int visited[VERTEXNUM];//记录状态的数组
    int  create_matrixgraph(MatricGraph*G);//创建邻接矩阵
    void test();//测试函数
    int Locate_vex(MatricGraph*G,VertexType vex);//定位函数
    Seq_Queue* init_queue();//置空循环队列
    int pop_queue(Seq_Queue*Q,int *x);//出队
    int push_queue(Seq_Queue*Q,int x);//入队
    int  empty_queue(Seq_Queue*Q);//判断队列是否为空
    //void BFSTraversAL(MatricGraph*G);//广度优先搜索的第一个函数
    //void BFSM(MatricGraph*G,int i);//广度优先搜索的第二个函数
    void DFSTraverse_matrixgraph(MatricGraph*G);//邻接矩阵的深度优先搜索
    void DFSM(MatricGraph*G,int i);//深度优先搜索的第二个函数
    
    void main()
    {
        test();//测试函数
    }
    int  create_matrixgraph(MatricGraph*G)//创建邻接矩阵
    {
        int i;
        int j;
        VertexType  vex1;
        VertexType  vex2;//临时变量
        int x,y;//临时变量
        printf("请输入图的顶点数：");
        scanf("%d",&G->n);
        printf("清输入图的边数：");
        scanf("%d",&G->e);
        //初始化邻接矩阵
          for(i=0;i<VERTEXNUM;i++)
        for(j=0;j<VERTEXNUM;j++)
        {
            G->arcs[i][j]=0;
        }
        printf("请依次输入节点信息:\n");
        for(i=0;i<G->n;i++)
        {
            printf("请输入顶点%d：",i+1);
            G->vexs[i]=(VertexType)malloc(sizeof(char)*10);//动态申请存储空间
            scanf("%s",G->vexs[i]);
    
        }
        //输出图中边的信息
        for(i=0;i<G->e;i++)
        {
            vex1=(VertexType)malloc(sizeof(char)*10);
            vex2=(VertexType)malloc(sizeof(char)*10);
               printf("顶点：");
              scanf("%s",vex1);
              printf("邻接点：");
              scanf("%s",vex2);
              x=Locate_vex(G,vex1);
              y=Locate_vex(G,vex2);
              if(x==-1||y==-1)
                  return ERROR;
              else
              {
                  G->arcs[x][y]=1;
                  G->arcs[y][x]=G->arcs[x][y];
                  free(vex1);//释放内存
                  free(vex2);
                }
        }
                return OK;
    }
    int Locate_vex(MatricGraph*G ,VertexType vex)
    {
        int index=0;
        while(index<G->n)
        {
            if(strcmp(vex,G->vexs[index])==0)
                  break;
               else
                index++;
        }
          return (index==G->n ? -1 : index );//三段式 表判断
    }
    void test()//测试函数
    {
        int i;
        int j;
        MatricGraph*G;
        G=(MatricGraph*)malloc(sizeof(MatricGraph));
        int result;
        result=create_matrixgraph(G);
        if(result ==ERROR)
        {
            printf("创建邻接矩阵失败:\n");
    
        }
        printf("打印邻接矩阵:\n");
          printf("\t");
          for(i=0;i<G->n;i++)
              printf("\t%s",G->vexs[i]);//打印第一行的字符
             printf("\n");
             for(i=0;i<G->n;i++)
             {
                 printf("\t%s",G->vexs[i]);
                 for(j=0;j<G->n;j++)
                 {
                     printf("\t%d",G->arcs[i][j]);
                 }
                 printf("\n");
             }
             printf("邻接矩阵深度优先搜索的结果为:\n");
             //BFSTraversAL(G);
             DFSTraverse_matrixgraph(G);
    
    }
    Seq_Queue*init_queue()
    {
        Seq_Queue*Q;
           Q=(Seq_Queue*)malloc(sizeof(Seq_Queue));
           Q->front=0;
           Q->rear=0;//初始化
           return Q;
    }
    int pop_queue(Seq_Queue*Q,int *x)
    {
        if(empty_queue(Q)==1)
            return 0;
          else
          {
              *x=Q->data[Q->front];
              Q->front=(Q->front+1)%MAXSIZE;
              return 1;
          }
    
    
    
    }
    int push_queue(Seq_Queue*Q,int x)//入队
    {
        Q->data[Q->rear]=x;
        Q->rear=(Q->rear+1)%MAXSIZE;
    }
    int empty_queue(Seq_Queue*Q)
    {
        if(Q->rear==Q->front)
            return 1;
        else
            return 0;
    }
    /*void BFSTraversAL(MatricGraph*G)//广度优先搜索的第一个函数
    {
        int i;
        for(i=0;i<VERTEXNUM;i++)//初始化状态数组
            visited[i]=0;//初始化
           for(i=0;i<G->n;i++)
           {
               if(visited[i]==0)
                  BFSM(G,i);//依次访问每一个顶点
           }
    }*/
    /*void BFSM(MatricGraph*G,int i)//进行入队和遍历操作  类似于层序遍历
    {
        int j;
        int k;
         Seq_Queue*Q;
         Q=init_queue();
         printf("%s->",G->vexs[i]);
         visited[i]=OK;
         push_queue(Q,i);//入队操作
          while(empty_queue(Q)!=1)
          {
                    pop_queue(Q,&k);
              for(j=0;j<G->n;j++)//遍历每一行的权值为一的顶点  并将其打印出来
              {
                  if(G->arcs[k][j]==1&&visited[j]==0)
                  {
                        printf("%s->",G->vexs[j]);
                        visited[j]=OK;
                        push_queue(Q,j);//将每一次遍历过的顶点入队  类似于层序遍历
                  }
              }
    
          }
    
    }*/
    void DFSTraverse_matrixgraph(MatricGraph*G)//邻接矩阵的深度优先搜索
    {
        int i;
        //初始化数组
        for(i=0;i<VERTEXNUM;i++)
            visited[i]=ERROR;
          for(i=0;i<G->n;i++)
          if(visited[i]==ERROR)
          {
              DFSM(G,i);//进行深度优先搜索
    
          }
    }
    void DFSM(MatricGraph*G,int i)//邻接矩阵的第二个函数  有递归的含义在其中
    {
        int k;
        int j;
        k=i;
        printf("%s->",G->vexs[k]);
         visited[k]=OK;
         for(j=0;j<G->n;j++)
         { 
             if(G->arcs[k][j]==1&&visited[j]==ERROR)
             {
                 DFSM(G,j);//继续遍历其邻接的节点  达到深度优先搜索的目的
             }
    
         }
    }