045-046 寻路算法(1).pptVIP

6.2 简单寻路算法 6.2.2 广度优先算法 3．广度优先寻路算法的程序实现 第6章 寻路算法 在大范围的地图上深度优先算法效率会高一些，但这种算法找到的路径不保证是最短路径，只能算是可以接受的路径。而且对于同一张地图，当采用不同的有哪些信誉好的足球投注网站次序时，可能效率会相差很大，找到的路径也很可能会有不同。 广度优先算法的优点是无论在何种地形，它找到的路径一定是最短路径，但缺点也很明显，因为这种算法在本质上是穷举所有可能，所以可以说和任何一种寻路算法比较起来，效率都是最低的。 小结（理论课） 第6章 寻路算法 图论 广度优先算法 深度优先算法 小测验(题目部分) 第6章 寻路算法 判断题 1．深度优先有哪些信誉好的足球投注网站找到的一定是最短路径。（ ） 2．深度优先有哪些信誉好的足球投注网站可能出现存在路径却有哪些信誉好的足球投注网站失败的情况。（ ） 3．完全有向图的边数是节点相同的完全无向图的边数的2倍。（ ） 小测验（答案部分） 第6章 寻路算法 判断题 1．深度优先有哪些信誉好的足球投注网站找到的一定是最短路径。（ 错 ） 2．深度优先有哪些信誉好的足球投注网站可能出现存在路径却有哪些信誉好的足球投注网站失败的情况。（ 对 ） 3．完全有向图的边数是节点相同的完全无向图的边数的2倍。（ 对 ） 课后作业 第6章 寻路算法 【作业1】完成深度优先算法实现寻路 思路分析：利用深度优先算法，完成寻路。 【作业2】完成广度优先算法实现寻路 思路分析：利用广度优先算法，完成寻路。 第6章 寻路算法 The End 专业教程 理论讲解部分 网络游戏开发——高级应用 第6章 寻路算法 第6章 寻路算法 图论 深度优先算法 广度优先算法 深度优先算法 广度优先算法 深度优先算法 广度优先算法 了解图论的基础知识 掌握深度优先算法的原理 掌握广度优先算法的原理 6.1 图论 6.1.1 图论基础 第6章 寻路算法 图论（Graph Theory）是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 四色猜想：可以用四种不同的颜色将接壤的国家分开表示 6.1 图论 6.1.2 图的定义 1．图的表示方式 第6章 寻路算法 图（Graph）是由非空的节点集合和一个描述节点之间关系（边或者弧）的集合组成。 G表示图、V表示节点的集合、E表示边的集合。 6.1 图论 6.1.2 图的定义 1．图的表示方式 第6章 寻路算法 给定一个图： 用数学方式表示为： 6.1 图论 6.1.2 图的定义 2．图的类型 第6章 寻路算法 若图中的边是节点的无序对（即两节点不分谁是起始点，谁是终止点），则称此图为无向图。通常用圆括号表示无向边。若图中的边是节点的有序对，则称此图为有向图。有向边又称为弧，通常用尖括号表示一条有向边。 有向图与无向图 6.1 图论 6.1.2 图的定义 2．图的类型 第6章 寻路算法 在一个有向完全图或是一个无向完全图中任意一个节点都是可以到达其他所有节点的，或者说是可以直达其他任意一个节点。 无向完全图与有向完全图 6.1 图论 6.1.2 图的定义 2．图的类型 第6章 寻路算法 若 都是E（G）中的弧，则称节点序列 为从节点Vp到节点Vq的一条路径。路径长度定义为路径上边或弧的数目。 路径与连通图 如果图中两个点之间有路径，称两个点是连通的，如果图中任意两点都有路径，称为连通图。 6.1 图论 6.1.3 计算机中图的存储结构 1．邻接矩阵（Adjacency Matrix） 第6章 寻路算法 所谓邻接矩阵的存储结构，就是用一维数组存储图中节点的信息，用矩阵来表示图中各节点之间的邻接关系。 6.1 图论 6.1.3 计算机中图的存储结构 2．邻接表（Adjacency List） 第6章 寻路算法 邻接表是图的一种顺序存储与链式存储结合的存储方法。 6.1 图论 6.1.3 计算机中图的存储结构 3．十字链表（Orthogonal List） 第6章 寻路算法 十字链表是有向图的一种存储方法，它实际上是邻接表与逆邻接表的结合，即把每一条边的边节点分别组织到以弧尾顶点为头节点的链表和以弧头顶点为头顶点的链表中。 6.2 简单寻路算法 6.2.1 深度优先算法 1．算法原理 第6章 寻路算法 它的基本思路是：按照某种条件往前试探有哪些信誉好的足球投注网站，如果前进中遭到失败则退回头另选通路继续有哪些信誉好的足球投注网站，直到找到符合条件的目标为止。 6.2 简单寻路算法 6.2.1 深度优先算法 2．使用深度优先算法实现图的遍历 第6章 寻路算法 图的遍历就是访问图中的每一个顶点。 从节点1开始，做