优秀题解【图的遍历——深度优先搜索】
解题思路: (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获取原文链接。