数据结构——图说课讲解.ppt

《数据结构——图说课讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——图图的定义及相关术语图的定义：图G由两个集合V(G)和E(G)所组成，记作G=(V, E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。(2)有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。有向图示例图中所示的G1为有向图，它由V(G1)和E(G1)组成。V(G1)={V1，V2，V3，V4}E(G1)={，，，}如其中弧，称V1为初始点或弧之尾，V2为终端点或弧之头。(3)无向图。如果图中每

2、条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。如图所示的G2为无向图。V(G2)={V1，V2，V3，V4}E(G2)={(V1,V2)，(V1,V3)，(V3,V4)，(V4,V1)}注意，在无向图中，(V1,V2)与(V2,V1)表示同一条边。图3-23无向图示例(4)子图。设有两个图GA和GB，且满足V(GB)V(GA)E(GB)E(GA)则称GB是GA的子图。如下图所示。图与子图(5)带权图。在图的边或弧上加上一个相关联的数(权)，称为带权图或网。如下图所示。ABECF1597211132有向网无向网(6)完全图。假设图中有n个顶点，e条

3、边，则含有e=n(n-1)/2条边的无向图称作完全图；含有e=n(n-1)条弧的有向图称作有向完全图。(7)稠密图与稀疏图。若图的边或弧的数目接近于相应完全图的边或弧的数目，则称之为稠密图，否则称为稀疏图。(8)路径。在一个图中，如果从顶点V1出发，沿着一些边经过顶点V1，V2，…，Vn-1到达顶点Vn，则称顶点序列(V1，V2，…，Vn-1，Vn)为从V1到Vn的一条路径。路径上边(弧)的数目称为该路径的长度。例如：下图中，{A,B,C,F}的路径长度为3。ABECF(9)简单路径：序列中顶点不重复出现的路径。(10)简单回路：序列中第一个顶点和最后一个顶点相同的简单路径。(1

4、1)连通图：在无向图中，若每一对顶点之间都有路径，则称此图为连通图。(12)连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。连通图BACDFEBACDFE非连通图(13)强连通图：在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。(14)强连通分量：各个强连通子图称作该有向图的强连通分量。强连通图ABECFABECF非强连通图(15)邻接点。在无向图中，如果边(u,v)∈E，则u和v互为邻结点，即u是v的邻结点，v也是u的邻结点。边(v,w)与顶点u和v相关联。在有向图中，如果弧∈E，则v是u的邻结点。称u邻接到v

5、，或顶点v邻接自顶点u。(16)顶点的度。在无向图中，顶点的度就是和该顶点相关联的边的数目，记为TD(V)。在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，记作ID(V)；以某顶点为弧尾的弧的数目称为此顶点的出度，记作OD(V)。该顶点的度则是此顶点的入度与出度之和。ACDFETD(B)=3，TD(A)=2BABECFID(B)=2，OD(B)=1TD(B)=ID(B)+OD(B)=3建立和销毁图结构插入或删除顶点对邻接点的操作访问顶点遍历图插入和删除弧基本操作5.2图的存储结构图的存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示*三、有向图的十字链表存储表

6、示*四、无向图的邻接多重表存储表示根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的顶点的集合；另一部分是顶点之间的联系，即边或弧的集合。可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有n(n≥1)个顶点的图，则G的邻接矩阵A是一个n×n阶矩阵。Aij={0若(Vi,Vj)或E(G)1若(Vi,Vj)或E(G)一、图的数组(邻接矩阵)存储表示定义:矩阵的元素为BADFEC010010100011

7、000101001001110000011100ABCDEFABCDEF有向图的邻接矩阵ABDCE0101000100000010010011000ABCDE在一般情况下，我们不关心图中顶点的情况，若将顶点编号为1～Vtxnum，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：intadjmatrix[Vtxnum][Vtxnum]；特点无向图的邻接矩阵是对称的;有向图的邻接矩阵不一定对称。对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。对于有向图