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