图论基础知识.ppt
《图论基础知识.ppt》由会员分享,可在线阅读,更多相关《图论基础知识.ppt(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 二、无向图的传递闭包问题二、无向图的传递闭包问题 三、生成树与最小生成树问题三、生成树与最小生成树问题 四、最短路径问题四、最短路径问题 五、拓扑排序与关键路径五、拓扑排序与关键路径 六、图论模型的建立六、图论模型的建立 七、匹配七、匹配 八、最大流八、最大流常州市第一中学常州市第一中学 林厚从林厚从图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 1 1、回顾三种数据结构模型:线性表、树、图、回顾三种数据结构模型:线性表、树、图 2 2、图的基本概念:、图的基本概念:图图=(顶顶点点集集,边边集集),顶顶点点集集必
2、必须须非非空空,什什么么是是顶顶点点,什什么么是是边边?图的分类:无向图、有向图,主要看是否可逆图的分类:无向图、有向图,主要看是否可逆 带权图:权的含义,不加权的图也可以认为所有边上的权都是带权图:权的含义,不加权的图也可以认为所有边上的权都是1 1。阶和度:一个图的阶是指图中顶点的个数阶和度:一个图的阶是指图中顶点的个数 如果顶点如果顶点A A和和B B之间有一条边相连,则称之间有一条边相连,则称A A和和B B是关联的是关联的 顶点的度:与该顶点相关联的边的数目,有奇点、偶点之分顶点的度:与该顶点相关联的边的数目,有奇点、偶点之分 对于有向图:有入度和出度之分对于有向图:有入度和出度之分
3、常州市第一中学常州市第一中学 林厚从林厚从图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 2 2、图的基本概念:、图的基本概念:定理:无向图中所有顶点的度之和等于边数的定理:无向图中所有顶点的度之和等于边数的2 2倍;倍;有向图中所有顶点的入度之和等于所有顶点的出度之和;有向图中所有顶点的入度之和等于所有顶点的出度之和;任意一个无向图一定有偶数个(或任意一个无向图一定有偶数个(或0 0个)奇点;个)奇点;完全图:完全图:一个一个n n阶的完全无向图含有阶的完全无向图含有n*(n-1)/2n*(n-1)/2条边;条边;一个一个n n阶的完全有向图含有阶的完全有向图含有n*(n-1
4、)n*(n-1)条边;条边;稠密图:当一个图的边数接近完全图时;稠密图:当一个图的边数接近完全图时;稀疏图:当一个图的边数远远少于完全图时;稀疏图:当一个图的边数远远少于完全图时;在具体使用时,要选用不同的存储结构;在具体使用时,要选用不同的存储结构;子图:从一个图中取出若干顶点、若干边构成的一个新的图;子图:从一个图中取出若干顶点、若干边构成的一个新的图;常州市第一中学常州市第一中学 林厚从林厚从图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 2 2、图的基本概念:、图的基本概念:路径:对于图路径:对于图G=G=(V V,E E),),对于顶点对于顶点a a、b b,如果存在
5、一些顶点序列如果存在一些顶点序列 x x1 1=a,x=a,x2 2,x xk k=b(k1)=b(k1),且(且(x xi i,x xi i+1+1)EE,i=1,2k-1i=1,2k-1,则称则称 顶点序列顶点序列x x1 1,x,x2 2,x xk k为顶点为顶点a a到顶点到顶点b b的一条路径,而路径上边的一条路径,而路径上边 的数目(即的数目(即k-1k-1)称为该路径的长度。称为该路径的长度。并称顶点集合并称顶点集合 x x1 1,x,x2 2,x xk k 为一个连通集。为一个连通集。简单路径:如果一条路径上的顶点除了起点和终点可以相同外,其它简单路径:如果一条路径上的顶点除了
6、起点和终点可以相同外,其它 顶点均不相同,则称此路径为一条简单路径;起点和终点顶点均不相同,则称此路径为一条简单路径;起点和终点 相同的简单路径称为回路(或环)。相同的简单路径称为回路(或环)。常州市第一中学常州市第一中学 林厚从林厚从图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 2 2、图的基本概念:、图的基本概念:路径和简单路径的举例:路径和简单路径的举例:左图左图123123是一条简单路径,长度为是一条简单路径,长度为2 2,而而1341313413就不是简单路径;就不是简单路径;右图右图121121为一个回路。为一个回路。常州市第一中学常州市第一中学 林厚从林厚从图论
7、算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 2 2、图的基本概念:、图的基本概念:连通:连通:在一个图中,如果从顶点在一个图中,如果从顶点U U到顶点到顶点V V有路径,有路径,则称则称U U和和V V是连通的;是连通的;有根图:有根图:在一个图中,若存在一个顶点在一个图中,若存在一个顶点WW,它与其它顶点都是连通的,则称此它与其它顶点都是连通的,则称此图为有根图,顶点图为有根图,顶点WW即为它的根。即为它的根。上面的两个图都是有根图,左图的上面的两个图都是有根图,左图的1 1、2 2、3 3、4 4都可以作为根;都可以作为根;而右图的而右图的1 1、2 2才可以作为根。才可以
8、作为根。常州市第一中学常州市第一中学 林厚从林厚从图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 2 2、图的基本概念:、图的基本概念:连通图:连通图:如果一个无向图中,任意两个顶点之间如果一个无向图中,任意两个顶点之间 都是连通的,则称该无向图为连通图。否则称为非连通图;左图为一个连通图。都是连通的,则称该无向图为连通图。否则称为非连通图;左图为一个连通图。强连通图:强连通图:在一个有向图中,对于任意两个顶点在一个有向图中,对于任意两个顶点U U和和V V,都存在着一条从都存在着一条从U U到到V V的的有向路径,同时也存在着一条从有向路径,同时也存在着一条从V V到到U U
9、的有向路径,则称该有向图为强连通图;右的有向路径,则称该有向图为强连通图;右图不是一个强连通图。图不是一个强连通图。连通分支:连通分支:一个无向图的连通分支定义为该图的最大连通子图,左图的连一个无向图的连通分支定义为该图的最大连通子图,左图的连通分支是它本身。通分支是它本身。强连通分支:强连通分支:一个有向图的强连通分支定义为该图的最大的强连通子图,一个有向图的强连通分支定义为该图的最大的强连通子图,右图含有两个强连通分支,一个是右图含有两个强连通分支,一个是1 1和和2 2构成的一个子图,一个是构成的一个子图,一个是3 3独立构独立构成的一个子图。成的一个子图。常州市第一中学常州市第一中学
10、林厚从林厚从图论算法与实现图论算法与实现 一、图论基础知识一、图论基础知识 3 3、图的存储结构(、图的存储结构(n n阶阶e e条边):条边):邻接矩阵邻接矩阵 边集数组边集数组 邻接表邻接表 优点优点 直直观观方便方便,AiAi,jj时间时间O O(1 1)存存储储稀疏稀疏图时图时,空,空间间效率比效率比较较好,也好,也比比较较直直观观 便于便于查查找任一找任一顶顶点的关点的关联边联边及及关关联联点点,查查找运算的找运算的时间时间复复杂杂性平均性平均为为O(e/n)O(e/n)缺点缺点 存存储储稀疏稀疏图图,会造,会造成很大的空成很大的空间间浪浪费费 不适合不适合对顶对顶点的运点的运算和算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基础知识
限制150内