图在日常生活及科学技术领域都有着广泛的应用.ppt

第七章 图 图在日常生活及科学技术领域都有着广泛的应用，是常用而又复杂的一种数据结构。 图的概念 图的存储结构 图的遍历 图的生成树和最小生成树 最短路径 拓扑排序 小结 over 图的概念 图(graph)的定义：一种复杂非线性数据结构。 ▲图的二元组定义G=(V,E)，V是顶点集，V={vi|0≤i≤n-1，n≥0，vi∈VertexType}，VertexType是顶点值类型，n为顶点数，n=0时V是空集；E是V上二元关系，即V上顶点序偶x,y(有向边)或无序对(x,y)(无向边)的集合，即是边集合。 ▲对于V上的每个顶点，在E中都允许有任意多个前驱和后继。 ▲图的二元组的另一个定义：图由顶点集(vertex set)V(G)和边集(edge set)E(G)所组成。 若V(G)为空，则E(G)也必然为空；若V(G)非空，则E(G)不一定非空。 ▲有向图(directed graph)---- 指图G的边集E(G)中为有向边。 ▲无向图(undirected graph)---- 指图G的边集E(G)中为无向边。 V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} V(G2)={0,1,2,3,4,5,6} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} V(G3)={0,1,2} E(G3)={0,1,1,0,1,2} E(G4)={0,1,2,3} V(G4)={0,1,1,0,0,2,2,0,0,3,3,0,1,2,2,1,1,3,3,1,2,3,3,2} 图的基本术语 ▲端点和邻接点 ▲顶点的度、入度、出度 ▲完全图、稠密图、稀疏图 ▲子图 ▲路径和回路 ▲连通和连通分量 ▲强连通图和强连通分量 ▲权和网 端点(endpoint)和邻接点(adjacent) 在一无向图中，若有边(vi,vj)，则称vi，vj为此边的两个端点，并称它们互为邻接点。 在一有向图中，若有边vi,vj，则称此边是顶点vi的一条出边(outedge)，顶点vj的一条入边(inedge)；vi是此边的起点/始点，vj是此边的终点；称vi和vj互为邻接点，并称vj是vi的出边邻接点，vi是vj的入边邻接点。 顶点的度、入度、出度 无向图中顶点v的度(deree)----D(v) 定义为以该顶点为一个端点的边的数目。 有向图中顶点v的度等于它的入度(ID(v))和出度(OD(v))之和，即D(v)=ID(v)+OD(v)。 ▲入度(in degree)----ID(v) 是该顶点的入边数目。 ▲出度(out degree)----OD(v) 是该顶点的出边数目。 若一个图有n个顶点和e条边，则该图所有顶点的度同边数e满足一下关系： 证明：∵每条边连接着两个顶点， ∴每个顶点的度数分别加1，总和加2， ∴全部顶点的度数为所有边数的2倍。 完全图、稠密图、稀疏图 完全图----若无向图中的每两个顶点间都存在一条边，有向图中每两个顶点间都存在反方向的两条边，则称这样的图为完全图。 无向完全图包含有n(n-1)/2条边；有向完全图包含有n(n-1)条边。 稠密图----一个图接近完全图时。 稀疏图----一个图含有较少的边数时。 子图 设有两个图G=(V,E)和G’=(V’,E’)，若V’?V，且E’?E，并且E’中的边所涉及的顶点均属于V’，则称G’是G的子图。 路径和回路 在一图G中，从顶点v到顶点v’的一条路径(path)是一个顶点序列u1,u2,…,um，其中v=u1，v’=um， 若此图是无向图，则(uj-1,uj)∈E(G)，2≤j≤m； 若此图是有向图，则 uj-1,uj∈E(G)，2≤j≤m。 路径长度----是指该路径上经过的边的数目。 简单路径----指一条路径上的所有顶点均不同。 复杂路径----指一条路径上的顶点有所重复。 回路(环cycle)----指一条路径上的前后两端点相同。 连通和连通分量 在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。 若图G中任意两个顶点都是连通的，则称G为连通图，否则为非连通图。 无向图G的极大连通子图称为G的连通分量。一个连通图有多个连通分量，且每个连通分量都能连通所有顶点；而非连通图的每个连通分量只能连通其中一部分顶点，不能连通全部顶点。 强连通图和强连通分量 在有向图G中，若从顶点vi到vj有路径