实验五 图的基本操作
一、实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容
[问题描述]
对给定图,实现图的深度优先遍历和广度优先遍历。
[基本要求]
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。
【测试数据】
由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作
1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果,对程序进行分析。
编程思路:
深度优先算法:计算机程序的一种编制原理,就是在一个问题出现多种可以实现的方法和技术的时候,应该优先选择哪个更合适的,也是一种普遍的逻辑思想,此种思想在运算的过程中,用到计算机程序的一种递归的思想。
度优先搜索算法:又称广度优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话 说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。
…… …… 余下全文
数据结构实验报告
实验:图的遍历
一、实验目的:
1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表
2、掌握图的构造方法
3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法
4、掌握图的深度优先遍历和广度优先原理
二、实验内容:
1、输入顶点数、边数、每个顶点的值以及每一条边的信息,构造一个无向图G,并用邻接矩阵存储改图。
2、输入顶点数、边数、每个顶点的值以及每一条边的信息,构造一个无向图G,并用邻接表存储该图
3、深度优先遍历第一步中构造的图G,输出得到的节点序列
4、广度优先遍历第一部中构造的图G,输出得到的节点序列
三、实验要求:
1、无向图中的相关信息要从终端以正确的方式输入;
2、具体的输入和输出格式不限;
3、算法要具有较好的健壮性,对错误操作要做适当处理;
4、程序算法作简短的文字注释。
四、程序实现及结果:
1、邻接矩阵:
#include <stdio.h>
#include <malloc.h>
#define VERTEX_MAX 30
#define MAXSIZE 20
…… …… 余下全文
实验五 图的存储与遍历
1、实验目的
掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示,以及在此两种常用存储方式下深度优先遍历(dfs)和广度优先遍历(BFS)操作的实现。
2、实验预备知识
(1)图的存储结构:邻接矩阵表示法和邻接表表示法。邻接矩阵表示法除了要用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组来存储顶点信息,另外还有图的顶点数和边数。邻接表表示法类似于树的孩子链表表示法。
(2)图的遍历方法有深度优先遍历(Depth-First Traersal)和广度优先遍历(Breadth-First Traversal),简称 DFS和BFS。DFS对图遍历时尽可能先对纵深方向进行搜索;BFS是类似于树的按层次遍历。
3、实验内容
题目1 对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历
(1) 问题描述:以邻接矩阵为图的存储结构,实现图的DFS和BFS遍历。
(2) 基本要求:建立一个图的邻接矩阵表示,输出顶点的一种DFS和BFS序列。
(3) 测试数据:如图4.18所示。
(4) 实现提示:图的DFS遍历可通过递归调用或用栈来实现。其思想是:只要当前结点未访问过,就访问该结点,沿着其一条分支深入下去,每深入一个未访问过的结点,就访问这个结点,然后从这个结点继续进行DFS遍历。在这一过程中,若深入时遇到一个已访问过的结点,则查找是否有与这个结点相邻的下一个未访问过的结点。若有则继续深人,否则将退回到这个结点的前一个结点,再找下一个相邻的本访问过的结点,……如此进行下去,直到所有的结点都被访问过。BFS遍历可利用队列来帮助实现,也可以用栈。实现方法与二叉树的层次遍历类似。
…… …… 余下全文
实验 五 图的遍历及其应用实现
一、实验目的
1.熟悉图常用的存储结构。
2.掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。
3.会用图的遍历解决简单的实际问题。
二、需求分析
很多问题都是建立在图的遍历的基础上实现的,所以必须有一个程序能够实现将图进行广度和深度遍历,必须对图的所有节点进行访问。
以无向图为例,以无向图的邻接表和邻接矩阵为存储结构,分别实现对图进行广度和深度遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应的生成树的边集。
三、实验内容
[题目一] :从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。
提示:
输入示例
上图的顶点和边的信息输入数据为:
5 7 DG
…… …… 余下全文
完成日期:2011.12.22
1.本演示程序中,输入的数据类型均为整型数据,不允许输入字符等其他数据类型,且需要按照提示内容进行输入,成对的关系数据必须在所建立的图中已经存在对应的结点。
2.演示程序以用户和计算机的对话方式执行,在计算机终端上显示的提示信息的说明下,按照要求输入数据,运算结果在其后显示。
3.本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图,有、无向网的建立和遍历。遍历分DFS和BFS两种算法,并分别以递归和非递归形式实现。
4.测试数据:
(1)无向图 结点数 4 弧数 3 结点:1 2 3 4 结点关系:1 2;1 3;2 4
(2)有向图 结点数 6 弧数 6 结点:1 2 3 4 5 6 结点关系:1 2;1 3;2 4;3 5;3 6;2 5
为实现上述程序功能,图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。
1.邻接矩阵存储结构的图定义:
ADT mgraph{
数据对象V:V是具有相同特性的的数据元素的集合,成为顶点集。
…… …… 余下全文
实现图的遍历算法
1. 需求分析
对于下图G,编写一个程序输出从顶点0开始的深度优先遍历序列(非递归算法)和广度优先遍历序列(非递归算法)。
2. 系统设计
1.用到的抽象数据类型的定义
图的抽象数据类型定义:
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集
数据关系R:
R={VR}
VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧,
谓词P(v,w)定义了弧<v,w>的意义或信息}
基本操作P:
CreatGraph(&G,V,VR)
初始条件:V是图的顶点集,VR是图中弧的集合
操作结果:按V和VR的定义构造图G
DestroyGraph(&G)
初始条件:图G存在
操作结果:销毁图G
InsertVex(&G,v)
初始条件:图G存在,v和图中顶点有相同特征
…… …… 余下全文
数据结构集中上机
试验报告
学院: 计算机科学与技术 专业:计算机科学与技术
学号:00000000 班级:(6) 姓名:
题目:图的创建与遍历
一.需求分析
很多问题都是建立在图的遍历的基础上实现的,所以必须有一个程序能够实现将图进行广度和深度遍历,必须对图的所有节点进行访问。
以无向图为例,以无向图的邻接表和邻接矩阵为存储结构,分别实现对图进行广度和深度遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应的生成树的边集。
二、源程序
图的邻接矩阵表示:
#include<iostream>
#include<queue>
using namespace std;
#define MAX_VEX_NUM 20//最大顶点数
queue<int>q;
struct MGraph
{
char vexs[MAX_VEX_NUM];//顶点向量// AdjMatrix
int arcs[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵
…… …… 余下全文