第讲：图及其应用.ppt

《第讲：图及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第15讲:数据结构之图一、图的基本概念二、图的存储结构三、图的遍历四、无向图的传递闭包五、最短路径六、最小生成树七、拓扑排序1、图的的定义图是由顶点V的集合和边E的集合组成的二元组：记G=（V，E）存在一个结点v，可能含有多个前驱结点和后继结点。一、图的基本概念1253412534无向图：在图G=（V，E）中，如果对于任意的顶点a，b∈V，当(a，b)∈E时，必有（b，a）∈E（即关系R对称），此图称为无向图。无向图中用不带箭头的边表示顶点的关系V={1,2,3,4,5}E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)}125342、无向图和有向图有向图

2、：如果对于任意的顶点a，b∈V，当(a，b)∈E时，(b，a)∈E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。V={1,2,3,4,5}E={<1,2>,<1,4>,<2,3>,<2,5>,<3,1>,<5,3>,<5,4>}12534在无向图中：顶点v的度是指与顶点v相连的边的数目。D(2)=33、顶点的度、入度和出度在有向图中：入度——以该顶点为终点的边的数目和.ID(3)=2出度——以该顶点为起点的边的数目和.OD(3)=1度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。度：等于该顶点的入度与出度之和。D(5)=ID(5)+OD(5)=1+2=312

3、53412534图中所有顶点的度=边的两倍图1图2完全图4、路径、简单路径、回路在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1……xk(k>1)⑴x1=a，xk=b⑵(xi，xi+1)∈Ei=1‥k-1则称结点序列x1=a，x2，…，xk=b为结点a到结点b的一条路径，而路径上边的数目（k-1）称为该路径的长度。1253412534图1图2图1:1、(1,2,3,5)长度=32、(1,2,3,5,2)长度=43、(1,2,5,4,1)长度=4图2:(1,2,5,4)长度=3（1）、如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简

4、单路径。（2）、x1=xk的简单路径称为回路（也称为环）5、连通、连通图、连通分量(无向图)直观理解：连通：“连成一片”。连通图：“能连成一片的图”。1253412534678图一图二确切定义：连通：如果从顶点u到v有路径，则称u和v是连通的。连通图：图中任意的两个顶点u和v都是连通的。图一是连通图，图二是非连通图连通分量：无向图中的极大连通子图。图二中有3个连通分量：{1245}{36}{78}求连通分量数，最大连通分量等。有向图：强连通、强连通图、强连通分量6、带权图图中的边可以加上表示某种含义的数值，数值称为边的权，此图称为带权图。也称为网。一般的图边上没有数字，边仅表示两个顶点的相连接

5、关系。125342342132二、图的存储结构1、邻接矩阵（静态数组）2、邻接表（指针数组）3、边集数组4、十字链表5、邻接多重表图的邻接矩阵表示法邻接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的邻接矩阵是如下定义的二维数组a。1、邻接矩阵a[i,j]=1(或权值)：无向图：有边(i,j)和边(j,i)有向图：有边0:i到j无边1253401110101011100110001011101234512345125342342132022302010321002300040324012345123451253401010

6、001011000000000001101234512345对角线为0：自身不相连。无向图：是对称矩阵。有向图一般不是。第i行非0的个数是结点i的度具体到题目时，数据的给出格式多种多样：1）、直接给出邻接矩阵，直接读即可。如：输入文件内容：50223020103210023000403240Maxn=100A:array[1..maxn,1..maxn]ofintegerFillchar(a,sizeof(a),0);Readln(n);Fori:=1tondoforj:=1tondoread(a[I,j]);1253423421322）、给出边的顶点。如输入文件：

7、两个顶点及权值57122132143231253352454125342342132Readln(n);readln(m);Fork:=1tomdobeginreadln(I,j,x);a[I,j]:=x;a[j,i]:=x;end2、邻接表:方法112534234213212345223243^123153^122152^1354233244^头指针邻接点指针结点邻接点指针邻接点