数据结构（c语言描述） 教学课件 作者 库波 第7章 图.ppt

数据结构(C#)主编: (Graph)是一种较为复杂的数据结构,是一种图状结构,比线性表和数更为复杂的数据结构。在图中,任何结点都可以相互建立联系,可以任意连接,图中的任意两个结点之间都有可能相关。近年来信息社会飞速发展,图的应用更为广泛,已渗透到逻辑学、物理、化学、语言学、计算机科学、人文科学和自然科学中,以及数学中。(Graph)是由非空的顶点(Vertices)集合和描述顶点之间的关系——边(Edge)或弧(Arc)的集合组成。其形式化定义为:G=(V,E)V={Vi|Vi∈dataobject}E={(Vi,Vj)|Vi,Vj∈V∧P(Vi,Vj)}图的定义(1)无向图(2)有向图(3)顶点、边、弧、弧头、弧尾(4)无向完全图、有向完全图(5)顶点的度、入度、出度(6)边的权、网图(7)路径、路径长度(8)简单路径、回路、简单回路(9)子图(10)连通图、连通分量(11)强连通图、强连通分量(12)生成树(13)生成森林图的相关术语图的基本操作图和其他的数据结构一样,它的基本操作包括查找、插入和删除。图的基本操作说明:1)GetNumOfVertex()如果图存在;则返回图中的顶点数。2)GetNumOfEdge()如果图存在;则返回图中的边或弧的数目。基本定义和术语3)SetEdge(Node<T>V1,Node<T>V2,intv)如果图存在,顶点V1和V2是图的两个顶点;那么在顶点V1和V2之间添加一条边或弧并设边或弧的值为v。4)DelEdge(Node<T>V1,Node<T>V2)如果图存在,顶点V1和V2是图的两个顶点并且V1和V2之间有一条边或弧;则删除顶点V1和V2之间的边或弧。5)IsEdge(Node<T>V1,Node<T>V2)如果图存在,顶点V1和V2是图的两个顶点;如果V1和V2之间有一条边或弧,返回true,否则返回false。基本定义和术语例:在无向图G1和有向图G2中找出各个顶点的入度和出度。基本定义和术语例:如下图所示无向网图,查看各条边的特点和权值。,任意两个顶点之间都有可能存在联系,所以没有办法用数据元素在存储区中的物理位置来表示元素与元素之间的关系,但是,可以借助元素与元素相邻接的关系来表示元素之间的关系。下面将介绍两种常用的表示方法,对无向图和有向图都有效,它们是邻接矩阵和邻接表表示法。