图的深度优先搜索遍历算法分析及其应用.doc

图的深度优先搜索遍历算法分析及其应用摘 要:文章介绍了图论，图的基本概念及其图的表示方法。详细的分析了图中以邻接表为存储结构进行的图的深度优先搜索遍历的算法，并且在VC+环境中实现其算法的过程，对运行记过做了一定量的分析，最后介绍了基于该算法的一些应用。关键词：图；深度优先搜索；遍历；算法图论Graph Theory是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图（Graph）是一种较线性表和树更复杂的数据结构，图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，在研究有关图的问题时，要考虑图中每个顶点的信息，访问图中的各个顶点，而访问图中各个顶点的操作过程即使图的遍历，图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。1 图的三元组定义 图是一个三元组由集合V，E和关联函数组成，记为：G=（V，E，W（G）。其中V是顶点的集合，表示V（G）=V1，V2，V3，Vn，V（）。是V中的点偶对的有穷集，表示为E（G）=e1，e2，e3em，其中ei为或Vj，Vt，若ei为Vj，Vt，称ei为以V j 和Vt为端点的无向边；若ei为，称ei为以V j为起点，Vt为终点的有向边；W（G）称为EVxV的关联函数。2图的存储结构 图的存储结构除了要存储图中各个顶点的本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息），因此，图的结构比较复杂，很难以数据元素在存储区中的物理位置来表示元素之间的关系，但也正是由于其任意的特性，故物理表示方法很多。常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。V2V1V5V4V3 图1 无向图G该图的G的邻接表表示如下:为了便于理解，本文以无向图G作为具体示例（如图1所示），给出以邻接表进行存储的图的数据结构。现将图G的各顶点进行编号，其对应的邻接表如图2所示：V1V2 V3V4V531 420 431 2 012 图2图G的邻接表表示2.1邻接表的数据结构定义，将图G采用邻接表存储。其结构有：#include iostream.hint *visited; /存放当前结点是否遍历typedef int *MGraph;/定义一个二维数组存放邻接矩阵，暂不定义矩阵大小，数据元素类型为整型/把矩阵看作数组元素是一维数组的一个一维数组struct ArcNode /定义邻接表中的边结点类型 int adjvex; /邻接点位置 int weight; /权值 ArcNode *nextarc; /指向下一个边结点的链域;struct VNode int data; ArcNode *nextarc;/邻接表表头结点typedef VNode *adjlist;/邻接矩阵存储方式void InitGraph(MGraph &G,int n) /建立n行n列的二维数组 G=new int *n;/分配第一维空间 int i,j; for(i=0;in;i+) Gi=new intn;/分配第二维空间 for(i=0;in;i+) for(j=0;jn;j+) Gij=0;/初始情况下没有连接 2.2构造算法：void CreateGraph(MGraph &G,int n)/建立无向图，其它形式的图可以自己建立 int i,j,e; coute; coutn输入每条边的起点和终点序号(注：结点编号范围为0n-1):n; for(int k=1;k=e;k+) coutn第kij; if(in|jn|i0|j0) return; Gij=Gji=1;/初始化void InitAdj(adjlist &G,int n) G=new VNoden; for(int i=0;in;i+) Gi.data=i;Gi.nextarc=NULL;/建立邻接表存储方式的图void CreateAdj(adjlist &G,int n) int i,j,k,e; coute; coutn输入每条边的起点和终点序号(注：结点编号范围为0n-1):n; for(k=1;k=e;k+) coutn第kij; if(in|jn|i0|jadjvex=j;p-weight=1; p-nextarc=Gi.nextarc; Gi.nextarc=p; /向序号为j的链表中插入一个边结点 p=new ArcNode; p-adjvex=i;p-weight=1; p-nextarc=Gj.nextarc; Gj.nextarc=p; 3图的DFS遍历 图的遍历是从图中的某个顶点出发，沿着某条搜索路径对图中其他顶点访问且被访问一次。通常有两条遍历图的路径：深度优先搜索（Depth First Search）和广度优先搜索（Breadth First Search）。它们对无向图和有向图均适用。3.1 DFS遍历的基本思想 从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点与所有邻接顶点都已被访问，则退回到已被访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。3.2 DFS遍历的具体步骤 设开始搜索的定点标号为1，用E(T)表示所求图G的生成树T的边集，以K为其序号；V为正在检查的顶点，W为待检查的顶点，N（I）为第I个顶点的标号。（1） V：=1，K：=1，N（1）：=1。（2） 寻找没有检验边的关联边。 取与V关联的第一条没有检验的边，设为V,W，经过此边到达顶点W，规定边V,W的方向从V到W，转（3）。 如果没有这样的边，即与顶点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遍历的算法设计结合示例，我们有具体的算法如下：void dfsMGraph(MGraph G,int n,int i)/从第i个顶点开始遍历 couti; visitedi=1; for(int j=0;jn;j+) if(Gij!=0&!visitedj) dfsMGraph(G,n,j);/深度遍历邻接表void dfsAdj(adjlist G,int n,int i) couti; visitedi=true; ArcNode *p=Gi.nextarc; while(p!=NULL) int j=p-adjvex; if(!visitedj) dfsAdj(G,n,j); p=p-nextarc; /根据邻接矩阵得到图的邻接表void graphChange(MGraph gm,adjlist ga,int n) int i,j; for(i=0;in;i+) for(j=0;jadjvex=j; p-weight=gmij; p-nextarc=gai.nextarc; gai.nextarc=p; 4 主程序 在给出了数据结构类型和具体操作的算法之后，可以编辑出以下主程序：/主函数void main() int i,n,v;MGraph gm; coutn; visited=new intn; InitGraph(gm,n); CreateGraph(gm,n); adjlist ga; InitAdj(ga,n); graphChange(gm,ga,n); /按图的邻接表得到的深度优先遍历 coutv; cout按图的邻接表得到的深度优先遍历:endl; for(i=0;in;i+) visitedi=0; cout; dfsAdj(ga,n,v); cout结束n; 5.运行结果该程序已经在Visual C+环境中调试通过，运行时输入的具体数据和相应结果如图3所示：图3 程序运行结果6 DFS遍历序列结果讨论（1）只给定一个无向图，则dfs遍历序列不一定唯一。从图的某顶点VI出发进行搜索时，若VI的邻接点有多个尚未访问，可任选一个访问。（2）只有确定了图的邻接表的内容及起始顶点，dfs遍历序列才能唯一。因为邻接点域的内容与建表时的输入次序相关。 7 基于DFS算法阿德应用（1）求无向图中连通分量的个数。 求解