资源描述：
《算法与数据结构第16章 图.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《《算算法法与与数数据据结结构构》》AlgorithmsAlgorithmsandandDataDataStructuresStructures第16章图116.1图的基本概念16.2抽象数据类型图16.3图的表示法16.4用邻接矩阵实现图16.5用邻接表实现图16.6用邻接矩阵实现赋权图16.7用邻接表实现赋权图16.8图的遍历搜索算法2011-6-3福州大学数学与计算机科学学院1《《算算法法与与数数据据结结构构》》AlgorithmsAlgorithmsandandDataDataStructuresStructures学习要点:·理解图的定义和与图相
2、关的有向图、无向图、赋权图、连通图等术语。·理解图是一个表示复杂非线性关系的数据结构。·掌握图的邻接矩阵表示及其实现方法。·掌握图的邻接表表示及其实现方法。·了解图的紧缩邻接表表示方法。·掌握图的广度优先搜索方法。·掌握图的深度优先搜索方法。·掌握单源最短路径问题的Dijkstra算法。·掌握所有顶点对之间最短路径问题的Floyd算法。·掌握构造最小支撑树的Prim算法。·掌握构造最小支撑树的Kruskal算法。·理解图的最大匹配问题的增广路径算法。2011-6-3福州大学数学与计算机科学学院2《《算算法法与与数数据据结结构构》》AlgorithmsAlg
3、orithmsandandDataDataStructuresStructures16.1图的基本概念图(Graph)——图G是由两个集合V(G)和E(G)组成记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成其中：V(G)是顶点的非空有限集E(G)是有向边的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为有向边的起点，w为有向边的终点无向图——无向图G是由两个集合V(G)和E(G)组成其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边
4、是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)本书约定：不考虑顶点到其自身的边；不允许一条边在图中重复出现。即只讨论简单图。2011-6-3福州大学数学与计算机科学学院3《《算算法法与与数数据据结结构构》》AlgorithmsAlgorithmsandandDataDataStructuresStructures例245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例1573246G2图G2中：V(G2)={1,2,3,4,
5、5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}2011-6-3福州大学数学与计算机科学学院4《《算算法法与与数数据据结结构构》》AlgorithmsAlgorithmsandandDataDataStructuresStructures完全图——设
6、V
7、=n,
8、E
9、=e。对有向图G，若e=n(n-1)，则称G为完全的有向图；对无向图G，若e=n(n-1)/2，则称G为完全的无向图。邻接、关联——若(u,v)是一条无向边，则称顶点u和v互为邻接点，或称u和v相邻接；并称边(u,v)关联于顶点u和
10、v，或称边(u,v)与顶点u和v相关联。若(u,v)是一条有向边，则称v是u的邻接顶点；并称边(u,v)关联于顶点u和v，或称边(u,v)与顶点u和v相关联。顶点的度无向图中，顶点v的度为关联于该顶点相连的边数，记为D(v)有向图中，顶点v的度分成入度与出度入度：以顶点v为终点的边的数目，记为ID(v)出度：以顶点v为起点的边的数目，记为OD(v)D(v)=ID(v)+OD(v)无论是有向图还是无向图，顶点数n，边数e和度数之间有如下关系：1ne=åD(vi)2i=12011-6-3福州大学数学与计算机科学学院5《《算算法法与与数数据据结结构构》》Algo
11、rithmsAlgorithmsandandDataDataStructuresStructures子图——如果图G(V,E)和图G’(V’,E’),满足：V’ÍVE’ÍE则称G’为G的子图有向图G1的若干子图无向图G2的若干子图2011-6-3福州大学数学与计算机科学学院6《《算算法法与与数数据据结结构构》》AlgorithmsAlgorithmsandandDataDataStructuresStructures路径：在无向图G中，若存在一个顶点序列u(1),u(2),…，u(m),使得(u(i),u(i+1))∈E(G)，i=1,2,…，m-1,则称
12、该顶点序列为顶点u(1)和u(m)之间的一条路径。其中u(1)称为
