C语言数据结构邻接表的广度优先搜索-BFS

￡神魔★判官ぃ 2022-01-22 04:37 221阅读 0赞

//无向图的邻接表的广度优先搜索——BFS

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define VERTEXNUM 100//最大顶点数
    #define ERROR 0
    #define  OK 1
    typedef char *VertexType;//顶点数据的结构体
    int visited[VERTEXNUM];//创建状态数组
    typedef struct edgenode
    {
        int  adjlist;//下标
        struct edgenode *next;//指向下一个邻接点的指针
    }EdgeNode;//邻接边的结构体
    typedef struct vnode
    {
        VertexType vertex;//顶点的数据
        EdgeNode *firstedge;//指向其顶点的第一个邻接点的指针
    
    }VNode;//顶点的结构体
    typedef struct algraph
    {
        VNode  adjlist[VERTEXNUM];//顶点数组
        int n,e;//图的边数和顶点数
    
    }ALGraph;//邻接表的结构体
    int  create_algraph(ALGraph*G);
    int locate_vex(ALGraph*G,VertexType vex);//定位函数
    void test();//测试函数
    void BFS_traversealgraph(ALGraph*G);//邻接表的广度优先搜索
    void BFSAL(ALGraph*G,int i);//广度优先搜索的第二个函数
    
    void main()
    {
        test();//测试函数
    
    }
    int  create_algraph(ALGraph*G)
    {
        int i;
        VertexType vex1;
        VertexType vex2;
        int x,y;//临时数组下标变量
        int  create_algraph(ALGraph*G);
        printf("请输入图的边数：");
        scanf("%d",&G->e);
        printf("请输入图的顶点数；");
         scanf("%d",&G->n);
         //输入顶点的信息
         for(i=0;i<G->n;i++)
         {
             printf("顶点：",i+1);
             G->adjlist[i].vertex=(VertexType)malloc(sizeof(char)*10);//创造动态存储空间
             scanf("%s",G->adjlist[i].vertex);
             G->adjlist[i].firstedge=NULL;//初始化 置空
    
    
         }//创建边的信息
         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
              {
                 EdgeNode *enode;
                 enode=(EdgeNode*)malloc(sizeof(EdgeNode));
                 enode->adjlist=y;
                 enode->next=G->adjlist[x].firstedge;
                 G->adjlist[x].firstedge=enode;
                    enode=(EdgeNode*)malloc(sizeof(EdgeNode));
                 enode->adjlist=x;
                 enode->next=G->adjlist[y].firstedge;
                 G->adjlist[y].firstedge=enode;
               }
    
         }
    
          return OK;
    }
    int locate_vex(ALGraph*G,VertexType vex)
    {
        int index=0;
          while (index<G->n)
          {
              if(strcmp(vex,G->adjlist[index].vertex)==0)
              {
                  break;
              }
              else
                index++;
          }
          return (index==G->n ? -1 : index);
    }
    void test()
    {
        ALGraph*G;
        int i;
          int  result;
          EdgeNode*enode;
        G=(ALGraph*)malloc(sizeof(ALGraph));
          if(G!=NULL)
            result =create_algraph(G);
          if(result ==ERROR)
          {
              printf("创建邻接表失败:\n");
                return ;
          }
           printf("邻接边的打印结果为:\n");
             for(i=0;i<G->n;i++)
             {
                 printf("%s",G->adjlist[i].vertex);
                  enode=G->adjlist[i].firstedge;
                   while(enode)
                   {
                       printf("->%d",enode->adjlist);
                         enode=enode->next;
                   }
                   printf("\n");
    
             }
             printf("邻接表的广度优先搜索的结果为:\n");
               BFS_traversealgraph(G);
    
    }
    void BFS_traversealgraph(ALGraph*G)
    {
        int i;
        for(i=0;i<VERTEXNUM;i++)
            visited[i]=ERROR;
        for(i=0;i<G->n;i++)
        {
           BFSAL(G,i);//让其遍历每一个顶点
    
        }
    }
    void BFSAL(ALGraph*G,int i)
    {
        EdgeNode*enode;
           if(visited[i]==ERROR)//避免顶点的重复打印
        printf("%s->",G->adjlist[i].vertex);
               visited[i]=OK;
              enode=G->adjlist[i].firstedge;
                while(enode!=NULL)
                {
                    if(visited[enode->adjlist]==ERROR)
                    {
                        printf("%s->",G->adjlist[enode->adjlist].vertex);
                          visited[enode->adjlist]=OK;//打印后的顶点状态改变
    
    
                    }
                    enode=enode->next;
    
                }
          }