数据结构课件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