【精品数据结构】图讲解

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

1、9.1图的基本概念第9章图9.2图的存储结构9.3图的遍历9.4生成树和最小生成树9.5最短路径9.6拓扑排序本章小结9.7AOE网与关键路径9.1图的基本概念9.1.1图的定义图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。在图G中,如果代表边的顶点对是无序的,则称G为无向图,无向图中代表边的无序顶点对通常用圆括号括起来,用以表示一条无向边。如果表示边的顶点对是有序的,则称G为有向图,在有向图中代表边的顶点对

2、通常用尖括号括起来。9.1.2图的基本术语端点和邻接点在一个无向图中,若存在一条边(vi,vj),则称vi和vj为此边的两个端点,并称它们互为邻接点。在一个有向图中,若存在一条边,则称此边是顶点vi的一条出边,同时也是顶点vj的一条入边；称vi和vj分别为此边的起始端点(简称为起点)和终止端点(简称终点)；称vi和vj互为邻接点。2.顶点的度、入度和出度在无向图中,顶点所具有的边的数目称为该顶点的度。在有向图中,以顶点vi为终点的入边的数目,称为该顶点的入度。以顶点vi为始点的出边的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶

3、点的度。若一个图中有n个顶点和e条边,每个顶点的度为di(1≤i≤n),则有：3.完全图若无向图中的每两个顶点之间都存在着一条边,有向图中的每两个顶点之间都存在着方向相反的两条边,则称此图为完全图。显然,完全无向图包含有条边,完全有向图包含有n(n-1)条边。例如,图(a)所示的图是一个具有4个顶点的完全无向图,共有6条边。图(b)所示的图是一个具有4个顶点的完全有向图,共有12条边。4.稠密图、稀疏图当一个图接近完全图时,则称为稠密图。相反,当一个图含有较少的边数(即当e<

4、V’,E’),若V’是V的子集,即V’V,且E’是E的子集,即E’E,则称G’是G的子图。例如图(b)是图(a)的子图,而图(c)不是图(a)的子图。6.路径和路径长度在一个图G=(V,E)中,从顶点vi到顶点vj的一条路径是一个顶点序列(vi,vi1,vi2,…,vim,vj),若此图G是无向图,则边(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)属于E(G)；若此图是有向图,则,,…,,属于E(G)。路径长度是指一条路径上经过的边的数目。

5、若一条路径上除开始点和结束点可以相同外,其余顶点均不相同,则称此路径为简单路径。例如,有图中,(v0,v2,v1)就是一条简单路径,其长度为2。7.回路或环若一条路径上的开始点与结束点为同一个顶点,则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。例如,右图中,(v0,v2,v1,v0)就是一条简单回路,其长度为3。9.连通、连通图和连通分量在无向图G中,若从顶点vi到顶点vj有路径,则称vi和vj是连通的。若图G中任意两个顶点都连通,则称G为连通图,否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然,任何连通

6、图的连通分量只有一个,即本身,而非连通图有多个连通分量。9.强连通图和强连通分量在有向图G中,若从顶点vi到顶点vj有路径,则称从vi到vj是连通的。若图G中的任意两个顶点vi和vj都连通,即从vi到vj和从vj到vi都存在路径,则称图G是强连通图。例如,右边两个图都是强连通图。有向图G中的极大强连通子图称为G的强连通分量。显然,强连通图只有一个强连通分量,即本身,非强连通图有多个强连通分量。10.权和网图中每一条边都可以附有一个对应的数值,这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图,也称作

7、网。例9.1有n个顶点的有向强连通图最多需要多少条边？最少需要多少条边？答：有n个顶点的有向强连通图最多有n(n-1)条边(构成一个有向完全图的情况)；最少有n条边(n个顶点依次首尾相接构成一个环的情况)。9.2图的存储结构9.2.1邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n＞0)个顶点的图,顶点的顺序依次为(v0,v1,…,vn-1),则G的邻接矩阵A是n阶方阵,其定义如下：(1)如果G是无向图,则：A[i][j]=1:若(vi,vj)∈E(G)0:其他(2)如果G是有向图,则：A[i][j]=1:若

8、vj>∈E(G)0:其他(3)如果G是带权无向图,则：A[i][j]=wij:若vi≠vj且(vi,vj)∈