资源描述：
《考研数据结构chapt7》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第七章图图的定义图的存储结构图的遍历图的应用7.1图的定义和术语1.图有向图（Digragh）无向图（Undigraph）7.1图的定义和术语有向图（Digragh）G=（V，{A}）其中，V为顶点的有穷非空集合{A}为顶点之间的关系集合G1=（V，{A}）V={v1,v2,v3,v4}A={,,,}其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)①②③④G17.1图的定义和术语无向图（Undigraph）G=(V,{E})其中，V同有向图，{E}为顶点之间的关系集合，E为边集合G2=
2、（V，{A}）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x与y之间的一条连线，称为边（edge）①②G2③④⑤7.1图的定义和术语设n为顶点数，e为边或弧的条数对无向图有：0<=e<=n(n-1)/2有向图有：0<=e<=n(n-1)证明：每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但每条边连接2个顶点，故最多为n(n-1)/27.1图的定义和术语2.完全图边达到最大的图无向完全图：边数为n(n-1)/2的无向图有向完全图：弧数为n(n-
3、1)的有向图权：与图的边或弧相关的数网：边或弧上带有权值的图7.1图的定义和术语3.顶点的度TD（V）无向图：为依附于顶点V的边数有向图：等于以顶点V为弧头的弧数（称为V的入度，记为ID（V））与以顶点V为弧尾的弧数（称为V的出度，记为OD（V））之和。即：TD（V）=ID（V）+OD（V）无向图ne=1/2（∑TD(vi)）i=1结论：有向图nne=∑ID(vi)=∑OD(vi)i=1i=1无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v为弧头的弧数与以顶点v为弧尾的弧数之和7.1图的定义和术语4.路径无向图：顶点v到v’的路径是一个顶点序列（v=vi0,vi1,…,vim=v’
4、）其中，（vij-1,vij）∈E,1<=j<=m有向图：顶点v到v’的路径是有向的顶点序列（v=vi0,vi1,…,vim=v’）其中，（vij-1,vij）∈A,1<=j<=m几个概念：路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。即：（v=vi0,vi1,…,vim=v’=v）简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路7.1图的定义和术语5.连通顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的连通图：包括无向连通图和有向连通图无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vi<>vj)有向
5、图：若图中任意两个顶点vi,vj，都存在从vi到vj和从vj到vi的路径，则称该有向图为强连通图(vi<>vj)连通分量：无向图：无向图中极大连通子图，称为连通分量有向图：有向图中极大强连通子图，称为强连通分量7.1图的定义和术语5.连通连通分量：①②③④G1有两个强连通分量①②③④G17.1图的定义和术语6.生成树定义：设无向图G是含有n个顶点的连通图，则图G的生成树是含有n个顶点，且只有n-1条边的连通子图三要素：n个顶点n-1条边连通极小连通子图，若再加一条边，必构成环生成树n-1条边7.2图的存储结构图有数组、邻接表、邻接多重表和十字链表等表示方法一、数组表示法（邻接矩阵）设图G=（
6、V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。其中：A[i，j]=1若（vi，vj）或∈E，i≠j0其它例如：G1的邻接矩阵┌0110┐A1＝│0000││0001│1000①②G2③④⑤┌01010┐A2＝│10101││01011│1010001100无向图的邻接矩阵为对称矩阵①②③④G17.2图的存储结构特点：判定两个顶点Vi与Vj是否关联,只需判A[i,j]是否为1顶点的度容易求得:有向图中：TD(Vi)=OD(Vi)+ID(Vi)nn=∑A[i,j]+∑A[j,i]j=1j=1nn无向图中：TD(Vi)=∑A[i,j]=∑A[j,i]j=1j=1即顶点Vi的
7、度等于邻接矩阵中第i行（或第i列）的元素之和（非0元素个数之和）。即顶点Vi的出度为邻接矩阵中第i行元素之和顶点Vi的入度为邻接矩阵中第i列元素之和7.2图的存储结构网的邻接矩阵定义为：A[i，j]=Wij，若（Vi，Vj）或∈E，其它V1V2V3V435214┌324┐A＝│││51如图：7.2图的存储结构二、邻接表（adjacencylist）1.无向图邻接表对图中每个顶点Vi建立一个单链表
