图论中搜索算法讲座精.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《图论中搜索算法讲座精.ppt》由会员分享,可在线阅读,更多相关《图论中搜索算法讲座精.ppt(57页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图论中搜索算法讲座第1页,本讲稿共57页图论中搜索算法和最图论中搜索算法和最短路径算法短路径算法2第2页,本讲稿共57页Read Euler,read Euler,he is the master of us all.P.-S.de Laplace3第3页,本讲稿共57页4第4页,本讲稿共57页5第5页,本讲稿共57页1 1 图图_ _基本概念基本概念2 图的存储结构图的存储结构 4 最短路径最短路径3 图的遍历算法图的遍历算法 内容内容6第6页,本讲稿共57页图是一种较线性表和树更为复杂的数据结构图是一种较线性表和树更为复杂的数据结构。线性表线性表:线性结构线性结构树树:层次结构层次结构图图
2、:结点之间的关系可以是任意的,即图中任意两个数据元素结点之间的关系可以是任意的,即图中任意两个数据元素之间都可能相关。如:之间都可能相关。如:ABCDE第一节:图的基本概念7第7页,本讲稿共57页1 图的定义和基本术语图的定义和基本术语图图 G 是由两个集合是由两个集合顶点集顶点集 V(G)和边集和边集 E(G)组成的,记作组成的,记作G=(V(G),E(G),简称,简称G=(V,E)。ABCDEABCDEABCDEV是顶点的有穷是顶点的有穷非空非空集合集合 E是两个顶点之间的关系,即边的有穷集合是两个顶点之间的关系,即边的有穷集合 8第8页,本讲稿共57页无向图和有向图无向图和有向图 无向图
3、无向图:边是顶点的无序对,即边没有方向性。边是顶点的无序对,即边没有方向性。v1v2v3v5v4上面无向图可以表示为:上面无向图可以表示为:G=(V,E),其中其中V=v1,v2,v3,v4,v5 E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)(v1,v2)表示顶点表示顶点 v1 和和 v2 之间的边,之间的边,(v1,v2)=(v2,v1)。9第9页,本讲稿共57页有向图有向图:其边是顶点的有序对,即边有方向性。其边是顶点的有序对,即边有方向性。v1v2v4v3V=v1,v2,v3,v4 E=,在有向图中,通常边称为在有向图中,通常边称为弧
4、弧,表示顶点表示顶点 v1 到到 v2 的弧。的弧。称称 v1 为弧尾,称为弧尾,称 v2 为弧头。为弧头。上面有向图可以表示为:上面有向图可以表示为:G=(V,E),其中其中10第10页,本讲稿共57页带权无向图带权无向图(无向网无向网)和和 带权有向图带权有向图(有向网有向网)有时对图的边或弧赋予相关的数值,这种与图的边或弧相关的有时对图的边或弧赋予相关的数值,这种与图的边或弧相关的数值叫做数值叫做权权。这种带权的图通常称为这种带权的图通常称为网网。带权的有向图称为带权的有向图称为有向网有向网。带权的无向图称为带权的无向图称为无向网无向网。ABCDE53821497这些权可以表示从一个顶点
5、到另一个顶点的距离。这些权可以表示从一个顶点到另一个顶点的距离。可以表示从一个顶点到另一个顶点的耗费。可以表示从一个顶点到另一个顶点的耗费。11第11页,本讲稿共57页子图子图假设有两个图假设有两个图 G=(V,E)和和 G=(V,E),如果,如果 V V,且,且 E E,则称,则称 G 为为 G 的的子图子图。v1v2v4v3求子图求子图v1v1v3v1v4v3v1v2v4v3v1v2v4v312第12页,本讲稿共57页邻接与关联邻接与关联对于无向图对于无向图 G=(V,E),如果,如果边边(v,v)E,则称顶点,则称顶点 v 和和 v 互为邻接点,互为邻接点,即即 v 和和 v 相相邻接邻
6、接。边边(v,v)依附于顶点依附于顶点 v 和和 v,或者说,或者说(v,v)与顶点与顶点 v 和和 v 相相关联关联。对于有向图对于有向图 G=(V,E),如果,如果弧弧 E,则称顶点,则称顶点 v 邻接到邻接到顶点顶点 v,顶点顶点 v 邻接自邻接自顶点顶点 v。vvvv弧弧 和顶点和顶点 v,v 相相关联关联。13第13页,本讲稿共57页顶点的度顶点的度对于无向图,对于无向图,顶点顶点 v 的度的度是和是和 v 相关联的边的数目,记做相关联的边的数目,记做TD(v)。v1v2v3v5v4顶点顶点 v3 的度为的度为 3对于有向图,对于有向图,顶点顶点 v 的度的度 TD(V)分为两部分分
7、为两部分出度出度、入度入度。以顶点以顶点 v 为为头头的弧的数目称为的弧的数目称为 v 的入度的入度,记为,记为ID(v);以顶点以顶点 v 为为尾尾的弧的数目称为的弧的数目称为 v 的出度的出度,记为,记为OD(v);顶点顶点 v 的度的度为为 TD(v)=ID(v)+OD(v)。14第14页,本讲稿共57页v1v2v4v3顶点顶点 v1 的出度为的出度为 2顶点顶点 v1 的入度为的入度为 1顶点顶点 v1 的度为的度为 315第15页,本讲稿共57页路径、链、简单路径、回路路径、链、简单路径、回路(环环)、简单回路、简单回路无向图无向图 G 中若存在一条有穷非空序列中若存在一条有穷非空序
8、列 w=v0 e1 v1 e2 v2 ek vk,其,其中中 vi 和和 ei 分别为顶点和边,则称分别为顶点和边,则称 w 是从顶点是从顶点 v0 到到 vk 的一条的一条路径路径。顶点顶点 v0 和和 vk 分别称为路径分别称为路径 w 的起点和终点。的起点和终点。路径的长度是路径上的边的数目。路径的长度是路径上的边的数目。v0v1v2vk-1vk.e1e2ek起点和终点相同的路径称为起点和终点相同的路径称为回路回路(环环)。16第16页,本讲稿共57页若路径若路径 w 的边的边 e1,e2,ek 互不相同,则称互不相同,则称 w 为为链链。若路径若路径 w 的顶点的顶点 v0,v1,vk
9、 互不相同,则称互不相同,则称 w 为为简单路径简单路径。v0v1v2vk-1vk.e1e2ek链是否为简单路径链是否为简单路径?简单路径是否为链简单路径是否为链?不一定不一定一定一定e1e2e3e4e5除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单简单回路回路(简单环简单环)。17第17页,本讲稿共57页例例157324G26路径:路径:1,2,5,7,6,5,2,3路径长度:路径长度:7简单路径:简单路径:1,2,5,7,6回路:回路:1,2,5,7,6,5,2,1简单回路:简单回路:1,2,3,118第18页,
10、本讲稿共57页有向图有向图 G 中若存在一条有穷非空序列中若存在一条有穷非空序列 w=v0 e1 v1 e2 v2 ek vk,其,其中中 vi 和和 ei 分别为顶点和弧,则称分别为顶点和弧,则称 w 是从顶点是从顶点 v0 到到 vk 的一条的一条路径路径。v0v1v2vk-1vk.e1e2ek链链简单路径简单路径回路回路简单回路简单回路19第19页,本讲稿共57页例例245136G1路径:路径:1,2,3,5,6,3路径长度:路径长度:5简单路径:简单路径:1,2,3,5回路:回路:1,2,3,5,6,3,1简单回路:简单回路:3,5,6,320第20页,本讲稿共57页连通、连通、连通图
11、连通图无向图无向图G,如果从顶点,如果从顶点 v 到顶点到顶点 v 有路径,则称有路径,则称 v 和和 v 是是连通连通的。的。如果对于如果对于无向图无向图 G 中中任意任意两个顶点两个顶点 vi,vj V,vi 和和 vj 都是都是连通连通的,则称的,则称 G 是是连通图连通图。v1v2v3v5v4是否为连通图是否为连通图21第21页,本讲稿共57页第2节 图的存储结构顺序存储顺序存储邻接矩阵邻接矩阵链式存储链式存储邻接表邻接表邻接多重表邻接多重表十字链表十字链表如何表达顶点之间存在的联系?如何表达顶点之间存在的联系?v1v2v4v322第22页,本讲稿共57页2.1 邻接矩阵邻接矩阵设图设
12、图 G=(V,E)具有具有 n(n1)个顶点个顶点 v1,v2,vn 和和 m 条边或弧条边或弧 e1,e2,em,则,则 G 的邻接矩阵是的邻接矩阵是 nn 阶矩阵,记为阶矩阵,记为 A(G)。其每一个元素其每一个元素 aij 定义为定义为:邻接矩阵存放邻接矩阵存放 n 个顶点信息和个顶点信息和 n2 条边或弧信息。条边或弧信息。aij =01顶点顶点 vi 与与 vj 不相邻接不相邻接顶点顶点 vi 与与 vj 相邻接相邻接v1v2v4v3例有向图例有向图 GA(G)=1 2 3 412340 1 1 00 0 0 00 0 0 11 0 0 023第23页,本讲稿共57页v1v2v3v5
13、v4例无向图例无向图 G0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0A(G)=1 2 3 4 512345优点优点:1.容易判断任意两个顶点之间是否有边或弧。容易判断任意两个顶点之间是否有边或弧。2.容易求取各个顶点的度。容易求取各个顶点的度。24第24页,本讲稿共57页无向图,顶点无向图,顶点 vi 的的度度是邻接矩阵中第是邻接矩阵中第 i 行或第行或第 i 列的元素之和。列的元素之和。例例 G中,中,v1 的度为的度为 2。v1v2v3v5v4例无向图例无向图 G0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1
14、 0 0A(G)=1 2 3 4 51234525第25页,本讲稿共57页v1v2v4v3例有向图例有向图 GA(G)=1 2 3 412340 1 1 00 0 0 00 0 0 11 0 0 0有向图,顶点有向图,顶点 vi 的的出度出度是邻接矩阵中第是邻接矩阵中第 i 行的元素之和。行的元素之和。顶点顶点 vi 的的入度入度是邻接矩阵中第是邻接矩阵中第 i 列的元素之和。列的元素之和。例例 v1 的出度为的出度为 2;入度为;入度为 1。26第26页,本讲稿共57页无向图的邻接矩阵都是无向图的邻接矩阵都是对称矩阵对称矩阵。有向图的邻接矩阵一般不对称。有向图的邻接矩阵一般不对称。1 2 3
15、 412340 1 1 00 0 0 00 0 0 11 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 01 2 3 4 512345故无向图可以采用压缩存储方式故无向图可以采用压缩存储方式无向图无向图有向图有向图27第27页,本讲稿共57页带权图带权图(网网)的邻接矩阵的邻接矩阵v1v2v3v5v4v65487935651aij =wij顶点顶点 vi 与与 vj 相邻接相邻接顶点顶点 vi 与与 vj 不相邻接不相邻接 5 7 4 8 9 5 6 5 A=1 2 3 4 5 6123456 3 1 28第28页,本讲稿共57页邻接矩阵存储
16、的缺点:邻接矩阵存储的缺点:这种存贮方式的空间复杂度正比于图的结点个数的这种存贮方式的空间复杂度正比于图的结点个数的平方,所以,当图中结点很多但边却很少时,采用这种平方,所以,当图中结点很多但边却很少时,采用这种结构会造成很大的浪费。结构会造成很大的浪费。29第29页,本讲稿共57页2.2 2.2 邻接表邻接表对图中每一个顶点建立一个单链表,指示与该顶点关联的对图中每一个顶点建立一个单链表,指示与该顶点关联的边边或或出弧出弧。vexinfo firstarcadjvexnextarcarcinfo表结点表结点头结点头结点adjvex :邻接顶点位置邻接顶点位置arcinfo :边的信息边的信息
17、nextarc :下一条关联边结点下一条关联边结点vexinfo :顶点的信息顶点的信息firstarc :第一条关联边结点第一条关联边结点v1v2v3v5v4v6548793565130第30页,本讲稿共57页v1v2v3v5v4例无向图例无向图 Ge1e2e3e4e5e612345v1v2v3v4v54e22e15e43e31e15e64e52e33e51e23e62e4如何获取顶点的度?如何获取顶点的度?顶点顶点 vi 的度为第的度为第 i 条链表中的结点数。条链表中的结点数。需要多少存储空间?需要多少存储空间?n+2e31第31页,本讲稿共57页v1v2v4v3例有向图例有向图 Ge1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论中 搜索 算法 讲座
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内