图练习：
1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列
B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n
5．n个结点的完全有向图含有边的数目（）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。
A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A．1/2 B．2 C．1 D．4
8. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度
遍历是一个递归过程
9．无向图G=(V,E),其中：
V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图
进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
10. 关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）
3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=。（）
4. 有e条边的无向图，在邻接表中有e个结点。（）
5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）
6．强连通图的各顶点间均可达。（）
7．邻接多重表是无向图和有向图的链式存储结构。（）
8. 十字链表是无向图的一种存储结构。（）
9．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）10．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零
元素之和的一半。（）
11. 有向图的邻接矩阵是对称的。（）
12．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）
13. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）
14. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）
15. 广度遍历生成树描述了从起点到各顶点的最短路径。（）
16．任何无向图都存在生成树。（）
17. 不同的求最小生成树的方法最后得到的生成树是相同的.（）
18．带权无向图的最小生成树必是唯一的。（）
19. 最小代价生成树是唯一的。（）
20．一个网（带权图）都有唯一的最小生成树。（）
21．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）22．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（）23．带权的连通无向图的最小代价生成树是唯一的。（）
24. 最小生成树问题是构造连通网的最小代价生成树。（）
三、填空题
1.判断一个无向图是一棵树的条件是______。
2．有向图G的强连通分量是指______。
3．一个连通图的______是一个极小连通子图。
4．具有10个顶点的无向图，边的总数最多为______。
5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。
6. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______
7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
9．在有n个顶点的有向图中，每个顶点的度最大可达______。
10．设G为具有N个顶点的无向连通图，则G中至少有______条边。
11．n个顶点的连通无向图，其边的条数至少为______。
12．如果含n个顶点的图形形成一个环，则它有______棵生成树。
13．N个顶点的连通图的生成树含有______条边。
14．构造n个结点的强连通图，至少有______条弧。
15．有N个顶点的有向图，至少需要量______条弧
才能保证是连通的。
16．右图中的强连通分量的个数为（
17．N个顶点的连通图用邻接矩阵表示时,该矩阵
至少有_______个非零元素。
18．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说
等于该顶点的______；对于有向图来说等于该顶点的______。
19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。
20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为
______，邻接表的边结点个数为______。
21. 已知一无向图G=（V，E），其中V={a,b,c,d,e }
E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历
图，得到的序列为abecd，则采用的是______遍历方法。
答案：
1.有n个顶点，n-1条边的无向连通图
2.有向图的极大强连通子图
3. 生成树
4. 45
5. n(n-1)/2 6 .
7. 9 8. n
9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n
15. N
16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e
22. 深度优先 23.宽度优先遍历
四、应用题
1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？
（2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？
（3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？
2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？3．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
4．给出图G：
（1）．画出G的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。5．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有
哪些？
6．考虑下图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，求它的最小生成树从A点开始
（4）根据kruskal 算法，求它的最小生成树
7．考虑下图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，求它的最小生成树从1点开始
（4）根据kruskal 算法，求它的最小生成树
3
6 7
5 8
9
4
2
1
3
10
5 7
8
4
2
1
6
9
答案：
1．（1）G1最多n(n-1)/2条边，最少n-1条边
(2) G2最多n(n-1)条边，最少n条边
(3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的)
2．n-1，n
3．深度优先遍历序列：125967384
宽度优先遍历序列：123456789
注：（1）邻接表不唯一，这里顶点的邻接点按升序排列
（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一
（3）这里的遍历，均从顶点1开始
4.略
5.遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
6．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列
(1)ABGFDEC (2)EACFBDG
7.略
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 数据结构C语言版无向图的邻接多重表存储表示和实现.txt只要你要，只要我有，你还外边转什么阿老实在我身边待着就行了。听我的就是,问那么多干嘛，我在你身边,你还走错路!跟着我!不能给你幸福是我的错，但谁让你不幸福，我TMD去砍了他/* 数据结构C语言版无向图的邻接多重表存储表示和实现 P166 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月15日 */ #include 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 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------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号（0--3）： */ #include 邻接矩阵的实现 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 《数据结构》实验报告 1 2 实验题目：第四次实验《无向图的应用》 3 姓名：刘创学号：132054137 班级：1320541 4 系名：计算机工程系专业：计算机科学与技术5 指导老师：刘海静 6 实验时间：2015年6月18日星期四实验地点：软件实验室 【实验概述】 1.实验目的及要求 目的：掌握图的有关知识 要求：用图的邻接表存储无向图； 实现图的遍历等操作 2.实验原理 图的遍历 图的存储 3.实验环境（使用的软件） VC++6.0/VS2013 【实验内容】 1.实验算法设计 实验：存储图使用图的邻接表进行存储； 用深度优先排序进行遍历图 2.实验过程（源代码及描述、调试过程及分析） 调试过程中，两个实验没有出现太大的问题，理论联系实际，多时间去实践方可等心应手。 实验代码: GraphTraverse.cpp #include #define MaxVertexNum 40 //最大顶点数 using namespace std; typedef struct node //表结点 { int adjvertex; //邻接点域 InfoType info; //与边相关信息（权值） struct node *next; //指向下一个领节点的指针域 }EdgeNode; typedef struct vnode { VertexType vertex; //顶点域信息 EdgeNode *firstedge; //边表头指针 }VertexNode; typedef struct { VertexNode adjlist[MaxVertexNum];//邻接表 int vertexNum, edgeNum;//顶点数和边数 }ALGraph; //以邻接表存储的图 int visited[MaxVertexNum]; int e; void CreatAdjList(ALGraph* G) //创建无向图（邻接表） { int i, j, k; EdgeNode * p1; //因为是无向图，所以有两次建立边表的过程EdgeNode * p2; EdgeNode * p3; EdgeNode * p4; cout << "请输入无向图的顶点数和边数:"; 第4章 1．简述需求分析中现行系统调查、新系统逻辑方案的提出等活动的详细内容、关键问题、主要成果及其描述方法。 系统调查 (1)组织机构的调查 了解组织的机构状况。即各部门的划分及其相互关系、人员配备、业务分工、信息流和物流的关系等等。组织机构状况可以通过组织结构图来反映。所谓组织机构图就是把组织分成若干部分，同时标明行政隶属关系，信息流动关系和其他关系。 (2)业务处理状况调查 为了弄清楚各部门的信息处理工作，哪些与系统建设有关，哪些无关，就必须了解组织的业务流程。系统分析人员应按照业务活动中信息流动过程，逐个调查所有环节的处理业务、处理内容、处理顺序和对处理时间的要求，弄清楚各个环节需要的信息内容、信息来源、去向、处理方法、提供信息的时间和信息形态等。 (3)现行系统的目标、主要功能和用户需求调查 只有充分了解现行系统的目标和功能以及用户需求，才能发现存在的问题，寻找解决问题的途径，也使新系统开发成为可能。 (4)信息流程调查 开发信息系统必须了解信息流程。业务流程虽然在一定程度上表达了信息的流动和存储情况，但仍含有物资、材料等内容。为了用计算机对组织的信息进行控制，必须舍去其他内容，把信息的流动、加工、存储等过程流抽象出来，得出组织中信息流的综合情况。描述这种情况的就是数据流图。 (5)数据及功能分析 有了数据流图后，要对图中所出现的数据和信息的属性进一步分析，包括编制数据词典、数据存储情况分析及使用情况分析。同时还要对数据流图中的各个加工逻辑进行描述。可用的工具有决策树、决策表、结构化语言等。 (6)系统运营环境分析 目前我国许多企业组织的信息系统处于停滞状态的主要原因是系统对环境环境的适 应性而非技术问题。因此，必须对系统的应用环境进行认真地调查分析，充分考虑各种可能发生的变化，以提高系统开发的质量。 新系统逻辑方案的提出 (1) 现行系统的薄弱环节 (2) 新系统的总体功能需求 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q } 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main() 重庆科技学院 课程设计报告 院（系）:_电气与信息工程学院专业班级:计科普0902 设计地点（单位）____计算机基础自主学习中心I306___设计题目:_________校园导游咨询____________________ 重庆科技学院 课程设计任务书设计题目：校园导游咨询 教研室主任：指导教师：向毅、陈刘奎、熊茜 2010年 12 月 20日 摘要 现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。 本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。 关键词：无向图、查找信息、最短距离、校园导游咨询 目录 摘要.................................................................................................................................................. II 1 设计内容和要求 (1) 1.1设计内容 (1) 1.1设计要求 (1) 2 概要设计 (2) 2.1 程序的模块图 (2) 2.2 主函数的概要设计 (3) 2.3 查找介绍函数的概要设计 (3) 2.4 查找最短路径函数的概要设计 (3) 2.5 退出函数的概要设计 (3) 3 详细设计 (4) 3.1 程序的流程图 (4) 3.2 主函数的详细设计 (5) 3.3 查找介绍函数的详细设计 (5) 3.4 查找最短路径函数的详细设计 (6) 3.5 退出函数的详细设计 (8) 3.6 数据结构的详细设计 (8) 4 软件测试 (10) 4.1 菜单的测试 (10) 4.2 查找景点简介的测试 (10) 4.3 查找两个景点之间的最短距离的测试 (11) 4.4 退出的测试 (11) 5 软件使用说明 (12) 6 致谢 (13) 7 参考文献 (14) 8 附录 (15) 数据结构教案第七章图 第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 精品文档数据结构 实 验 报 告 目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include 实验7 无向图 一、问题描述 创建一个无向图，实现图的深度优先遍历和广度优先遍历等功能。 二、需求分析 1、简述程序的基本功能 本程序可以直接进行对图中元素的输入、输出、插入顶点、删除顶点、插入边、删除边、寻找邻接点以及深度优先遍历和广度优先遍历等功能。 2、输入的形式和输入值的范围 提供了一个功能选择界面，可以输入0~9进行功能的选择。 3、输出的形式 用户选择1选项时，程序会输出图的顶点数目和边的数目以及各条边顶点及权值； 用户选择2选项时，程序会提示输入创建图的顶点数和边数，然后逐个输入顶点，以及各条边； 用户选择3选项时，程序会提示输入顶点，然后输出该顶点的第一个邻接顶点； 用户选择4选项时，程序会提示输入顶点以及当前的邻接顶点，然后输出该顶点的下一个邻接顶点； 用户选择5选项时，程序会提示输入所要插入边的顶点以及权重； 用户选择6选项时，程序会提示输入所要插入的顶点； 用户选择7选项时，程序会提示输入所要删除的边的两个顶点； 用户选择8选项时，程序会提示输入所要删除的顶点 用户选择9选项时，程序提示输入遍历的起始顶点，然后输出深度遍历的结果； 用户选择0选项时，程序提示输入遍历的起始顶点，然后输出广度遍历的结果； 用户选择q选项时，程序结束。 4、测试数据要求 1）、选择选项时，不论输入几个字符，只读取第一个字符； 2）、选择选项时，输入的字符不能过多，若输入过多的字符就会出现异常； 3）、输入顶点时，每个元素只能是一个字符，输入多个字符会出错； 4）、在查找、插入、删除顶点或边时，会有容错提示； 5）、在查找和删除顶点或边时，若没有此元素，会给出提示； 三、概要设计 1、抽象数据类型 在该程序中，定义了一个类模板template class Graph，在该类中有*Vertices、**Edge、numEdges、numVertices 和maxVertices五个私有成员分别表示该类的顶点集、边集、现有边数、现有顶点数和顶点最大数目；自 图的实验报告 班级：电子091 学号：0908140620 姓名：何洁编号：19 （一）实验要求 创建一个图。能够实现图的输入，插入顶点和边，利用队列进行深度和广度遍历。（二）需求分析 功能：1，输入图的信息；2，插入一个顶点；3插入一个边；4，删除一个顶点；5，删除一个边；6，深度优先遍历；7，广度优先遍历；8退出。 （三）概要设计 本程序采用的是模板类，抽象数据类型有：T,E。 类： template 数据结构实验十一：图实验
数据结构C语言版 无向图的邻接多重表存储表示和实现
数据结构图习题
数据结构实验---图的储存与遍历
数据结构：图子系统
数据结构实验报告图实验
数据结构实验四：无向图的应用
数据流图的构成与绘制步骤
数据结构实验
数据结构 第六章 图 练习题及答案详细解析
数据结构实验报告图实验
数据结构图实验报告
数据结构实验报告无向图
基于无向图的校园导游系统数据结构课程设计报告
(完整版)数据结构详细教案——图
数据结构实验—图实验报告
数据结构图的实现
数据结构--图的实验报告
相关主题
文本预览