当前位置：文档库 › 图的深度优先遍历算法课程设计报告

图的深度优先遍历算法课程设计报告

合肥学院

计算机科学与技术系

课程设计报告

2013～2014学年第二学期

课程数据结构与算法

课程设计名称图的深度优先遍历算法的实现

学生姓名陈琳

学号1204091022

专业班级软件工程

指导教师何立新

2014 年9 月

一：问题分析和任务定义

涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。

深度优先遍历图的方法是，从图中某顶点v 出发：（1）访问顶点v ；

（2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问；

（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。二：数据结构的选择和概要设计设计流程如图：

图1 设计流程

利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。

图 2 原始图 1.从0开始，首先找到0的关联顶点3

2.由3出发，找到1；由1出发，没有关联的顶点。

3.回到3，从3出发，找到2；由2出发，没有关联的顶点。

4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。

所以最后顺序是0,3,1,2,4

三：详细设计和编码

1.创建邻接表和图

void CreateALGraph (ALGraph* G) //建立邻接表函数.

{

int i,j,k,s;

char y;

EdgeNode* p; //工作指针.

printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n");

scanf("%d,%d",&(G->n),&(G->e));

scanf("%c",&y); //用y来接收回车符.

for(s=0;sn;s++)

{

printf("请输入下标为%d的顶点的元素:\n",s);

scanf("%c",&(G->adjlist[s].vertex));

scanf("%c",&y); //用y来接收回车符.当后面要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。

G->adjlist[s].firstedge=NULL;

}

printf("请分别输入该图的%d条弧\n",G->e);

for(k=0;ke;k++)

{

printf("请输入第%d条弧的起点和终点（起点下标,终点下标）:\n",(k+1));

scanf("%d,%d",&i,&j);

p=(EdgeNode*)malloc(sizeof(EdgeNode));

p->adjvex=j;

p->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=p;

}

2.深度优先遍历

void DFS(ALGraph* G,int v) //深度优先遍历

{

EdgeNode* p;

int w;

printf("%c ",G->adjlist[v].vertex);

visited[v]=True;

for(p=G->adjlist[v].firstedge;p;p=p->next)

{

w=p->adjvex;

if(!visited[w])

DFS(G,w); //对于没有访问过的顶点，调用深度优先搜索函数 }

}

void DFStraverse(ALGraph* G)

{

int v;

for(v=0;vn;v++)

{

visited[v]=False;

}

for(v=0;vn;v++) //对v尚未访问到的邻接点w进行一个递归遍历.

{

if(!visited[v])

DFS(G,v);

}

四：上机调试过程

在创建图时，输入程序printf("第%d条弧的起点和终点（格式为"起点下标,终点下标"）:\n",(k+1));运行发现有十六个错误，错误截图为：

图3 调试错误图

经调试，将该段程序修改为：printf("请输入第%d 条弧的起点和终点（起点下标,终点下标）:\n",(k+1));即可成功。

五：测试结果及其分析 1.测试结果：

图4 测试结果图 2.分析

此程序的图如下：

图5 原始图

遍历从0开始，第一步到3

图6 第一次遍历

与3相连的有1和2，在此先遍历1

图7 第二次遍历

而与1相关的没有，则返回到3

，与3相连的有1和2，1遍历过，所以遍历2

图8 第三次遍历

2没有与之相关的顶点返回3,3的所有相关都遍历过，返回0，只剩下4

图9 第四次遍历

与4相关的1已遍历过，返回0,0的所有相关都已遍历，则深度优先遍历结束。

遍历顺序：0 3 1 2 4

六：用户使用说明

1.根据屏幕提示输入图的顶点数n与边数e(以逗号做分隔符)；

2.依次输入下标为0,1,2……（n-1）的顶点的元素；

3.依次输入第1,2……e条弧的起点和终点，格式为：起点下标，终点下标；

4.即可得出所输入图的深度优先遍历序列；

七：参考文献

1.王昆仑、李红.《数据结构与算法（第二版）》.北京：中国铁道出版社，2012

2.程杰.《大话数据结构[M]》.北京:清华大学出版社，2011

3.韩利凯、李军.《数据结构[M]》.浙江:浙江大学出版社，2013

4.谢若阳.《数据结构[M].北京》：清华大学出版社，2010

5.黄国瑜、叶乃菁.《数据结构[M]》.北京：清华大学出版社，2009

八：附录

//以邻接表为存储结构的深度优先搜索算法

#include "stdio.h"

#include "malloc.h"

#define MaxVerNum 8

#define MAXSIZE 100 //顶点最大个数

#define False 0

#define True 1

int visited[MaxVerNum];//全局变量，0表示未被访问过，1表示已被访问过

typedef char VertexType;

typedef struct node //邻接表节点.

{

int adjvex; //邻接点的位置

struct node* next; //指向下一个节点

}EdgeNode; //邻接表中的节点类型

typedef struct vnode //顶点节点.

{

VertexType vertex; //顶点信息

EdgeNode* firstedge; //指向第一个邻接表节点

}VertexNode; //表头节点类型

typedef struct

{

VertexNode adjlist[MaxVerNum];//存储邻接表节点的一维数组

int n,e; //定义顶点数n和边数e

}ALGraph; //邻接表类型

void CreateALGraph (ALGraph* G) //建立邻接表函数.

{

int i,j,k,s;

char y;

EdgeNode* p; //工作指针.

printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n");

scanf("%d,%d",&(G->n),&(G->e));

scanf("%c",&y); //用y来接收回车符.

for(s=0;sn;s++)

{

printf(“请输入下标为%d的顶点的元素:\n",s);

scanf("%c",&(G->adjlist[s].vertex));

scanf("%c",&y);//用y来接收回车符.当后面要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。

G->adjlist[s].firstedge=NULL;

}

printf("请分别输入该图的%d条弧\n",G->e);

for(k=0;ke;k++)

{

printf("请输入第%d条弧的起点和终点（起点下标,终点下标）:\n",(k+1));

scanf("%d,%d",&i,&j);

p=(EdgeNode*)malloc(sizeof(EdgeNode))

p->adjvex=j;

p->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=p;

}

void DFS(ALGraph* G,int v) //深度优先遍历

{

EdgeNode* p;

int w;

printf("%c ",G->adjlist[v].vertex);

visited[v]=True;

for(p=G->adjlist[v].firstedge;p;p=p->next)

w=p->adjvex;

if(!visited[w])

DFS(G,w); //对于没有访问过的顶点，调用深度优先搜索函数

}

void DFStraverse(ALGraph* G)

{

int v;

for(v=0;vn;v++)

{

visited[v]=False;

}

for(v=0;vn;v++) //对v尚未访问到的邻接点w进行一个递归遍历{

if(!visited[v])

DFS(G,，v)

}

int main()

{

ALGraph net; //定义一个有向图

CreateALGraph(&net); //创建一个给定的有向图

printf("图的深度优先遍历为：\n");

DFStraverse(&net); //进行该有向图的深度优先遍历，并打印结果

printf("\n");

return 0;

}

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

连通图深度优先遍历

#include #include #define MAXLEN 20 typedef struct node3 { int adjvex; struct node3 *next; }ARCNODE; typedef struct { char data; ARCNODE *firstarc; int id; } VEXNODE; typedef struct { VEXNODE vertices[MAXLEN]; int vexnum, arcnum; int kind; }ALGRAPH; int visited[MAXLEN]; ALGRAPH creat_graph() { ARCNODE *p; int i, s, d; ALGRAPH g; printf("\n\n输入顶点数和边数(用逗号隔开) : "); scanf("%d,%d", &s, &d);fflush(stdin); g.vexnum = s; /*存放顶点数在g.vexnum 中 */ g.arcnum = d; /*存放边点数在g.arcnum 中*/ printf("\n\n"); for(i = 0; i < g.vexnum; i++) /*输入顶点的值*/ {printf("输入顶点 %d 的值 : ", i + 1); scanf("%c", &g.vertices[i].data); fflush(stdin); g.vertices[i].firstarc = NULL;} printf("\n"); for(i = 0; i < g.arcnum; i++) {printf("输入第 %d 条边的起始顶点和终止顶点下标(用逗号隔开): ", i+1);

图的深度优先遍历算法课程设计报告

合肥学院计算机科学与技术系课程设计报告 2013～2014学年第二学期课程数据结构与算法课程设计名称图的深度优先遍历算法的实现学生姓名陈琳学号1204091022 专业班级软件工程指导教师何立新 2014 年9 月一：问题分析和任务定义涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。

深度优先遍历图的方法是，从图中某顶点v 出发：（1）访问顶点v ；（2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问；（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。二：数据结构的选择和概要设计设计流程如图：图1 设计流程利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。

所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;sn;s++) { printf("请输入下标为%d的顶点的元素:\n",s); scanf("%c",&(G->adjlist[s].vertex)); scanf("%c",&y); //用y来接收回车符.当后面要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。 G->adjlist[s].firstedge=NULL; } printf("请分别输入该图的%d条弧\n",G->e); for(k=0;ke;k++) { printf("请输入第%d条弧的起点和终点（起点下标,终点下标）:\n",(k+1)); scanf("%d,%d",&i,&j); p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=j; p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; } } 2.深度优先遍历 void DFS(ALGraph* G,int v) //深度优先遍历 { EdgeNode* p;

图的深度优先遍历实验报告

一．实验目的熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。二．实验原理深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验内容编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20

人工智能深度优先算法课程设计报告

人工智能课程报告题目：深度优先算法班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX

【摘要】结合生活中解决搜索问题所常用的思考方法与解题方法，从深度优先探讨了提高程序效率的适用技巧。【关键词】1搜索顺序；2搜索对象；3搜索优化；一、深度优先搜索的优化技巧我们在做事情的时候，经常遇到这类问题——给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。二、搜索的顺序及对象：在解决约束满足问题的时候，问题给出的约束条件越强，对于搜索就越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过程中很好的利用了题目中的约束条件进行优化，达到提高程序效率的目的。显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件优化效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。三、搜索特点 1.由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。 2.深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。

3.由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。 4.深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。 5.适用范围：适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。四、算法数据结构描述深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN 表，直到搜索到目标结点或OPEN栈空为止。具体算法如下： ①把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。 ②如果OPEN为一空表，则搜索失败退出。 ③取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。 ④如果结点ｎ的深度等于最大深度，则转向２。 ⑤否则，扩展结点ｎ，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向ｎ的返回指针；如果没有后裔，则转向２。 ⑥如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向２。

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue