实验五 图的遍历及其应用实现
实验五图的遍历及其应用实现
班级：软件091 姓名：郭靖学号：200900834126
一、实验目的
1．熟悉图常用的存储结构。
2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。
3．会用图的遍历解决简单的实际问题。
二、实验内容
[题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。
提示：
输入示例
上图的顶点和边的信息输入数据为：
5 7 DG
A B C D E
AB AE BC CD DA DB EC
[题目二]：在图G中求一条从顶点 i 到顶点 s 的简单路径三、实验步骤
㈠、数据结构与核心算法的设计描述
1、/* 输入图的顶点和边的信息,建立图*/
void CreateGraph(MGraph &G)
2、/* 深度优先搜索遍历图*/
int FirstAdjVex(MGraph &g,int i)
{//得到图g中i节点的第一个邻结点
}
int NextAdjVex(MGraph &g,int i,int w)
{//得到图g中结点i相对于w的下一个邻结点
}
void DFSTraverse(MGraph &G,int v)
{// 从顶点v出发，深度优先搜索遍历连通图 G
}
3、/* 深度优先搜索遍历图*/
void BFSTraverse(MGraph &G, int v)
{从顶点v出发，广度优先搜索遍历连通图 G
}
4、/*在图G中求一条从顶点 i 到顶点 s 的简单路径*/
void Append(MGraph G,char *PATH,int v)
{//把图中顶点v加入路径PATH
}
void Delete(char *PATH,int v)
{//从路径PATH中删除v
}
void DFSearch(MGraph &G, int v, int s, char *PATH)
{//在图G中求一条从顶点v到顶点s的简单路径
}
㈡、函数调用及主函数设计
主函数实现比较简单，这里不再描述，代码尽最后程序清单。㈢程序调试及运行结果分析
1、运行程序后，依次按要求输入图信息，如下：
2、按回车，可得到深度和广度优先遍历的结果，如下：
3、按回车，提示输入查找路径的起点和终点，输入后回车，可得到
其简单路径，如下：
㈣实验总结
四、主要算法流程图及程序清单
1、主要算法流程图
深度优先遍历流程图
2、程序清单
#includ e
using namespace std;
#d efine MAX_VERTEX_NUM 20
#d efine OK 1
#d efine ERROR 0
#d efine OVERFLOW -1
typed ef enum{ DG, DN, UDG, UDN } GraphKind;
typed ef int status;
typed ef struct ArcNod e // 弧结点
{ int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置
struct ArcNod e *nextarc; //链域，指示依附于vi的下一条边或弧的结点，
}ArcNod e;
typed ef struct VNode //表头结点
{ char vexdata; //存放顶点信息
struct ArcNod e *firstarc; //指示第一个邻接点
}VNod e,AdjList[MAX_VERTEX_NUM];
typed ef struct { //图的结构定义
AdjList vertices; //顶点向量
int vexnum, arcnum;
// GraphKind kind=0; // 图的种类标志
} MGraph;
int LocateVex(MGraph &G,char v){
for(int i=0;i if(G.vertices[i].vexdata==v) return i; } return -1; } void CreateGraph(MGraph &G) {// 生成图G的存储结构-邻接表 cout<<"输入顶点数、边数:"< cin >> G.vexnum >> G.arcnum ; // 输入顶点数、边数和图类 // G.vexnum=5;G.arcnum=7; cout<<"输入顶点:"< for (int i=0; i // 构造顶点数组： cin>> G.vertices[i].vexdata; // 输入顶点 G.vertices[i].firstarc = NULL; } cout<<"输入各边:"< for (int k=0; k { char sv,tv; cin>>sv>> tv; // 输入一条边（弧）的始点和终点 i = LocateVex(G, sv); int j = LocateVex(G, tv);// 确定sv和tv在G中位置，即顶点在G.vertices中的序号 ArcNod e * pi = new ArcNod e; if (!pi) exit(-1); // 存储分配失败 pi -> adjvex = j; // 对弧结点赋邻接点"位置 pi -> nextarc = G.vertices[i].firstarc;//头插法，将tv结点插入到第i个单链表中 G.vertices[i].firstarc = pi; // 插入链表G.vertices[i] } cout<<"构造成功!"< } /*----------------深度优先遍历图--------------------*/ bool visited[10]; ArcNod e *nextnod e=NULL;//全局变量 //得到i号顶点的第一个邻接点 int FirstAdjVex(MGraph &g,int i){ ArcNod e *p; p=g.vertices[i].firstarc; if(!p) return -1; return(p->adjvex); } //得到i号顶点的下一个邻接点 int NextAdjVex(MGraph &g,int i,int w){ if(!w) return -1; ArcNod e *p; p=g.vertices[i].firstarc; whil e (p&&p->adjvex!=w) { p=p->nextarc; } if (!p||!p->nextarc) { return -1; } int m=p->nextarc->adjvex; return m; } void DFSTraverse(MGraph &G,int v) { // 从顶点v出发，深度优先搜索遍历连通图G visited[v] = true; cout< for (int w=FirstAdjVex(G, v);w!=-1;w=NextAdjVex(G,v,w)) //返回V的(相对于w)下一邻接点 if (!visited[w]) DFSTraverse(G,w);// 对v的尚未访问的邻接顶点w 递归调用DFS } /*----------------广度优先遍历图--------------------*/ /*****队列定义******/ typed ef struct Nod e { int data; struct Nod e *next; }QNod e,*QueuePtr; typed ef struct { QueuePtr front; QueuePtr rear; }LinkQueue; //初始化队列 status InitQueue(LinkQueue &Q) { Q.front=Q.rear=(QueuePtr)mall oc(sizeof(QNode)); if (!Q.front) return OVERFLOW; Q.front->next=NULL; return OK; } //入队列 status EnQueue(LinkQueue &Q,int e) { //将e压入队列 QueuePtr p=(QueuePtr)malloc(sizeof(QNod e)); if (!p) { return OVERFLOW; } p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } //出队列 status DeQueue(LinkQueue &Q,int &e) { //获得队列首元素，并赋值给e if (Q.front==Q.rear) { return ERROR; } QueuePtr p=Q.front->next; e=p->data; Q.front->next=p->next; if (Q.rear==p) Q.rear=Q.front; free(p); return OK; } //判空 status IsEmptyQueue(LinkQueue &Q) { if (Q.front==Q.rear) return 1; else return 0; } //清空队列 status Cl earQueue(LinkQueue &Q) { Q.front=Q.rear; return OK; } /*******************/ void BFSTraverse(MGraph &G, int v) { LinkQueue Q; InitQueue(Q); visited[v] = true; cout< EnQueue(Q, v); // v入队列 whil e (!IsEmptyQueue(Q)) { int u; DeQueue(Q,u); // 队头元素出队并置为u for(int w=FirstAdjVex(G,u);w!=-1; w=NextAdjVex(G,u,w)) if ( ! visited[w]){ visited[w]=true; cout< EnQueue(Q, w); // 访问的顶点w入队列 } } } /*---------------在图G中求一条从顶点i 到顶点s 的简单路径---------------------*/ int pathcount=0; void Append(MGraph G,char *PATH,int v) { PATH[pathcount]=G.vertices[v].vexdata; pathcount++; } void Del ete(char *PATH,int v) { pathcount--; } bool found=false; void DFSearch(MGraph &G, int v, int s, char *PATH) { if (found) { return; } visited[v] = true;// 访问第v 个顶点，并置访问标志 Append(G,PATH, v);//把顶点v加入路径 for (int w=FirstAdjVex(G, v);w!=-1&&!found;w=NextAdjVex(G,v,w)) { if (w==s) { found =true; Append(G,PATH, w); return;//exit(1); }//找到退出 else if(!visited[w]) DFSearch(G,w, s, PATH);//加入w } //end for if (!found) Del ete(PATH,v); } /*----------------main（）函数--------------------*/ int main() { MGraph G; CreateGraph(G); int i; for (i=0;i<10;i++) { visited[i]=false; } cout<<"深度优先遍历："< DFSTraverse(G,4); cout< for (i=0;i<10;i++) { visited[i]=false; } cout<<"广度优先遍历："< BFSTraverse(G,0); cout< for (i=0;i<10;i++) { visited[i]=false; } char PATH[20]; char st,ed; cout<<"输入起点和终点"< cin>>st>>ed; DFSearch(G,LocateVex(G, st),LocateVex(G, ed),PATH); for (i=0;i<=pathcount;i++) { cout< } cout< return 0; } . .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握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;i 数据结构课程设计 设计说明书 图的遍历的实现 数学与计算机科学学院 2014年1 月 4日 学生姓名 英 茜 学 号 1118064033 班 级 网络1101班 成 绩 指导教师 申 静 课程设计任务书 2013—2014学年第一学期 课程设计名称：数据结构课程设计 课程设计题目：图的遍历实现 完成期限：自2013年12 月23日至2014年 1 月4 日共 2 周 设计内容： 1. 任务说明 (1) 采用邻接表存储结构创建一个图； (2) 编程实现图的深度优先搜索（或广度优先搜索）遍历算法； (3) 输出遍历结果； (4) 给定具体数据调试程序。 2. 要求 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？ 2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析； 7）编写课程设计报告。 3. 参考资料 指导教师：申静教研室负责人：余冬梅 课程设计评阅 摘要 针对图问题中如何更好地实现图的遍历问题，以无向图为例，分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以VC++为开发环境进行系统的设计和实现，其运行结果表明，系统能很好地完成遍历后节点的输出，实现了遍历的目的，系统界面友好，可操作性强。 关键词：数据结构；存储结构；邻接矩阵 实验四图的存储、遍历与应用 1、实验目的 1）熟悉图的邻接矩阵和邻接表的两种常用存储结构 2）掌握两种常用存储方式下深度优先遍历(dfs)和广度优先遍历（BFS）操作的实现及其应用。 3）进一步掌握递归算法的设计方法。 2、实验内容 1）图的两种存储结构实现： （1）邻接矩阵存储：用一个一维数组来存储顶点信息，用一个二维数组存储用于表示顶点间相邻的关系（边） （2）邻接表存储：用一个一维数组来存储顶点信息，用一个链表表示与顶点相连的边。 表示法类似于树的孩子链表表示法。 2）图的遍历 （1）对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历：建立一个图的邻接矩阵表示，输出以某顶点为起始点的DFS和BFS序列。 实现提示：图的DFS遍历可通过递归调用或用栈来实现。其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。BFS 遍历可利用队列来帮助实现，也可以用栈。实现方法与二叉树的层次遍历类似。 （2）对以邻接表为存储结构的图进行DFS和BFS遍历：以邻接表为存储结构，实现图的DFS和BFS遍历，输出以某顶点为起始点的DFS和BFS序列。 实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。只是由于图的存储形式不同。而具体到取第一个邻接点和下一个邻接点的语句表示上有所差别而已。 （3）测试数据：自己设计测试用的图，给出其邻接矩阵存储表示。也可以用如下图作为测试数据。 武汉东湖学院 实验报告 学院：计算机科学学院—专业计算机科学与技术2016年11月18日 1.实验目的 (1)了解邻接矩阵存储法和邻接表存储法的实现过程。 (2)了解图的深度优先遍历和广度优先遍历的实现过程。 2.实验内容 1.采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵 2.设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法 3.实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列 4.实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列 3.实验环境Visual C++ 6.0 4 .实验方法和步骤（含设计） 我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可 知， 其邻接矩阵示意图为如下： V0 v1 v2 v3 v4 v5 V0 1 0 1 0 1 V1 1 0 1 1 1 0 V2 0 1 0 0 1 0 V3 1 1 0 0 1 1 V4 0 1 1 1 0 0 V5 1 1 此时的 “1 ” 表示这两个节点有关系，“ 0”表示这两个节点无关系 我们通过邻接表来在计算机中存储图时，其邻接表存储图如下: 5.程序及测试结果 #include 实验四：图的遍历 题目：图及其应用——图的遍历 班级：姓名：学号：完成日期： 一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容： （1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。 （2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR} VR={ 数据结构课程设计 设计说明书 图的遍历的实现 学生姓名英茜 学号1１18064０33 班级网络1101班 成绩 指导教师申静 数学与计算机科学学院 2０14年1 月4日 课程设计任务书 2013—２０14学年第一学期 课程设计名称:数据结构课程设计 课程设计题目:图的遍历实现 完成期限：自2013年1２月23日至2014年１月4日共 2 周 设计内容： 1. 任务说明 (1）采用邻接表存储结构创建一个图； (２）编程实现图的深度优先搜索(或广度优先搜索)遍历算法; (3) 输出遍历结果； (4) 给定具体数据调试程序。 ２．要求 １）问题分析和任务定义：根据设计题目的要求,充分地分析和理解问题，明确问题要求做什么? 2)逻辑设计：写出抽象数据类型的定义，各个主要模块的算法,并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析; 7)编写课程设计报告。 3. 参考资料 指导教师:申静教研室负责人：余冬梅 课程设计评阅 摘要 针对图问题中如何更好地实现图的遍历问题，以无向图为例,分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以ＶＣ++为开发环境进行系统的设计和实现,其运行结果表明，系统能很好地完成遍历后节点的输出,实现了遍历的目的，系统界面友好,可操作性强。 关键词：数据结构;存储结构；邻接矩阵 数据结构实验报告 实验：图的遍历 一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理 二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列 三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。 四、程序实现及结果： 1、邻接矩阵： #include 《数据结构》 实 验 报 告 网络081 200800824126 甘春泉 实验五图的遍历及其应用实现 一、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。3．会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 三、实验步骤 ㈠、数据结构与核心算法的设计描述 依次输入顶点偶对，建立无向图邻接表 void CreatGraphAdList(ALGraph &G) // 依次输入顶点偶对，建立无向图 邻接表 { ArcNode *p; int i,j,k,m; cout<<"请输入无向图顶点的数目"< p=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个结点 p->adjvex=j; //为结点j的序号赋值 p->data=j; //假设结点数据域为整型，且以结点序号为其值 p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; //将结点j插入到第i个链表 p=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个结点 p->adjvex=i; p->data=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; //将结点i插入到第j个链表 // cin>>i>>j; //再次输入下一条边的两个顶点序号} } 从第v个顶点出发递归的深度优先遍历图 void DFS(ALGraph &G,int v,int flag[]) {//从第v个顶点出发递归的深度优先遍历图 ArcNode *p; int i; flag[v]=1; cout< 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 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 #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;i 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include ##大学 数据结构课程设计报告题目：图的遍历和生成树求解 院（系）：计算机工程学院 学生: 班级：学号: 起迄日期: 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 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { 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 数据结构【第六次】实验报告学院： 班级： 学号： 姓名： 实验六 （一）实验名称：图的实现及遍历 （二）实验目的： 1) 掌握有向图和无向图的概念； 2) 掌握邻接矩阵和邻接链表建立图的存储结构； 3) 掌握DFS及BFS对图的遍历操作和过程； 4) 了解图结构在人工智能、工程等领域的广泛应用。（三）实验要求： 1) 采用邻接矩阵作为图的存储结构，完成有向图和无向图的DFS和BFS操作； 2) 采用邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。 （四）源代码： 1）邻接矩阵作为存储结构的程序 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 typedef struct{ char vexs[MaxVertexNum]; int edges[MaxVertexNum][MaxVertexNum]; int 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;i 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 三、附录： 在此贴上调试好的程序。 #include #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;i 实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include 数 据 结 构 实 验 报 告（五）姓名: 学院：班级： 实验五图的遍历及其应用实现 一、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示： 输入示例 上图的顶点和边的信息输入数据为： 5 7 DG A B C D E AB AE BC CD DA DB EC 定义相关常量及类型 #define INFINITY INT_MAX //最大值无穷 #define MAX_VERTEX_NUM 20 //最大顶点数 bool visited[MAX_VERTEX_NUM]; //标记数组 typedef struct ArcCell //定义邻接矩阵{intadj;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct //图的结构定义{ char vexs[MAX_VERTEX_NUM]; //图中所有顶点的集合AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //定义图的顶点数和弧数 }MGraph; 一、相关函数声明： 1、/* 输入图的顶点和边的信息,建立有向图*/ void CreateDGGraph(MGraph &G,int a,int b) 2、/* 输入图的顶点和边的信息,建立无向图*/ void CreatUDGGraph(MGraph &G,int a,int b) 3、/*获取图中点a的位置*/ int locatevex(MGraph &G,char a) 4、/*返回G中顶点n(序号)的未曾访问过的第一个邻接点(序号)*/ int firstadjver(MGraph G,int n) 5、/*返回G中顶点n(序号)的除顶点m(序号)的未曾访问过的邻接点(序号)*/ int nextadjvex(MGraph G,int n,int m) 6、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G) void DFS(MGraph G,int i) 7、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G) 二、函数具体实现 1、/*获取图中点a的位置*/ int locatevex(MGraph &G,char a) { for(int i=0;i 一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点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 实验七图的创建与遍历 实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求： 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计： #include 图的遍历操作实验报告
图的遍历实现课程设计 数据结构 程序 图
实验五 图的存储与遍历
实验报告：图的存储结构和遍历
图的遍历实验报告
图的遍历实现课程设计-数据结构-程序-图
数据结构实验报告-图的遍历
图的基本操作-遍历的实现
数据结构实验---图的储存与遍历
数据结构实验报告图实验
数据结构课程设计之图的遍历和生成树求解
数据结构图的遍历实验报告
图的实现及遍历
数据结构实验 - 图的储存与遍历
图的基本操作 实验报告
实验_五____图的遍历及其应用实现
图的深度优先遍历实验报告
数据结构实验七图的创建与遍历