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

川长思鸟来 2022-01-22 11:15 232阅读 0赞

/\*  
\*创建邻接表的链式存储结构  
\*初始化顶点信息  
\*初始化边的信息  
\*创建以每一个顶点为起点的单向链表  
\*以顶点数输出链表中的数据  
\*邻接表的深度优先搜索-DFS  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define VERTEXNUM 100
    #define ERROR 0
    #define OK  1
    #define FALSE 0
    #define TRUE 1
    int visitied[VERTEXNUM];//创建表明是否已经搜索过的数组
    typedef char * VertexType;//字符串的字符串定义
    typedef struct edgenode
    {
        int adjvex;//邻接点的下标
         struct edgenode*next;//指向下一个邻接点的指针域
    }EdgeNode;//边的结构体
    typedef struct vnode
    {
        EdgeNode*firstedge;
        //指向第一个邻接点的指针 类型为邻接边的结构体类型相同
        VertexType *vertex;
        //顶点的信息
    
    }Vnode;//顶点结构体
    typedef struct algraph
    {
        Vnode adjlist[VERTEXNUM];//顶点数组
        int n,e;//图的边数和点数
    }ALGraph;//图的邻接表的结构体
    int create_algraph(ALGraph *G);//邻接表的创建
    void test_algraph();//测试函数
    int locate(ALGraph*G,VertexType *vex);//顶点的名称在数组的下标
    void DFSTraverseAL(ALGraph*G);//深度优先搜索
    void DFSAL(ALGraph*G,int i);//深度遍历
    
    void main()
    {
       test();//测试函数
    
    }
    int create_algraph(ALGraph *G)//邻接表的创建
    {
        int i,j;
        int x1,x2;//临时下标变量
        EdgeNode*enode;//创建边的结构体指针
    
        VertexType vex1,vex2;
        printf("请输入图的边数:\n");
          scanf("%d",&G->e);
          printf("请输入图的点数:\n");
           scanf("%d",&G->n);
           //初始化图的顶点信息
           for(i=0;i<G->n;i++)
           {
               G->adjlist[i].vertex=(VertexType)malloc(sizeof(char)*10);
               printf("顶点%d：",i+1);
               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);
                  x1= locate(G,vex1);
                  x2= locate(G,vex2);
                  if(x1==-1||x2==-1)
                  {
                      free(vex1);
                      free(vex2);
                      return ERROR;
                  }
    
    
                      else
                      {
                          enode=(EdgeNode*)malloc(sizeof(EdgeNode));
                          enode->adjvex=x2;
                          enode->next=G->adjlist[x1].firstedge;
                            G->adjlist[x1].firstedge=enode;
                            enode=(EdgeNode*)malloc(sizeof(EdgeNode));
                          enode->adjvex=x1;
                          enode->next=G->adjlist[x2].firstedge;
                            G->adjlist[x2].firstedge=enode;
                    }
            }
            return OK;
    }
    int locate(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;
        Vnode vnode;
        EdgeNode* enode;
        G=(ALGraph*)malloc(sizeof(ALGraph));
         result=create_algraph(G);
         if(result!=0)
         {
             for(i=0;i<G->n;i++)
             {
                 vnode=G->adjlist[i];
                 printf("顶点：");
                  printf("%s",vnode.vertex);
                  enode=vnode.firstedge;
                  while(enode)
                  {
                      printf("->%d",enode->adjvex);
                      enode=enode->next;
                  }
                  printf("\n");
             }
         }
         printf("\n");
         printf("深度优先搜索的结果为：\n");
         DFSTraverseAL(G);
    
    }
    void DFSAL(ALGraph*G,int i)
    {
        EdgeNode*p;
        printf("%s->",G->adjlist[i].vertex);
        visitied[i]=TRUE;
        p=G->adjlist[i].firstedge;
        //核心关键点所在 每次遍历都是以一个新的顶点 继续去遍历其所邻接的边的点
        while(p)
        {
            if(visitied[p->adjvex]==FALSE)//刚得到的下标未曾遍历过 继续遍历
            {
                DFSAL(G,p->adjvex);
    
            }
            else
               p=p->next;
        }
    }
    void DFSTraverseAL(ALGraph*G)//深度优先搜索
    {
        int i;
        for(i=0;i<VERTEXNUM;i++)
        {
            visitied[i]=FALSE;
    
        }
        for(i=0;i<G->n;i++)
        {
            if(visitied[i]==0)
            {
                DFSAL(G,i);
            }
        }
    }