当前位置：文档库 › 图的遍历课程设计

图的遍历课程设计

题目图的遍历

教学院计算机

专业

班级

姓名

指导教师

2011 年12 月31 日

课程设计任务书

2010 ～2011 学年第1 学期

学生姓名：专业班级：

指导教师：工作部门：

一、课程设计题目

图的遍历

二、课程设计内容（含技术指标）

1．显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。

2．当用户选择的功能错误时，系统会输出相应的提示。

3．通过图操作的实现，把一些实际生活中的具体的事物抽象出来

三、进度安排

1．初步完成总体设计，搭好框架；

2．完成最低要求：两种必须都要实现，写出画图的思路；

3．进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。

四、基本要求

1．界面友好，函数功能要划分好

2．程序要加必要的注释

3．要提供程序测试方案

一概述 (1)

1.问题描述 (1)

2.系统分析 (1)

3.课程设计（论文）进程安排 (1)

二.总体设计方案 (2)

1．整体设计思路 (2)

2．算法的整体思路 (3)

3．工作内容 (3)

三详细设计 (4)

1.详细设计思路及算法 (4)

2.程序流程图 (11)

四程序的调试与运行结果说明 (12)

１.运行结果 (12)

五．课程设计总结 (15)

参考文献 (16)

附录 A 原程序清单 (16)

数据结构课程设计成绩评定表 (30)

一概述

1.问题描述

1)函数功能要划分好

2)总体设计应画流程图

3)程序要加必要的注释

4)要提供程序测试方案

2.系统分析

1)掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力

2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技

能

3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力

4)训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备

的科学的工作方法和作风

3.课程设计（论文）进程安排

二.总体设计方案

1．整体设计思路

图的邻接矩阵：

对于一个具有n个顶点的图，可以使用n*n的矩阵（二维数组）来表示它们间的邻接关系。

图的邻接表：

邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

深度优先遍历的递归算法思想：

假定以图中某个顶点V i为出发点，首先访问出发点，然后选择一个V i的未访问过的邻接点V j，以V j为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。

1)访问结点V并标记结点V为已访问；

2)查找结点V的第一个邻接结点W；

3)若结点W的临界结点W存在，则继续执行，否则算法结束；

4)若结点W尚未被访问，则递归访问结点W；

5)查找结点V的W临界结点的下一个临界结点W ，转到步骤（3）。

广度优先遍历算法：

从图的某一顶点V i出发，访问此顶点后，依次访问V i的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。

1)访问初始结点V并标记结点V为已访问；

2)结点V入队列；

3)当队列非空时则继续执行，否则算法结束；

4)出队列取得队头结点U；

5)查找结点U的第一个邻接结点W；

6)若结点U的邻接结点W不存在，则转到步骤（3），否则循环执行下列步骤：

a)（6.1）若结点W尚未被访问，则访问结点W并标记结点W

为已访问；

b)（6.2）结点W入队；

c)（6.3）查找结点U的W邻接结点的下一个邻接结点W，转到

步骤（6）。

普利姆算法思想：

令集合U的初值为U={u0}，集合T的初值为T={}。从所有结点u属于U和结点v属于V\U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断反复，当U=V时，最小生成树便构造完毕。

克鲁斯卡尔算法思想：

设无向连通带权图G=(V,E)，其中V为结点的集合，E为边的集合。设带权图G 的最小生成树T由结点集合和边的集合构成，其初值为T=(v,{}),即初始时最小生成树T只由带权图G中的结点集合组成，各结点之间没有一条边。这样，最小生成树T中的各个结点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中边集合E的各条边，若被考察的边的两个结点属于T的两个不同的连通分量，则将此边加入懂啊最小生成树T中，同时，把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树。

连通分量：

非连通图的每一个连通部分。

2．算法的整体思路

本系统能分别用邻接矩阵存储结构和邻接表存储结构构造无向图，然后在此无向图中能实现深度优先遍历，广度优先遍历，最小生成树和连通分量的算法。

3．工作内容

1.显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。

2.当用户选择的功能错误时，系统会输出相应的提示。

3.通过图操作的实现，把一些实际生活中的具体的事物抽象出来。

三详细设计1.详细设计思路及算法

图1-1 无向图1.程序中所用变量的定义:

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

2.邻接矩阵的定义：

typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct {

char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;

A 0 50 60

0 0 0 0 B 50

0 0 65 40 0 0 C 60 0 0 52 0 0 45 D 0 65 52 0 50 30 0 E 0 40 0 50 0 70 0 F 0 0 0 30 70 0 80 G 0 0 45 0 0 80 0

图1-2 邻接矩阵

3.邻接表：

表1-1 邻接表

4.深度优先遍历：

void adjprint(algraph gra)

5.广度优先遍历：

void bfstra(algraph gra)

6.最小生成树PRIM算法：

7.最小生成树KRUSCAL算法：

2.程序流程图

四程序的调试与运行结果说明１.运行结果

图2-1 输入顶点数

图2-2 输入权值

无向图创建成功

图2-3 菜单

图2-4 邻接矩阵

图2-5 邻接表

图2-6 深广度优先遍历

图2-7 最小生成树

图2-8 连通分量

五．课程设计总结

课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。

对于我们学生来讲，此次课程设计是为了让我们训练自己的实际设计能力，通过设计实践，去真正获得此项目管理和团队协作等方面的基本训练和工作经验。通过课程设计的一系列训练，我们能提高如何综合运用所学知识解决实际问题的能力，以及获得此项目管理和团队协作等等众多方面的具体经验，增强对相关课程具体内容的理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。

通过这近一个星期的数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。

此次课程设计也让我认识到必须培养严谨的态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的态度。我想这不仅是对于程序设计，做任何事都应如此。

在实践过程中，我和组员分工合作，勇于提出问题，解决难题，在实践中，我遇到了许多困难，但都一一克服了。最终我圆满的完成此次课程设计，学到了很多东西。同时，程序还存在着一些缺陷，就是不能输出原图，存在一些局限性，不过我会继续努力思考，完善程序，做到最好。

此次试验，老师对我的指导是至关重要的，在此我非常感谢老师，从她那我学到了很多有关c语言的知识，为以后的学习打下了一定的基础。

总的来说，本次课程设计，不仅我的知识面有所提高，另外我的综合素质也有所提高，，比如说：团队精神、提问能力、思考能力等等。这次课程设计为我以后更好的学习和使用c语言打下了基础。

参考文献

[1]数据结构—使用C语言（第3版）朱战立编，西安交通大学出版社。

[2] Visual C++程序设计──基础与实例分析.北京：清华大学出版社，2004

附录A 原程序清单

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

//…………………………………………邻接矩阵定义……………………

typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct

{

char vexs[20];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

int localvex(MGraph_L G,char v)//返回V的位置

{

int i=0;

while(G.vexs[i]!=v)

{

++i;

}

return i;

}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示

{

char v1,v2;

int i,j,w;

cout<<"…………创建无向图…………"<

cin>>G.vexnum>>G.arcnum;

for(i=0;i!=G.vexnum;++i)

{

cout<<"输入顶点"<

cin>>G.vexs[i];

}

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for(int k=0;k!=G.arcnum;++k)

{

cout<<"输入一条边依附的顶点和权:(a b 3)不包括()"<

cin>>v1>>v2>>w;//输入一条边依附的两点及权值

i=localvex(G,v1);//确定顶点V1和V2在图中的位置

j=localvex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

cout<<"图G邻接矩阵创建成功！"<

return G.vexnum;

}

void ljjzprint(MGraph_L G)

{

int i,j;

for(i=0;i!=G.vexnum;++i)

{

for(j=0;j!=G.vexnum;++j)

cout<

}

int visited[max];//访问标记

图的深度广度优先遍历操作代码

一、实验目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构； 2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用； 3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。二、实验内容实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。 [程序代码] 头文件： #include #include #define MAX_VERTEX_NUM 30 #define MAX_QUEUE_NUMBER 30 #define OK 1 #define ERROR 0 #define INFEASIBLE -1

图的遍历操作实验报告

. .. . .. .. 实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。三、DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、示例程序 1．邻接矩阵作为存储结构的程序示例

#include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 }

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 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)

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

数据结构实验报告-图的遍历

数据结构实验报告实验：图的遍历一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。四、程序实现及结果： 1、邻接矩阵： #include #include #define VERTEX_MAX 30 #define MAXSIZE 20 typedef struct { int arcs[VERTEX_MAX][VERTEX_MAX] ; int vexnum,arcnum; } MGraph; void creat_MGraph1(MGraph *g) { int i,j,k; int n,m; printf("请输入顶点数和边数:"); scanf("%d%d",&n,&m); g->vexnum=n; g->arcnum=m; for (i=0;iarcs[i][j]=0;

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

合肥学院计算机科学与技术系课程设计报告 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;

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R={VR} VR={ | v，w v且P(v，w)，表示从v到w得弧，谓词P(v，w)定义了弧的意义或信息} } ADT Graph 2.此抽象数据类型中的一些常量如下： #define TRUE 1 #define FALSE 0 #define OK 1 #define max_n 20 //最大顶点数 typedef char VertexType[20]; typedef enum{DG, DN, AG, AN} GraphKind; enum BOOL{False,True}; 3.树的结构体类型如下所示：

数据结构实验---图的储存与遍历

学号：姓名：实验日期： 2016.1.7 实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示 V0 V1 V2 V3 V4 三、附录：在此贴上调试好的程序。 #include #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

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

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

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

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

数据结构图的遍历

#include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ivexnum;i++) if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

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

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 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