资源描述：
《数据结构 第6章 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、6.1图的基本概念6.2图的存储结构6.3图的遍历第6章图16.1图的基本术语其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。有向图：无向图：完全图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge图：记为G＝(V,E)？v1v2v3v5v4v4v1v2v3v42例：判断下列4种图形各属什么类型？无向无向图(树)
2、有向图有向n(n-1)/2条边n(n-1)条边G1的顶点集合为V(G1)={0,1,2,3}边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图3稀疏图： 稠密图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。子图：边较少的图。通常边数远少于nlogn边很多的图。无向图中，边数接近n(n-1)/2有向图中，边数接近n(n-1)4带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与
3、v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。→带权图在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。强连通图：网络：DEABCFJLMGHIK非强连通图的极大强连通子图叫做强连通分量。5邻接点：有向边(u,v)称为弧，边的始点u叫弧尾，终点v叫弧头。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。若(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。弧头和弧尾：入度和出度：问：当有向图中仅1个顶点的
4、入度为0,其余顶点的入度均为1，此时是何形状？uv度：顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。U的入度=?U的出度=?答：是树！而且是一棵有向树！66.2图的存储结构图的特点：链式存储结构：顺序存储结构：难！（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）可用多重链表邻接矩阵(数组)表示法邻接表(链式)表示法但可用数组描述元素间关系。非线性结构（m:n）邻接矩阵邻接表各种表示法成立的原则：存入电脑后能惟一复原7①建立一个顶点表和一个邻接矩阵。1.邻接矩阵（数组）表示法例1：邻接矩阵：A.Edge=（v1v2v3v4
5、v5）v1v2v3v4v50101010101010111010101110分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。顶点表：无向图的邻接矩阵如何表示？v1v2v3v5v4v4A记录各个顶点信息表示各个顶点之间关系②设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：000000000000000000000000001010101010101110101011108例2：有向图的邻接矩阵如何表示？分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点v
6、i的出度=第i行元素之和，OD(vi)=A.Edge[i][j]顶点vi的入度=第i列元素之和。ID(vi)=A.Edge[j][i]顶点的度=第i行元素之和+第i列元素之和,即：TD(vi)=OD(vi)+ID(vi)v1v2v3v4A邻接矩阵：A.Edge=(v1v2v3v4)v1v2v3v40000000000000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：011000000001100001100000000110009容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧
7、）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。例3：有权图（即网络）的邻接矩阵如何表示？定义：A.Edge[i][j]=Wij或（vi,vj）∈VR∞无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞N.Edge=(v1v2v3v4v5v6)邻接矩阵法优点：邻接矩阵法缺点：顶点表：5748956531∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞
