数据构造实验报告(图).docx

数据构造实验报告(图)实验报告课程：数据构造c语言实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期：12月13号12月20号专业班级：媒体161组别：无姓名：学号：实验报告内容验证性实验一、预习准备：实验目的：1、熟练把握图的构造特性，熟悉图的各种存储构造的特点及适用范围；2、熟练把握几种常见图的遍历方法及遍历算法；实验环境：Widows操作系统、VC6.0实验原理：1.定义：基本定义和术语图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(Vertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，v0,v2)或有序对即：有方向的,。邻接矩阵表示顶点间相联关系的矩阵设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有下面性质的n阶方阵特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边有向图中指以Vi为尾的弧特点:无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。图的遍历从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次经过.。遍历图的经过本质上是通过边或弧对每个顶点查找其邻接点的经过，其消耗的时间取决于所采用的存储构造。图的遍历有两条途径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储构造时，查找每个顶点的邻接点所需要时间为On2，n为图中顶点数；而当以邻接表作图的存储构造时，找邻接点所需时间为Oe，e为无向图中边的数或有向图中弧的数。实验内容和要求：选用任一种图的存储构造，建立如下列图所示的带权有向图：要求：12、依次将图的边以及相应的权值插入，建立如上图所示的图，并将结点集合和权值集合输出；3、对所建立的图进行深度优先搜索或广度优先搜索，输出图的遍历序列；