1、数据结构（六）,常宝宝北京大学计算机科学与技术系,内容提要,图状结构-实现-遍历-拓扑排序-最短路径,邻接矩阵,如果一个有向图含有n个顶点，则可以用nn的布尔型矩阵adjacencynn来存储图状结构。若顶点v邻接到顶点w，则adjacencyvw= true，否则adjacencyvw= false上述图状结构的表示方法称为邻接矩阵表示法。对于无向图而言，采用邻接矩阵表示法，则邻接矩阵必为对称矩阵，即adjacencyvw= adjacencywv。,邻接矩阵,邻接矩阵的C+实现,template class Graph int count;/顶点数 bool adjacencymax_si
2、zemax_size;/邻接矩阵;,邻接表,除采用邻接矩阵表示图状结构外，还可以采用邻接表的方法实现图状结构。在邻接表表示法中，n个顶点的图状结构可以表示成一个含有n个元素的线性表（称为顶点表）和n个线性表（称为邻接表）。每个顶点对应一个邻接表，顶点v对应的邻接表记录了顶点v邻接到的所有顶点。顶点表和邻接表既可以采用链式线性表也可以采用顺序线性表。,邻接表,邻接表,邻接表的C+实现（顶点表为顺序表，邻接表为链表）,typedef int Vertex;template class Graph int count;/顶点数 List neighborsmax_size;/邻接表;,邻接表,邻接表
3、的C+实现（顶点表、邻接表均为链表），这种实现也称为十字链表法。,class Edge;class Vertex Edge* first_edge; Vertex* next_vertex;class Edge Vertex* end_point; Edge* next_edge;class Graph Vertex* first_vertex;,图的遍历,和树的遍历类似，可以从图的某个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程称为图的遍历。图的遍历比树的遍历复杂。树的遍历始于根结点，图中没有根结点。图中可能存在回路。常用的图遍历方法深度优先遍历宽度优先遍历,深度优先遍历,
4、深度优先遍历类似于树的先根遍历，其基本思想为：从图中某个顶点v0出发，访问此顶点。然后依次从v0未被访问的邻接结点出发深度优先遍历图，直到图中所有和顶点v0连通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。,深度优先遍历,图中可能包含回路，因此在遍历过程中，一个顶点有可能被重复访问，为此设置一个布尔数组记录顶点是否被访问过。bool visitedmax_size;图有可能不连通，必须保证图中所有顶点被访问。,不是程序，不能编译,深度优先遍历算法,template void Graph:depth_first
5、( void (*visit)(Vertex,template void Graph:traverse( Vertex ,宽度优先遍历,宽度优先遍历的基本思想为：从图中某个顶点v0出发，访问此顶点。然后依次访问v0的各个未被访问过的邻接结点，然后分别从这些邻接结点出发宽度优先遍历图，直到图中所有和顶点v0连通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。,不是程序，不能编译,深度优先遍历算法,template void Graph:breadth_first( void (*visit)(Vertex ,拓扑
6、排序,什么是拓扑排序？ 如果G（V, E）是一个无环的有向图，则G上的拓扑排序指的是图中顶点满足下列条件的一种排序。若 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）只有当一个顶点的所有后继顶点已经全部加入拓扑排序后，才可把该顶点加入到拓扑排序的最前端。,深度优先排序,
7、拓扑排序的实现,有向图采用邻接表实现，顶点表采用顺序存储，邻接表采用链式存储。,typedef int Vertex;template class Graph int count;/顶点数 List neighborsgraph_size;/邻接表 void recursive_depth_sort(Vertex v, bool visited, List,深度优先排序的实现,template void Graph:depth_sort(List,深度优先排序的实现,template void Graph: recursive_depth_sort(Vertex v, bool *visite
8、d, List ,宽度优先排序,宽度优先排序（1）正向产生拓扑排序，首先产生拓扑排序中第一个顶点， 最后产生拓扑排序中最后一个顶点。（2）找一个没有前趋的顶点并将其作为拓扑排序的第一个顶点。（3）只有当一个顶点的所有前趋顶点已经全部加入拓扑排序后，才可把该顶点加入到拓扑排序的最后端。用一个数组记录图中每个顶点的前趋的个数int predecessor_countgraph_size;,宽度优先排序,宽度优先排序,template void Graph:breadth_sort(List ,最短路径,最短路径通常是针对有向网络而言的。即边上带有权值的有向图。假定G是一个有向网络，每条边上带有一个
9、非负的权值，则从顶点v到顶点w的最短路径指的是从顶点v到顶点w的所有路径中权值之和最小的路径。顶点v称做源点，顶点w称做终点。,最短路径,顶点0和顶点1之间的最短路径是哪条路径?怎样快速求出从某给定源点到其它顶点间的最短路径?,最短路径,Dijkstra算法依最短路径的长度递增的次序求得各条路径。设置一个集合S，该集合中存放从给定源点出发最短路径已知的所有顶点。因此算法开始时，集合S中只有源点一个顶点。随着算法的进行，其余的顶点被逐步加入集合S。因此算法要解决的问题是确定每步应该加入哪个顶点？设定一个数组int distancegraph_size;记录从源点到其它顶点的距离。,最短路径,若顶
10、点v已在S中，则distancev记录了从源点到顶点v的最短距离。若顶点v还未加入S中，则distancev记录了从源点到某个S中的顶点w的最短距离加上边的权值。distance数组的初始化。 (1)若从源点邻接到顶点v(有边的情况)，则distancev即为该边的权值。(2)否则(无边的情况)，则distancev为无穷大。算法进行时，从distance中找一个最小值，并将其对应的顶点加入到S中。,最短路径,一旦某顶点v加入S，则重新计算尚未加入S的顶点所对应的数组distance元素值。更新规则为：若distancew distancev+weight()，令distancew = dis
11、tancev+weight()如此循环往复，直到把所有顶点加入S。,最短路径,Dijkstra算法的实现,有向网络用邻接矩阵实现。,template class Graph int count; Weight adjacencygraph_sizegraph_size;public: void set_distances(Vertex source, Weight distance) const;,Dijkstra算法的实现,template void Graph:set_distances(Vertex source, Weight distance) const Vertex v,w; bool foundgraph_size;/集合S for (v=0; v:max(); for (w=0; wcount; w+) if (!foundw) if ( distancewmin) v=w; min=distancew; foundv=true; for (w=0; wcount; w+) if (!foundw) if (min+adjacencyvw distancew) distancew= min+adjacencyvw; ,上机作业,在机器上用C+分别实现和图状结构有关的算法。想一想为什么用Dijkstra算法可以求出最短路径？,
