无向图的邻接表深度优先算法

小鱼儿 2022-06-15 11:20 210阅读 0赞

/*无向图的邻接表深度优先算法*/
    #include<stdio.h>
    #define vnum 10
    int visited[vnum]={
       0};
    typedef struct arcnode
    {
        int adjvex;                         /*下一条边的顶点编号*/
        struct arcnode * nextarc;           /*指向下一条边的指针*/
    }ArcNode;
    typedef struct vexnode
    {
        int vertex;                         /*顶点编号*/
        ArcNode *firstarc;                  /*指向第一条边的指针*/
    }AdjList[vnum];
    typedef struct gp
    {
        AdjList adjlist;
        int vexnum,arcnum;                  /*顶点和边的个数*/
    }Graph;
    CreateAdjlist(Graph *g,int x,int y)     /*创建并初始化邻接表*/
    {
        int i;
        g->vexnum=x;
        g->arcnum=y;
        for(i=0;i<g->vexnum;i++)
        {
            g->adjlist[i].vertex=i;         /*初始化顶点信息*/
            g->adjlist[i].firstarc=NULL;    /*初始化i的第一个邻接点为NULL*/
        }
    }
    InsertEdge(Graph *g)                    /*插入边*/
    {
        ArcNode *p;
        int i,j,k;
        for(k=0;k<g->arcnum;k++)
        {
            printf("第%d条边:",k+1);
            scanf("%d %d",&i,&j);
            p=(ArcNode *)malloc(sizeof(ArcNode));/*生成j的表结点*/
            p->adjvex=j;
            p->nextarc=g->adjlist[i].firstarc;   /*将结点j链接到i的单链表中*/
            g->adjlist[i].firstarc=p;
            p=(ArcNode *)malloc(sizeof(ArcNode));/*生成i的表结点*/
            p->adjvex=i;
            p->nextarc=g->adjlist[j].firstarc;   /*将结点i链接到j的单链表中*/
            g->adjlist[j].firstarc=p;
        }
    }
    void DFS(Graph *g,int i)                /*深度优先搜索*/
    {
        ArcNode *p;
        printf("%d ",i);                    /*访问顶点*/
        visited[i]=1;                       /*置已访问标志*/
        p=g->adjlist[i].firstarc;
        while(p!=NULL)
        {
            if(!visited[p->adjvex])DFS(g,p->adjvex);
            p=p->nextarc;
        }
    }
    main()
    {
        Graph g;
        int x,y;
        printf("采用邻接表创建无向图\n");
        printf("请输入图的顶点数和边数(逗号分隔):\n");
        scanf("%d,%d",&x,&y);
        CreateAdjlist(&g,x,y);
        InsertEdge(&g);
        printf("图的深度优先遍历:");
        DFS(&g,0);
    }

编译效果  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220615/5e319310abbe40228a66b855b0f8f4b6.png