第六章图.ppt

第6章 图 本章中介绍下列主要内容： 图的定义 图的存储结构 图的遍历操作 图的几个典型问题 6.1 图的基本概念 6.2 图的存储结构 6.3 图的遍历 6.4 图的应用 6.1 图的定义 6.1.1 定义 图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 图 6-1 2．图的相关术语 （1）无向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。如图6.1(b)所示是一个无向图。 （2）有向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。如图6.1(a)所示是一个有向图 (3)顶点、边、弧、弧头、弧尾：图中，数据元素vi称为顶点(vertex )；P(vi, vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对（vi, vj）来表示，称顶点vi和顶点vj互为邻接点，边（vi, vj）依附于顶点vi与顶点vj；弧用顶点的有序偶对vi, vj来表示，有序偶对的第一个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧头），在图中就是带箭头的一端。 （4）无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 （5）有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。 （6）顶点的度、入度、出度：顶点的度（degree）是指依附于某顶点v的边数，通常记为TD (v)。在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点v为终点的弧的数目。记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD (v)。有TD (v)=ID (v)＋OD (v)。 （7）边的权、网：与边有关的数据信息称为权（weight）。在实际应用中，权值可以有某种含义。 边上带权的图称为网或网络（network）。 （8）路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2, …, vim,vq.。其中，（vp,vi1），(vi1,vi2)，…,(vim,.vq)分别为图中的边。路径上边的数目称为路径长度。 （9）回路、简单路径、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的路径称为回路或者环（cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。 网图举例 举例 非连通图 无向图及其三个连通分量 6.1.2 图的基本操作 （1） CreatGraph（G）输入图G的顶点和边，建立图G的存储。 （2）DestroyGraph（G）释放图G占用的存储空间。 （3）GetVex（G，v）在图G中找到顶点v，并返回顶点v的相关信息。 （4）PutVex（G，v，value）在图G中找到顶点v，并将value值赋给顶点v。 （5）InsertVex（G，v）在图G中增添新顶点v。 （6）DeleteVex（G，v）在图G中，删除顶点v以及所有和顶点v相关联的边或弧。 （7）InsertArc（G，v，w）在图G中增添一条从顶点v到顶点w的边或弧。 （8）DeleteArc（G，v，w）在图G中删除一条从顶点v到顶点w的边或弧。 （9）DFSTraverse（G，v）在图G中，从顶点v出发深度优先遍历图G。 （10）BFSTtaverse（G，v）在图G中，从顶点v出发广度优先遍历图G。 6.2 图的存储结构 6.2.1 邻接矩阵 1. 有向图的邻接矩阵 具有n个顶点的有向图可以用一个n?n的方形矩阵表示。假设该矩阵的名称为M，则当vi,vj是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中“1”的个数；入度为第i列中“1”的个数，并且有向图弧的条数等于矩阵中“1”的个数。 图 6-4 1．2 无向图的邻接矩阵 具有n个顶点的无向图也可以用一个n?n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]