图的深度优先遍历代码递归

谁践踏了优雅 2022-05-22 06:40 184阅读 0赞

实现图的深度优先遍历,如下图:  
![这里写图片描述][70]

#include <iostream>
    #include <stdio.h>//注意
    #include <stdlib.h>//注意
    using namespace std;
    #define MAX_VERTEX_NUM 20
    #define MAX_VEX 20
    typedef char VertexType,VexType;
    typedef int EdgeType,InfoType;
    int  Visited[MAX_VEX] ;
    
    typedef struct ArcNode{ //边（弧）结点的类型定义
        int  adjvex;   //边（弧）的另一顶点的在数组中的位置
        ArcNode *nextarc;//指向下一边（弧）结点的指针
        InfoType *info;      //该弧相关信息的指针
    }ArcNode;
    typedef struct Vnode{
       //顶点结点及其数组的类型定义
        VertexType data;    //顶点信息
        ArcNode * firstarc;    //指向关联该顶点的边（弧）链表
    } Vnode, AdjList[MAX_VERTEX_NUM];
    typedef struct {
        AdjList  vertices;
        int  vexnum, arcnum;    //图的当前顶点数和弧数
        int  kind;    //图的种类标志
    } ALGraph;    //图邻接表类型
    
    int  LocateVex(ALGraph  &G , VexType vp)
    {
        int  k=0 ;
        for (k=0 ; k<G.vexnum ; k++)
        {
       if (G. vertices[k].data==vp)  return(k) ;}
        return(-1) ;     /* 图中无此顶点 */
    }
    void CreatALGraph(ALGraph &G)//有向带权图的创建
    {
        char e1,e2=0;
        int k,l=0,m=0;
        ArcNode *s;
        cin>>G.vexnum>>G.arcnum; //输入顶点数和边数
        for( int i=0;i<G.vexnum;i++)
        {   cin>>G.vertices[i].data;//输入顶点信息
            G.vertices[i].firstarc=NULL;
        }
        for(k=0;k<G.arcnum;k++)
        {   cin>>e1>>e2;
            s=(ArcNode*)malloc(sizeof(ArcNode));
            l=LocateVex(G, e1);
            m=LocateVex(G , e2);
            s->adjvex=m;
            s->nextarc=G.vertices[l].firstarc;
            G.vertices[l].firstarc=s;
        }
    }
    void OutputALGraph(ALGraph &G)//邻接表的输出
    {   int i;
        for(i=0;i<G.vexnum;i++)
        {   ArcNode * s;
            printf("%d:%c",i,G.vertices[i].data);  //顶点信息
            s=G.vertices[i].firstarc;
            while(s!=NULL)
            {  printf(" %d",s->adjvex);
                s=s->nextarc;   }
            printf("\n");
        }
    }
    void  DFS(ALGraph &G , int v)
    {   ArcNode  *p ;
        if(Visited[v]==0)
        { printf("%c ",G.vertices[v].data);      /* 置访问标志，访问顶点v */  }
        Visited[v]=1;
        p=G.vertices[v].firstarc;   /* 链表的第一个结点 */
        while (p!=NULL)
        {  if  (!Visited[p->adjvex])
          {DFS(G, p->adjvex) ;}
            /* 从v的未访问过的邻接顶点出发深度优先搜索 */
            p=p->nextarc ;
        }
    }
    
    void DFS_traverse_Grapg(ALGraph &G,int t)
    {
        for (int v=0 ; v<G.vexnum ; v++)
        { Visited[v]=0 ;}    /* 访问标志初始化 */
        DFS(G, t);
        for (int v=0 ; v<G.vexnum ; v++)
        {   if (Visited[v]==0)
          { DFS(G ,v);}
        }
    }
    
    int main()
    {
        ALGraph G;
        char m;
        int t=0;
        CreatALGraph(G);
        OutputALGraph(G);
        cin>>m;
        t=LocateVex(G,m);
        DFS_traverse_Grapg(G,t);
        return 0;
    }

结果:  
![这里写图片描述][70 1]

[70]: /images/20220522/f1671addf795411bb86a31ce08262dca.png
[70 1]: /images/20220522/0a34b0afe95b40e2a5ceebbb4067fcd7.png