实验报告
while(w!=-1){
if(visited[w]==0){
visit(w);
EnQueue(q,w);
visited[w]=1;
}
w=NextAdj(g,v);
}
}
}
void Travel_BFS(VNode g[],int visited[],int n){
int i;
for(i=0;i visited[i]=0; } for(i=0;i if(visited[i]==0) BFS(g,i,visited); } } 实验心得: 通过本次实验,我理解图的逻辑特点,理解图的邻接矩阵或邻接表存储结构,掌握图的深度优先遍历、广度优先遍历算法。实验中遇到了很多问题,通过与同学交流沟通,最终完成了本次实验,希望以后能再接再厉。 合肥学院 计算机科学与技术系 课程设计报告 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;s 深度优先遍历 一、实验目的 了解深度优先遍历的基本概念以及实现方式。 二、实验内容 1、设计一个算法来对图的进行深度优先遍历; 2、用C语言编程来实现此算法。用下面的实例来调试程序: 三、使用环境 Xcode编译器 四、编程思路 深度优先遍历图的方法是,从邻接矩阵出发:访问顶点v;依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;构造一个遍历辅助矩阵visited[]进行比较若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止,并将顶点信息存储在数组Q[]里面。反复搜索可以通过使用函数的嵌套来实现。 五、调试过程 1.程序代码: //为方便调试,程序清晰直观删除了邻接矩阵的构造函数, //并且修改了main()函数,只保留了DFS函数 #include #include 上机实验报告 学院:计算机与信息技术学院 专业:计算机科学与技术(师范)课程名称:数据结构 实验题目:深度优先遍历(邻接矩阵)班级序号:师范1班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号 一、实验目的: 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。 二、实验环境: Windows 8.1 Microsoft Visual c++ 6.0 二、实验内容及要求: 编写图的深度优先遍历邻接矩阵算法。建立图的存储结构,能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 四、概要设计: 深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问,则深度优先遍历可从图的某个顶点V出发,访问此顶点,然后依次从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中的一个未被访问的顶点,重复上述过程,直至图中所有顶点都被访问到为止。 以图中无向图G4为例,深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索,在访问了顶点V1后,选择邻接点V2。因为V2未曾访问,则从V2出发进行搜索。依次类推,接着从V4,V8,V5出发进行搜索。在访问了V5之后,由于V5的邻接点已都被访问,则搜索回到V8。由于同样的理由,搜索继续回到V4,V2直至V1,此时由于V1的另一个邻接点为被访问,则搜索又从V1到V3,再继续进行下去。由此得到顶点的访问序列为: V1 V2 V4 V8 V5 V3 V6 V7 五、代码 #include 一.实验目的 熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法,并能运用图的深度优先搜索遍历一个图,对其输出。 二.实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问,则深度优先搜索可从图中某个顶点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 实验四:图的遍历 题目:图及其应用——图的遍历 班级:姓名:学号:完成日期: 一.需求分析 1.问题描述:很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。 2.基本要求:以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据:教科书图7.33。暂时忽略里程,起点为北京。 4.实现提示:设图的结点不超过30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制,注意,生成树的边是有向边,端点顺序不能颠倒。 5.选作内容: (1).借助于栈类型(自己定义和实现),用非递归算法实现深度优先遍历。 (2).以邻接表为存储结构,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能,需要有一个图的抽象数据类型。该抽象数据类型的定义为: ADT Graph { 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R: R={VR} VR={ #include 华北水利水电学院数据结构实验报告 20 10 ~20 11 学年第一学期2008级计算机专业 班级:107学号:200810702姓名:王文波 实验四图的应用 一、实验目的: 1.掌握图的存储结构及其构造方法 2.掌握图的两种遍历算法及其执行过程 二、实验内容: 以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现无向连通图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。 提示:首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先和广度优先遍历,并输出遍历的结果。 三、实验要求: 1.各班学号为单号的同学采用邻接矩阵实现,学号为双号的同学采用邻接表实现。 2.C/ C++完成算法设计和程序设计并上机调试通过。 3.撰写实验报告,提供实验结果和数据。 4.写出算法设计小结和心得。 四、程序源代码: #include { int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2; 题目: 图的深度优先遍历算法 一、实验题目 前序遍历二叉树 二、实验目的 ⑴掌握图的逻辑结构; ⑵掌握图的邻接矩阵存储结构; ⑶验证图的邻接矩阵存储及其深度优先遍历操作的实现。 三、实验内容与实现 ⑴建立无向图的邻接矩阵存储; ⑵对建立的无向图,进行深度优先遍历;实验实现 #include typedef struct EdgeNode { int adjvex; struct EdgeNode *next; }EdgeNode; typedef struct VertexNode { VertexType data; EdgeNode *firstedge; }VertexNode,AdjList[MaxVex]; typedef struct Graph{ AdjList adjList; int numVertexes,numEdges; }Graph,*GraphAdjList; typedef struct LoopQueue{ int data[MaxVex]; int front,rear; }LoopQueue,*Queue; void initQueue(Queue &Q){ Q->front=Q->rear=0; } Bool QueueEmpty(Queue &Q){ if(Q->front == Q->rear){ return TRUE; }else{ return FALSE; } } Bool QueueFull(Queue &Q){ if((Q->rear+1)%MaxVex == Q->front){ return TRUE; }else{ return FALSE; } } void EnQueue(Queue &Q,int e){ if(!QueueFull(Q)){ Q->data[Q->rear] = e; *问题描述: 建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图,其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵: 1,若(Vi,Vj)∈E 或 若图中每个顶点只含一个编号i(1≤i≤vnum),则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下: type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相联,并容易求得各个顶点的度。 对于无向图,顶点Vi的度是邻接矩阵中第i行元素之和,即 n n D(Vi)=∑A[i,j](或∑A[i,j]) j=1 i=1 对于有向图,顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和,顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)=∑A[i,j],OD(Vi)=∑A[j,i]) j=1j=1 用邻接矩阵也可以表示带权图,只要令 Wij, 若 2007-05-27 晴 //采用非递归深度优先遍历算法,可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 福建江夏学院 《数据结构与关系数据库(本科)》实验报告姓名班级学号实验日期 课程名称数据结构与关系数据库(本科)指导教师成绩 实验名称:深度优先遍历以邻接表存储的图 一、实验目的 1、掌握以邻接表存储的图的深度优先遍历算法; 二、实验环境 1、硬件环境:微机 2、软件环境:Windows XP,VC6.0 三、实验内容、步骤及结果 1、实验内容: 基于图的深度优先遍历编写一个算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。 2、代码: #include 精品文档数据结构 实 验 报 告 目的要求 1.掌握图的存储思想及其存储实现。 2.掌握图的深度、广度优先遍历算法思想及其程序实现。 3.掌握图的常见应用算法的思想及其程序实现。 实验内容 1.键盘输入数据,建立一个有向图的邻接表。 2.输出该邻接表。 3.在有向图的邻接表的基础上计算各顶点的度,并输出。 4.以有向图的邻接表为基础实现输出它的拓扑排序序列。 5.采用邻接表存储实现无向图的深度优先递归遍历。 6.采用邻接表存储实现无向图的广度优先遍历。 7.在主函数中设计一个简单的菜单,分别调试上述算法。 源程序: 主程序的头文件:队列 #include *问题描述: 建立图的存储结构,能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图,其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵: 1,若(Vi,Vj)∈E 或 对于有向图,顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和,顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)=∑A[i,j],OD(Vi)=∑A[j,i]) j=1j=1 用邻接矩阵也可以表示带权图,只要令 Wij, 若 实验报告 一、实验目的和内容 1. 实验目的 掌握图的邻接矩阵的存储结构;实现图的两种遍历:深度优先遍历和广度优先遍历。 2. 实验内容 1.图的初始化; 2.图的遍历:深度优先遍历和广度优先遍历。 二、实验方案 程序主要代码: /// { public static int Max_Vertex_Num = 20; // 最大顶点数 private object [] Vexs; // 顶点数据数组 private ArcCell [,] Arcs; // 邻接矩阵 private GKind Kind; // 图的种类 private int VexNum,ArcNum; // 当前顶点数和弧数 /// 数据结构实验报告 实验四图的应用 一、实验题目: 图的应用——xx优先/xx优先搜索遍历 二、实验内容: 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法,实现图的深度优先和广度优先搜索遍历操作。 要求: 以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现连通无向图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。(注: 学号为奇数的同学使用邻接矩阵存储结构实现,学号为偶数的同学使用邻接矩阵实现) 提示: 首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先、广度优先搜索遍历,并输出遍历的结果。 三、程序源代码: #include int adjvex;//该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode; typedef struct VNode{ int data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; }ALGraph; typedef struct QNode{ int data; struct QNode *next; }QNode,*QuePtr; typedef struct{ QuePtr front;//队头指针 QuePtr rear;//队尾指针 }LinkQue; void InitQue(LinkQue &q){} void EnQue(LinkQue &q,int e){} int DeQue(LinkQue &q){int e; 算法设计:深度优先遍历和广度优先遍历实现 深度优先遍历过程 1、图的遍历 和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意: 以下假定遍历过程中访问顶点的操作是简单地输出顶点。 2、布尔向量visited[0..n-1]的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后,又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点,必须记住每个已访问的顶点。为此,可设一布尔向量visited[0..n-1],其初值为假,一旦访问了顶点Vi之后,便将visited[i]置为真。 -------------------------- 深度优先遍历(Depth-First Traversal) 1.图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的 实验项目名称:图的遍历 一、实验目的 应用所学的知识分析问题、解决问题,学会用建立图并对其进行遍历,提高实际编程能力及程序调试能力。 二、实验内容 问题描述:建立有向图,并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数,能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机,Code::Blocks。 四、实验原理 用邻接表存储一个图,递归方法深度搜索和用队列进行广度搜索,并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 重庆邮电大学 数学大类专业 2008级《数学建模与数学实验》课程设计 设计题目:图的深度优先搜索遍历算法分析及其应用设计时间:2010.9.7-----2010.9. 12 班级: 学号: 指导教师: 图的深度优先搜索遍历算法分析及其应用 摘要:文章介绍了图论,图的基本概念及其图的表示方法。详细的分析了图中以邻接表为存储结构进行的图的深度优先搜索遍历的算法,并且在VC++环境中实现其算法的过程,对运行记过做了一定量的分析,最后介绍了基于该算法的一些应用。 关键词:图;深度优先搜索;遍历;算法 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。 图(Graph)是一种较线性表和树更复杂的数据结构,图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。因此,在研究有关图的问题时,要考虑图中每个顶点的信息,访问图中的各个顶点,而访问图中各个顶点的操作过程即使图的遍历,图的遍历算法是求解图的连通性问题,拓扑排序和求关键路径等算法的基础。 1图的三元组定义 图G是一个三元组由集合V,E和关联函数组成,记为:G=(V,E,W(G))。其中V是顶点的集合,表示V(G)={V1,V2,V3,……Vn},V(G)≠NULL。E是V中的点偶对的有穷集,表示为E(G)={e1,e2,e3……em},其中ei为图的深度优先遍历算法课程设计报告
图论深度优先搜索实验报告
连通图深度优先遍历
深度优先遍历(邻接矩阵)
图的深度优先遍历实验报告
图的遍历实验报告
邻接矩阵的深度优先遍历
图的深度优先遍历和广度优先遍历
数据结构实验报告图的深度优先遍历算法
邻接矩阵表示图深度广度优先遍历
采用非递归深度优先遍历算法
2-深度优先遍历以邻接表存储的图-实验报告
数据结构实验—图实验报告
邻接矩阵表示图_深度_广度优先遍历
图的深度和广度遍历-实验报告
实验四-图的应用――深度优先/广度优先搜索遍历
算法设计:深度优先遍历和广度优先遍历
数据结构 图的遍历 实验报告
图的深度优先搜索遍历算法分析及其应用