资源描述：
《最新图的定义【共享精品-】PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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图的定义和术语3.顶点的度TD（V）无向图：为依附于顶点V的边数有向图：等于以顶点V为弧头的弧数（称为V的入
2、度，记为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’）其中，（vij-1,vij）∈E,1<=j<=m有向图：顶点v到v’的路径是有向的顶点序列（v=vi0,vi1,…,vim=v’）其中，
3、（vij-1,vij）∈A,1<=j<=m几个概念：路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。即：（v=vi0,vi1,…,vim=v’=v）简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路7.1图的定义和术语5.连通顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的连通图：包括无向连通图和有向连通图无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vi<>vj)有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从vj到vi的路径，则称该有向图为强连通图(vi
4、<>vj)连通分量：无向图：无向图中极大连通子图，称为连通分量有向图：有向图中极大强连通子图，称为强连通分量7.1图的定义和术语5.连通连通分量：①②③④G1有两个强连通分量①②③④G17.1图的定义和术语6.生成树定义：设无向图G是含有n个顶点的连通图，则图G的生成树是含有n个顶点，且只有n-1条边的连通子图三要素：n个顶点n-1条边连通极小连通子图，若再加一条边，必构成环生成树n-1条边7.2图的存储结构图有数组、邻接表、邻接多重表和十字链表等表示方法一、数组表示法（邻接矩阵）设图G=（V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。其中：A[
5、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的度等于邻接矩阵中第i行（或第i
6、列）的元素之和（非0元素个数之和）。即顶点Vi的出度为邻接矩阵中第i行元素之和顶点Vi的入度为邻接矩阵中第i列元素之和7.2图的存储结构网的邻接矩阵定义为：A[i，j]=Wij，若（Vi，Vj）或∈E，其它V1V2V3V435214┌324┐A＝│││51如图：7.2图的存储结构二、邻接表（adjacencylist）1.无向图邻接表对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域：adjvexnextarc其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息；链域（nextarc）指向下一个与
7、顶点Vi邻接的邻接的链表p结点每个链表附设一个头结点，头结点结构为：vexdatafirstarc其中：vexdata存放顶点信息（姓名、编号等）；fristarc指向链表的第一个结点。7.2图的存储结构二、邻接表（adjacencylist）如图G2的邻接表为：2534154353341221212345特点：设无向图中顶点数为n，边数为e，则它的邻接表需要n个头结点和2e个表结点。顶点Vi的度TD（Vi）=链表i中的表结点数。①②G2③④⑤7.2图的存储结构二、邻接表（adjacencylist）2.有向图邻接表与无向图的邻接表结构一样。只是在第i条链
8、表上的结点是以Vi为弧尾的各个弧头顶点234143121234特点
