数据结构课件07全.ppt
文本预览下载声明
数据结构课程的内容 第7章 图 7.1 图的基本术语 证明: 例:判断下列4种图形各属什么类型? 稀疏图:稠密图: 带权图: 邻接点: 简单路径: 图的抽象数据类型 7.2 图的存储结构 图的特点:非线性结构(m :n ) 一、邻接矩阵(数组)表示法 例2 :有向图的邻接矩阵 特别讨论 :网(即有权图)的邻接矩阵 图的邻接矩阵存储表示(参见教材P161) 例:用邻接矩阵生成无向网的算法(参见教材P162) 二、邻接表(链式)表示法 例1:无向图的邻接表 例3:已知某网的邻接(出边)表,请画出该网络。 邻接表存储法的特点: 讨论:邻接表与邻接矩阵有什么异同之处? 图的邻接表存储表示(参见教材P163) 三、十字链表(自学)(适用于有向图)四、邻接多重表(自学)(适用于无向图) 7.3 图的遍历 一、深度优先搜索( DFS ) 深度优先搜索(遍历)步骤: 讨论1:计算机如何实现DFS? 讨论2: DFS算法如何编程? 讨论3:在图的邻接表中如何进行DFS? 讨论4: 邻接表的DFS算法如何编程? DFS 算法效率分析: 二、广度优先搜索( BFS ) 广度优先搜索(遍历)步骤: 讨论1:计算机如何实现BFS? 讨论2: BFS算法如何编程? BFS 算法效率分析: 7.4 图的其他运算 1. 求图的生成树 2. 求最小生成树 普利姆(Prim)算法 例: 计算机内怎样实现Prim(普里姆)算法? 具体示例: 算法流程 Kruskal(克鲁斯卡尔)算法 计算机内怎样实现Kruskal算法? 具体示例:详见殷人昆等,数据结构习题解析,P180-181 3. 求最短路径 一、单源最短路径 (Dijkstra算法) 例2: Dijkstra(迪杰斯特拉)算法 算法描述: 算法的C语言程序见教材P189 对应流程图见下页 算法流程: 例3: 二、所有顶点之间的最短路径 问题的提出:已知一个各边权值均大于0的带权有向图,对每一对顶点 vi ? vj,希望求出vi 与vj之间的最短路径和最短路径长度。 解决思路: 可以通过调用n次Dijkstra算法来完成,但时间复杂度为O(n3)。 改进: Floyd算法(略) 本章小结 基本思想:——仿树的层次遍历过程。 Breadth_First Search v1 v1 v2 v3 v8 v7 v6 v4 v5 BFS 结果 例1: → → → → v2 v3 → v4 v5 → v6 v7 → v8 例2: v3 → BFS 结果 v4 → v5 → 起点 遍历步骤 起点 v2 → v1 → v6 → v9 → v8 → v7 简单归纳: 在访问了起始点v之后,依次访问 v的邻接点; 然后再依次访问这些顶点中未被访问过的邻接点; 直到所有顶点都被访问过为止。 广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有回退的情况。因此,广度优先搜索不是一个递归的过程,其算法也不是递归的。 邻接表 ——除辅助数组visited [n ]外,还需再开一辅助队列! 例: 起点 辅助队列 v2已访问过了 BFS 遍历结果 入队! 初始f=n-1,r=0 BFS1(List, n, v) { Visit(v); Visited[v]=1; front=n-1;rear=0; q[rear]=v; while(rear!=front){ front=(front+1)%n; v=q[front]; p=List[v].firstarc; while(!p){ if(! Visited[adjvex(p)] ) {Visit(adjvex(p)); Visited[adjvex(p)]=1; rear=(rear+1)%n; q[rear]= adjvex(p)} p=nextarc(p); } } return } ——层次遍历应当用队列! //List为邻接表,v为起点,Q[n]为辅助队列 //访问(例如打印)顶点v并修改标志 // BFS1 //指向单链表中下一个邻接点 //队列指针初始化 (教材上BFS递归算法见P170) //起始点入队 //队不空时 //访问过的顶点出队 //P指向第1个邻接点 未到表尾,且邻接域未访问过, 则先输出再改标记,最后再入队 DFS与BFS之比较: 空间复杂度相同,都是O(n)(借用了堆栈或队列); 时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无关。 如果使用邻接表来表示图,则BFS循环的总时间代价为 d0
显示全部