数据结构12.ppt

数据结构（六） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 内容提要 图状结构-实现-遍历-拓扑排序-最短路径 邻接矩阵 如果一个有向图含有n个顶点，则可以用n×n的布尔型矩阵adjacency[n][n]来存储图状结构。 若顶点v邻接到顶点w，则adjacency[v][w] true，否则adjacency[v][w] false 上述图状结构的表示方法称为邻接矩阵表示法。 对于无向图而言，采用邻接矩阵表示法，则邻接矩阵必为对称矩阵，即adjacency[v][w] adjacency[w][v]。 邻接矩阵 邻接矩阵的C++实现 邻接表 除采用邻接矩阵表示图状结构外，还可以采用邻接表的方法实现图状结构。 在邻接表表示法中，n个顶点的图状结构可以表示成一个含有n个元素的线性表（称为顶点表）和n个线性表（称为邻接表）。每个顶点对应一个邻接表，顶点v对应的邻接表记录了顶点v邻接到的所有顶点。 顶点表和邻接表既可以采用链式线性表也可以采用顺序线性表。 邻接表 邻接表 邻接表的C++实现（顶点表为顺序表，邻接表为链表） 邻接表 邻接表的C++实现（顶点表、邻接表均为链表），这种实现也称为十字链表法。 图的遍历 和树的遍历类似，可以从图的某个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程称为图的遍历。 图的遍历比树的遍历复杂。 树的遍历始于根结点，图中没有根结点。 图中可能存在回路。 常用的图遍历方法 深度优先遍历 宽度优先遍历 深度优先遍历 深度优先遍历类似于树的先根遍历，其基本思想为： 从图中某个顶点v0出发，访问此顶点。然后依次从v0未被访问的邻接结点出发深度优先遍历图，直到图中所有和顶点v0连通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。 深度优先遍历 图中可能包含回路，因此在遍历过程中，一个顶点有可能被重复访问，为此设置一个布尔数组记录顶点是否被访问过。 bool visited[max_size]; 图有可能不连通，必须保证图中所有顶点被访问。 深度优先遍历算法 宽度优先遍历 宽度优先遍历的基本思想为： 从图中某个顶点v0出发，访问此顶点。然后依次访问v0的各个未被访问过的邻接结点，然后分别从这些邻接结点出发宽度优先遍历图，直到图中所有和顶点v0连通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。 深度优先遍历算法 拓扑排序 什么是拓扑排序？ 如果G＝（V, E）是一个无环的有向图，则G上的拓扑排序指的是图中顶点满足下列条件的一种排序。若 v, w ∈E，则在顶点v必须位于顶点w之前。 上图可能的拓扑排序 9 6 3 4 8 2 0 5 1 7 3 6 9 0 2 4 1 5 8 7 拓扑排序算法 常用拓扑排序方法： 深度优先排序 宽度优先排序 深度优先排序（1）逆序产生拓扑排序，首先产生拓扑排序中最后一个顶点， 最后产生拓扑排序中的第一个顶点。（2）找一个没有后继的顶点并将其作为拓扑排序的最后一个顶点。（3）只有当一个顶点的所有后继顶点已经全部加入拓扑排序后，才可把该顶点加入到拓扑排序的最前端。 深度优先排序 拓扑排序的实现 有向图采用邻接表实现，顶点表采用顺序存储，邻接表采用链式存储。 深度优先排序的实现 深度优先排序的实现 宽度优先排序 宽度优先排序（1）正向产生拓扑排序，首先产生拓扑排序中第一个顶点， 最后产生拓扑排序中最后一个顶点。（2）找一个没有前趋的顶点并将其作为拓扑排序的第一个顶点。（3）只有当一个顶点的所有前趋顶点已经全部加入拓扑排序后，才可把该顶点加入到拓扑排序的最后端。 用一个数组记录图中每个顶点的前趋的个数int predecessor_count[graph_size]; 宽度优先排序 宽度优先排序 最短路径 最短路径通常是针对有向网络而言的。即边上带有权值的有向图。 假定G是一个有向网络，每条边上带有一个非负的权值，则从顶点v到顶点w的最短路径指的是从顶点v到顶点w的所有路径中权值之和最小的路径。顶点v称做源点，顶点w称做终点。 最短路径 顶点0和顶点1之间的最短路径是哪条路径? 怎样快速求出从某给定源点到其它顶点间的最短路径? 最短路径 Dijkstra算法 依最短路径的长度递增的次序求得各条路径。 设置一个集合S，该集合中存放从给定源点出发最短路径已知的所有顶点。 因此算法开始时，集合S中只有源点一个顶点。随着算法的进行，其余的顶点被逐步加入集合S。因此算法要解决的问题是确定每步应该加入哪个顶点？ 设定一个数