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

解题思路: (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]);

}

点击http://www.dotcpp.com/blog/8200.html获取原文链接。

原文发布于微信公众号 - 编程范(dotcpp)

原文发表时间:2018-06-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

有向图----有向图的实现

11100
来自专栏码匠的流水账

聊聊hystrix的BucketedCounterStream

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/metric/consumer/BucketedCou...

9110
来自专栏软件开发 -- 分享 互助 成长

欧拉回路

一、定义 欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次, 称这条回路为欧拉回路。具有欧拉...

21890
来自专栏张善友的专栏

如何去理解 拓扑排序算法

查看Castle的代码,在Castle.Core中内部的数据结构采用图,排序使用的拓扑排序算法:        对于一条有向边(u,v),定义u < v;满足所...

249100
来自专栏张俊红

数据结构-图

图是不同于前面两种数据结构的另一种新的数据结构,线性表中元素与元素之间是被串起来的,每个数据元素只有一个直接前驱和一个直接后继,是一种一对一的数据结构;在树的结...

39810
来自专栏个人分享

XML封装与验证消息

22340
来自专栏用户画像

5.2.4 邻接多重表

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

11710
来自专栏java系列博客

HibernateCallback 的用法

11920
来自专栏码匠的流水账

聊聊storm TridentTopology的构建

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/TridentTopology.java

19430
来自专栏deed博客

数学速算法

16820

扫码关注云+社区

领取腾讯云代金券