严蔚敏数据结构讲义(第07章 图)

《严蔚敏数据结构讲义(第07章 图)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第07章图7.1图的定义一、图的定义与相关术语G=(V，E)——Graph=(Vertex，edge)（一）图的分类1.无向图(undirectedgraph)(a,b)——a可达b，b也可达a；无向图中的顶点之间的连线称之为无向边或边。2.有向图(directedgraph)——a可达b，b不可达a；有向图中顶点之间的带有方向性的连线称之为弧。a为弧尾，b为弧头。3.完全无向图具有n个顶点的无向图，边的数目达到最大值，则此无向图称之为完全无向图。——即图中任意两个顶点都有连线，都可互

2、达。4.完全有向图具有n个顶点的有向图，边的数目达到最大值，则此有向图称之为完全有向图。——即图中任意两个顶点都可互达。5.稀疏图(sparegraph)在一个图G中，G的边或弧很少()6.稠密图(densegraph)在一个图G中，G的边或弧很多()7.边或弧的权(weight)在图的边或弧上添加的一些具有特定意义的数称之为权。8.网边或弧上带有权值的图称之为网。（二）边和顶点的关系1.无向图中：若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(adjacent)；或称vi和vj相邻

3、接；并称边(vi,vj)依附于顶点vi和vj或关联于顶点vi和vj；或称边(vi,vj)与顶点vi和vj相关联。2.有向图中：若是一条有向边，则称顶点vi邻接到vj或vj邻接于vi；并称边关联于顶点vi和vj或称边与顶点vi和vj相关联。3.顶点的度(degree)（1）无向图中顶点的度：顶点v的度是关联于该顶点的边的数目。（2）有向图中顶点的入度(indegree)：有向图G中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。（3）有向图中顶点的

4、出度(outdegree)：有向图G中，以顶点v为始点的边的数目称为v的出度，记为OD(v)。（4）有向图中顶点的度：有向图G中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。4.顶点数n、边数e和度数之间的关系15——无向图、有向图都适用——有向图适用1.路径路径是一个顶点序列v1,v2,…,vn，使得(vi,vi+1)(1。对于有向图，其路径是有向的。2.路径的长度：路径上边的数目。3.简单路径在路径中，如果路径上的每一个顶点均不相同，则称这条路径为简单路径。4

5、.环如果一条路径的第一个顶点和最后一个顶点相同，则称这条路径为环。5.自环特殊情况下，一个顶点到其自身可以看成是一条路径，称为自环。（一）子图1.连通：在无向图中，若顶点vi和vj之间有路径，则称vi和vj是连通的。2.连通图(Connectedgraph)：在无向图中，若任意两个不同顶点都连通，则称该图为连通图。3.连通分量(Connectedcomponent)：无向图G的极大连通子图称为G的连通分量。4.强连通图：在有向图中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj

6、以及vj到vi的路径，则称G是强连通图。5.强连通分量：有向图中的极大强连通子图称为G的强连通分量。（二）最小生成树1.最小生成树的定义：一个连通图的最小生成树是一极小连通图，包含图中的全部顶点。但只有足以构成一棵树的n-1条边。2.最小生成树的特点：（1）一棵有n个顶点的生成树有且仅有n-1条边；（2）如果一个图有n个顶点和小于n-1条边，则它是非连通图；（3）如果一个图有n个顶点和大于n-1条边，则它一定有环；（4）有n-1条边的图不一定是生成树。3.有向树：如果一个有向图恰有一个顶点的入度

7、为0，其余顶点的入度均为1，则它是一棵有向树。4.有向图的生成森林：一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。一、图的抽象数据类型157.1图的存储方式一、数组表示法——又称为邻接矩阵表示法，顺序存储结构（一）无向图的邻接矩阵表示1.无向图的邻接矩阵是对称的；可压缩存储；有n个顶点的无向图需存储空间为——保存对角线和对角线以上(或以下)的元素。2．顶点i的度＝第i行(或列)中1的个数；3.完全图的邻接矩阵中，对角元素为0，其余全1。（二）有

8、向图的邻接矩阵表示1.在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。2.有向图的邻接矩阵可能是不对称的。有n个顶点的有向图需存储空间为n2。3.顶点vi的出度=第i行元素之和(即非零元素个数)：OD(vi)=ΣA[i][j]顶点vi的入度=第i列元素之和(即非零元素个数)：ID(vi)=ΣA[j][i]顶点的度=第i行元素之和+第i列元素之和,即：TD(vi)=OD(vi)+ID(vi)（三）有权图（即网络）的邻接矩阵表示与有向图的