图的深度优先搜索遍历算法分析及其应用.docx
《图的深度优先搜索遍历算法分析及其应用.docx》由会员分享，可在线阅读，更多相关《图的深度优先搜索遍历算法分析及其应用.docx（13页珍藏版）》请在冰点文库上搜索。
图的深度优先搜索遍历算法分析及其应用
图的深度优先搜索遍历算法分析及其应用
重庆邮电大学
数学大类专业
2008级《数学建模与数学实验》课程设计
设计题目：
图的深度优先搜索遍历算法分析及其应用
设计时间：
2010.9.7-----2010.9.12
设计成绩：
姓名：
班级：
学号：
指导教师：
图的深度优先搜索遍历算法分析及其应用
摘要:
文章介绍了图论，图的基本概念及其图的表示方法。
详细的分析了图中以邻接表为存储结构进行的图的深度优先搜索遍历的算法，并且在VC++环境中实现其算法的过程，对运行记过做了一定量的分析，最后介绍了基于该算法的一些应用。
关键词：
图；深度优先搜索；遍历；算法
图论〔GraphTheory〕是数学的一个分支。
它以图为研究对象。
图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图（Graph）是一种较线性表和树更复杂的数据结构，图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
因此，在研究有关图的问题时，要考虑图中每个顶点的信息，访问图中的各个顶点，而访问图中各个顶点的操作过程即使图的遍历，图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。
1图的三元组定义
图Ｇ是一个三元组由集合V，E和关联函数组成，记为：
G=（V，E，W（G））。
其中V是顶点的集合，表示V（G）={V1，V2，V3，……Vn}，V（Ｇ）≠ＮＵＬＬ。
Ｅ是V中的点偶对的有穷集，表示为E（G）={e1，e2，e3……em}，其中ei为或{Vj，Vt}，若ei为{Vj，Vt}，称ei为以Vj和Vt为端点的无向边；若ei为，称ei为以Vj为起点，Vt为终点的有向边；W（G）称为E→VxV的关联函数。
2图的存储结构
图的存储结构除了要存储图中各个顶点的本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息），因此，图的结构比较复杂，很难以数据元素在存储区中的物理位置来表示元素之间的关系，但也正是由于其任意的特性，故物理表示方法很多。
常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。
邻接表是图的一种链式存储结构。
对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。
图1无向图G
该图的G的邻接表表示如下:
为了便于理解，本文以无向图G作为具体示例（如图1所示），给出以邻接表进行存储的图的数据结构。
现将图G的各顶点进行编号，其对应的邻接表如图2所示：
V1
V2
V3
V4
V5
3
1
∧
4
2
0
∧
4
3
1
∧
2
0
∧
1
∧
2
图2图G的邻接表表示
2.1邻接表的数据结构定义，将图G采用邻接表存储。
其结构有：
#include"iostream.h"
int*visited;//存放当前结点是否遍历
typedefint**MGraph;//定义一个二维数组存放邻接矩阵，暂不定义矩阵大小，数据元素类型为整型
//把矩阵看作数组元素是一维数组的一个一维数组
structArcNode{//定义邻接表中的边结点类型
intadjvex;//邻接点位置
intweight;//权值
ArcNode*nextarc;//指向下一个边结点的链域
};
structVNode{
intdata;
ArcNode*nextarc;
};//邻接表表头结点
typedefVNode*adjlist;
//邻接矩阵存储方式
voidInitGraph（MGraph&G,intn）//建立n行n列的二维数组
{
G=newint*[n];//分配第一维空间
inti,j;
for（i=0;iG[i]=newint[n];//分配第二维空间
for（i=0;ifor（j=0;jG[i][j]=0;//初始情况下没有连接
}
2.2构造算法：
voidCreateGraph（MGraph&G,intn）{//建立无向图，其它形式的图可以自己建立
inti,j,e;
cout<<"输入无向图中边的总数量";
cin>>e;
cout<<"\n输入每条边的起点和终点序号（注：
结点编号范围为0~n-1）:
\n";
for（intk=1;k<=e;k++）{
cout<<"\n第"<";
cin>>i>>j;
if（i>n||j>n||i<0||j<0）return;
G[i][j]=G[j][i]=1;}
}
//初始化
voidInitAdj（adjlist&G,intn）
{
G=newVNode[n];
for（inti=0;i}
//建立邻接表存储方式的图
voidCreateAdj（adjlist&G,intn）
{
inti,j,k,e;
cout<<"输入图的总边数：
";
cin>>e;
cout<<"\n输入每条边的起点和终点序号（注：
结点编号范围为0~n-1）:
\n";
for（k=1;k<=e;k++）{
cout<<"\n第"<";
cin>>i>>j;
if（i>n||j>n||i<0||j<0）return;
//向序号为i的链表中插入一个边结点
ArcNode*p=newArcNode;
p->adjvex=j;p->weight=1;
p->nextarc=G[i].nextarc;
G[i].nextarc=p;
//向序号为j的链表中插入一个边结点
p=newArcNode;
p->adjvex=i;p->weight=1;
p->nextarc=G[j].nextarc;
G[j].nextarc=p;
}
}
3图的DFS遍历
图的遍历是从图中的某个顶点出发，沿着某条搜索路径对图中其他顶点访问且被访问一次。
通常有两条遍历图的路径：
深度优先搜索（DepthFirstSearch）和广度优先搜索（BreadthFirstSearch）。
它们对无向图和有向图均适用。
3.1DFS遍历的基本思想
从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。
如果当前被访问过的顶点与所有邻接顶点都已被访问，则退回到已被访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。
3.2DFS遍历的具体步骤
设开始搜索的定点标号为1，用E（T）表示所求图G的生成树T的边集，以K为其序号；V为正在检查的顶点，W为待检查的顶点，N（I）为第I个顶点的标号。
（1）V：
=1，K：
=1，N
（1）：
=1。
（2）寻找没有检验边的关联边。
1取与V关联的第一条没有检验的边，设为｛V,W｝，经过此边到达顶点W，规定边｛V,W｝的方向从V到W，转（3）。
2如果没有这样的边，即与顶点V关联的每一边都已检测过，转（4）。
（3）①若W是未被访问过的顶点，即N（W）尚未确定，则把边｛V,W｝送入边集E（T），令V：
=W,K：
=K+1,N（W）：
=K，转
（2）。
②若W是被访问过的顶点，即N（W）≠0，回到顶点V转
（2）。
（4）确定集合T中指向顶点V的边｛U,V｝。
①找到该边返回到顶点U，令V：
=U，转
（2）。
②没有边｛U,V｝则停止。
3.3遍历的算法设计
结合示例，我们有具体的算法如下：
voiddfsMGraph（MGraphG,intn,inti）//从第i个顶点开始遍历
{
cout<";
visited[i]=1;
for（intj=0;jif（G[i][j]!
=0&&!
visited[j]）
dfsMGraph（G,n,j）;
}
//深度遍历邻接表
voiddfsAdj（adjlistG,intn,inti）
{
cout<";
visited[i]=true;
ArcNode*p=G[i].nextarc;
while（p!
=NULL）
{
intj=p->adjvex;
if（!
visited[j]）
dfsAdj（G,n,j）;
p=p->nextarc;
}
}
//根据邻接矩阵得到图的邻接表
voidgraphChange（MGraphgm,adjlistga,intn）
{
inti,j;
for（i=0;ifor（j=0;jif（gm[i][j]!
=0）
{
ArcNode*p=newArcNode;
p->adjvex=j;
p->weight=gm[i][j];
p->nextarc=ga[i].nextarc;
ga[i].nextarc=p;
}
}
4主程序
在给出了数据结构类型和具体操作的算法之后，可以编辑出以下主程序：
//主函数
voidmain（）
{
inti,n,v;MGraphgm;
cout<<"输入图中顶点数量：
";
cin>>n;
visited=newint[n];
InitGraph（gm,n）;
CreateGraph（gm,n）;
adjlistga;
InitAdj（ga,n）;
graphChange（gm,ga,n）;
//按图的邻接表得到的深度优先遍历
cout<<"输入按图的邻接表遍历的起始顶点：
";
cin>>v;
cout<<"按图的邻接表得到的深度优先遍历:
"<for（i=0;ivisited[i]=0;
cout<<"开始==>";
dfsAdj（ga,n,v）;
cout<<"结束\n";
}
5.运行结果
该程序已经在VisualC++环境中调试通过，运行时输入的具体数据和相应结果如图3所示：
图3程序运行结果
6DFS遍历序列结果讨论
（1）只给定一个无向图，则dfs遍历序列不一定唯一。
从图的某顶点VI出发进行搜索时，若VI的邻接点有多个尚未访问，可任选一个访问。
（2）只有确定了图的邻接表的内容及起始顶点，dfs遍历序列才能唯一。
因为邻接点域的内容与建表时的输入次序相关。
7基于DFS算法阿德应用
（1）求无向图中连通分量的个数。
求解该问题只要在算法dfsAdj中加入一个计数器count，每调用一次dfs后，使count加1，最后count的值就是无向图中连通分量的个数。
（2）求解无向图中通过给定顶点VI的简单回路的算法。
8结论
综上所述，图的结构比较发杂，在遍历图的DFS算法和程序时，关键要掌握他的遍历思想，并且能使用一些编程技巧和经验对程序优化，在完全理解DFS算法的基础上，再解决图的有关应用问题就容易多了。
参考文献：
（1）严蔚敏，吴伟民。
数据结构。
清华大学出版社。
1997：
1602178.
（2）胡学钢。
数据结构算法设计指导，清华大学出版社。
1999：
1982216。
（3）RobertSedgewickAlgorithmsInC，ThirdEdition..人民邮电出版社，2003，22
（2）：
1-2
（4）朱战立，李文，数据结构，西安交通大学出版社，19971159-175.
（5）余祥宣，计算机算法基础（第二版）华中科技大学出版社，2000.27-29.
9总结
在这次课程设计中，我和搭档选择了关于图的深度优先搜索遍历的算法分析及其应用，刚开始的时候，根本就不懂何为深度优先搜索遍历，通过查找相关的资料和书本，在数据结构这本书上，我们看到了图的深度优先搜索相关内容并且通过学习基本的指导图的深度优先搜索遍历时什么一回事情，并且结合老师给的资料进一步的探索学习。
通过学习书本和请教相关的同学我们理解了图的深度优先搜索遍历的一般原理和基本实现方法。
把学过的计算机编译原理的知识强化，能够把相关算法通过自己设计的程序表示出来，加深了对理论知识的理解。
在设计的过程中遇到问题，可以说得是困难重重，不了解命题是首要的，其次对相关的编程知识掌握的不是很牢固，这样势必会花大量的时间在编程的摸索上，我主要的工作是对程序进行调试，发现问题，解决问题和对文章的最后编写。
首先按照老师的资料上的程序调试出现了很多的错误，通过解决，最终只剩下了一个问题，但我们查找很多书本资料都很难理解为什么要如此编写程序，要为什么会出现这样的错误。
实验调试了很多次，还是没能解决问题，我们就决定换一种编程思想对相关的算法进行编译，结果得到了我们想要的结果。
在设计的过程中我发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，一定把以前所学过的知识重新温故，另外，资料上也有部分知识不太清楚，于是我又不得不边学边用。
整个设计我基本上还满意，由于水平有限，难免会有错误，还望老师批评指正。
升级会员 