搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 编程范 > 优秀题解【图的遍历——深度优先搜索】

优秀题解【图的遍历——深度优先搜索】

编程范 2018-06-26

点击蓝字

优秀题解【图的遍历——深度优先搜索】

解题思路:
(1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

如visit[i]=1表示编号为i的顶点已经访问过。然后选取与该顶点邻接的一个未被访问过 的顶点访问,并把该顶点设置为已访问,当某个顶点的所有邻接顶点都已访问,则依次返回到最近访问过的节点,再选取与该顶点邻接的一个未被访问过 的顶点访问。当图中所有顶点都已经访问过时,遍历结束。


(2)以上过程为思想描述过程,但在实际代码描述中,许些地方不同

①:假设图的存储结构为邻接表,从顶点v开始访问,其代码遍历过程为

②:访问该顶点v,把该顶点置为已访问visit[v]=1

③:让p指向v的第一个边表节点

④:当p不等于NULL时,循环以下过程

1):如果该边表节点未被访问过,以该节点为顶点继续深度优先遍历

2):1)结束后 p=p->nextarc p等于p的下一个边表节点


以下为邻接表图结构定义模板,以及其在邻接表结构下的DFS

typedef struct ArcNode_{

     

    int adjvex;/*边表节点编号,其实也就是顶点编号*/

    struct ArcNode_ * nextarc;/*指向下一个边表节点*/

}*arcnode,ArcNode;

 

typedef struct VNode_{

    char data;/*顶点数据*/

    ArcNode * firstarc;/*指向他的第一个边表节点*/

 

}*vnode,VNode;

 

typedef struct Agraph_{

   

  VNode adjlist[maxsize];/*邻接表*/ /*maxsize为图顶点数*/

  int n,e;/*图的定点数和边数*/

 

}*agraph,Agraph;

   


int visit[maxsize]={0};

void DFS(Agraph* G,int v)

{

    ArcNode * p;

    visit(v);/*访问v*/

    visit[v]=1;/*编号为v的顶点设置为已经访问*/

 

     p=G->adjlist[v].firstarc;

      while(p!=NULL)

      {

          if(visit[p->adjvex]==0)/*若顶点v的第一个边表节点未被访问过/这里第一个指刚进循环时*/

            DFS(G,p->adjvex);

          p=p->nextarc;/*下一个边表节点*/

      }

}

   

注意事项:

题目输入为邻接矩阵,因为输入的一定是无向图所以偷个懒把它直接当做邻接表,故可以第0列为顶点表,后面1到n-1列分别为边表节点。

一定要在熟练理解背诵上面所有代码的基础上,书写代码

不用先把它转化为邻接表存储,再用以上代码

参考代码:


#include<stdio.h>

#include<malloc.h>

 

void DFS_(int **edges,int visit[],int n,int v);

void input(int **edges,int n);

int main()

{

    int n;/*定点个数*/

    int **edges;/*邻接矩阵*/

    while(scanf("%d",&n)!=EOF)

    {   /*为邻接矩阵开辟空间*/

        edges=(int **)malloc(n*sizeof(int *));

         for(int i=0;i<n;i++)

            edges[i]=(int *)malloc(n*sizeof(int));

          int visit[n];

          for(int i=0;i<n;i++)

            visit[i]=0;/*访问数组起始为0*/

          input(edges,n);/*输入邻接矩阵*/

          DFS_(edges,visit,n,0);

 

    }

    return 0;

}

/*==========================================================*/

void DFS_(int **edges,int visit[],int n,int v)

{

    printf("%d ",v);/*输出访问顶点*/

    visit[v]=1;/*顶点v设置为已访问*/

      for(int i=1;i<n;i++)/*相当于while(p!=NULL)*/

      {

          if(edges[v][i]!=0&&visit[i]==0)/*如果顶点i是v的邻接顶点,且没有被访问,则进行以i为顶点的深度优先遍历*/

          {

              DFS_(edges,visit,n,i);

          }

      }

}

/*==========================================================*/

void input(int **edges,int n)

{

    for(int i=0;i<n;i++)

        for(int j=0;j<n;j++)

        scanf("%d",&edges[i][j]);

}

   



点击“阅读原文”获取原文链接。

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《优秀题解【图的遍历——深度优先搜索】》的版权归原作者「编程范」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注编程范微信公众号

编程范微信公众号:dotcpp

编程范

手机扫描上方二维码即可关注编程范微信公众号

编程范最新文章

精品公众号随机推荐