软件技术基础图课件.ppt

《软件技术基础图课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.图的基本概念2.图的存储方法3.图的遍历第十三章图图的引入图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。图的引入图与线性表和树的比较：数据结构逻辑结构直接前驱个数直接后继个数线性表线性结构至多1个至多1个树非线性结构至多1个多个图非线性结构多个多个1.图的

2、基本概念2.图的存储方法3.图的遍历第十三章图1.图的基本概念下面介绍图的一些常用的基本术语。1.1图的定义图(G)是一种非线性数据结构，它由两个集合V(G)和E(G)组成，形式上记为：G=(V,E),其中：V(G)是顶点(Vertex)的非空有限集合，E(G)是V(G)中任意两个顶点之间的关系集合，又称为边(Edge)的有限集合。1.2有向图和无向图(1)有向图：当且仅当图G的每条边都有方向，即每条边都用箭头表明了方向，则此图为有向图。下图(a)；有向边记为〈起始顶点，终止顶点〉。用尖括号括起一对顶点表示。

3、有向边又称为弧，因此弧的起始顶点就称为弧尾，终止顶点称为弧头。顶点数n和边数e的有向图满足0≤e≤n(n-1)的关系。(a)有向图G1V(G1)={A,B,C}E(G1)={,,,}1.图的基本概念(2)无向图：如果图中每条边都是顶点的无序对，则称此图为无向图。如下图(b)。无向边用两个顶点组成的无序对表示，记为(起始顶点，终止顶点)。用圆括号括起一对顶点表示。注：顶点数n和边数e的无向图满足0≤e≤n(n-1)/2的关系。(b)无向图G2V(G2)={A,B,C}E(G

4、2)={(A,B),(B,C),(C,A)}={(B,A),(C,B),(A,C)}注意，在无向图中，(V1,V2)与(V2,V1)表示同一条边。1.图的基本概念约定在下面的讨论中，不考虑顶点到其自身的边，也不允许一条边在图中重复出现。ABCAB(a)存在顶点到其自身的边(b)两点间有多条相同的边1.图的基本概念1.3几种特殊的图(1)完全无向图：顶点数n和边数e满足e=n(n-1)/2的关系的无向图。(2)完全有向图：顶点数n和边数e满足e=n(n-1)的关系的有向图。(3)稀疏图：顶点数n和边数e满足e

5、lgn的关系的图。(4)稠密图：顶点数n和边数e满足e>=nlgn的关系的图。1.图的基本概念(5)子图：两个同类型的图G1=(V1,E1)和G2=(V2,E2)存在关系V1V2,E1E2,则称G1是G2的子图。例：图G2ABC图G1V(G1)={A,B,C}E(G1)={,,}V(G2)={A,B,C}E(G2)={,,,}1.图的基本概念1.4图的邻接关系无向图G中，若边(vi,vj)E(G)则称顶点vi和vj相互邻接，互为邻接点；并称边

6、(vi,vj)关联于顶点vi和vj或称边(vi,vj)与顶点vi和vj相关联。在有向图G中，若边〈vi,vj〉E(G)则称为顶点vi邻接到vj或vj邻接于vi；并称边〈vi,vj〉关联于顶点vI和vj或称边〈vi,vj〉与顶点vi和vj相关联。(a)有向图G1(b)无向图G21.图的基本概念1.5图的度无向图顶点的度：在无向图中关联于某一顶点vi的边的数目称为vi的度，记为D(vi)。有向图顶点的度：在有向图中，把以顶点vi为终点的边的数目称为vi的入度，记为ID(vi)；把以顶点vi为起点的边的数目称为vi的

7、出度，记为OD(vi)；把顶点vi的度定义为该顶点的入度和出度之和。(a)有向图G1(b)无向图G21.图的基本概念图的边与度的关系：有n个顶点e条边的图G中，每个顶点的度为D(vi)(1≤i≤n)，则存在以下关系：对于有向图G1对于有向图G2D(A)=3D(A)=2D(B)=3D(B)=3D(C)=2D(C)=2e=(3+3+2)/2=4e=(2+2+2)/2=3(a)有向图G1(b)无向图G21.图的基本概念1.6权与网络权：如果图的边或弧具有一个与它相关的数时，这个数就称为该边或弧的权。这个数常用来表示一

8、个顶点到另一个顶点的距离或消耗。网络：图中的每条边都具有权时，这个带权图被称为网络，简称为网。35641.图的基本概念1.7路径、简单路径和简单回路路径：若从顶点v1出发，沿着一些边经过顶点v1,v2,…,vn-1到达顶点vn，则称顶点序列(v1,v2,v3,…,vn-1,vn)为从v1到vn的一条路径。路径的长度：将无权图沿路径经过的边数称为该路径的长度。对于有权图，则取沿路径各边的