常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 数据结构（六） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn.

Presentation on theme: "常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 数据结构（六） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn."— Presentation transcript:

1 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn
数据结构（六） 常宝宝 北京大学计算机科学与技术系

2 内容提要 图状结构 -实现 -遍历 -拓扑排序 -最短路径

3 邻接矩阵 如果一个有向图含有n个顶点，则可以用n×n的布尔型矩阵adjacency[n][n]来存储图状结构。
若顶点v邻接到顶点w，则adjacency[v][w]= true，否则adjacency[v][w]= false 上述图状结构的表示方法称为邻接矩阵表示法。 对于无向图而言，采用邻接矩阵表示法，则邻接矩阵必为对称矩阵，即adjacency[v][w]= adjacency[w][v]。

4 邻接矩阵 邻接矩阵的C++实现 template <int max_size> class Graph { int count; //顶点数 bool adjacency[max_size][max_size]; //邻接矩阵 };

5 邻接表 除采用邻接矩阵表示图状结构外，还可以采用邻接表的方法实现图状结构。
在邻接表表示法中，n个顶点的图状结构可以表示成一个含有n个元素的线性表（称为顶点表）和n个线性表（称为邻接表）。每个顶点对应一个邻接表，顶点v对应的邻接表记录了顶点v邻接到的所有顶点。 顶点表和邻接表既可以采用链式线性表也可以采用顺序线性表。

6 邻接表

7 邻接表 邻接表的C++实现（顶点表为顺序表，邻接表为链表）
typedef int Vertex; template <int max_size> class Graph { int count; //顶点数 List< Vertex> neighbors[max_size]; //邻接表 };

8 邻接表 邻接表的C++实现（顶点表、邻接表均为链表），这种实现也称为十字链表法。 class Edge;
class Vertex { Edge* first_edge; Vertex* next_vertex; }; class Edge { Vertex* end_point; Edge* next_edge; }; class Graph { Vertex* first_vertex; };

9 图的遍历 和树的遍历类似，可以从图的某个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程称为图的遍历。
图的遍历比树的遍历复杂。 树的遍历始于根结点，图中没有根结点。 图中可能存在回路。 常用的图遍历方法 深度优先遍历 宽度优先遍历

10 深度优先遍历 深度优先遍历类似于树的先根遍历，其基本思想为：
从图中某个顶点v0出发，访问此顶点。然后依次从v0未被访问的邻接结点出发深度优先遍历图，直到图中所有和顶点v0连通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。

11 深度优先遍历 图中可能包含回路，因此在遍历过程中，一个顶点有可能被重复访问，为此设置一个布尔数组记录顶点是否被访问过。 bool visited[max_size]; 图有可能不连通，必须保证图中所有顶点被访问。

12 深度优先遍历算法 template <int max_size> void Graph<max_size>::depth_first( void (*visit)(Vertex&)) const { bool visited[max_size]; Vertex v; for (all v in G) visited[v]=false; for (all v in G) if ( !visited[v] ) traverse(v, visited, visit); } 不是程序，不能编译 template <int max_size> void Graph<max_size>::traverse( Vertex &v, bool visted[], void (*visit)(Vertex&)) const { Vertex w; visited[v] = true; (*visit)(v); for (all w adjacent to v) if ( !visited[w] ) traverse(w, visited, visit); }

13 宽度优先遍历 宽度优先遍历的基本思想为： 从图中某个顶点v0出发，访问此顶点。然后依次访问v0的各个未被访问过的邻接结点，然后分别从这些邻接结点出发宽度优先遍历图，直到图中所有和顶点v0连通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。

14 深度优先遍历算法 template <int max_size> void Graph<max_size>::breadth_first( void (*visit)(Vertex&)) const { Queue q; bool visited[max_size]; Vertex v, w, x; for (all v in G) visited[v]=false; for (all v in G) if ( !visited[v] ) { q.append(v); while( !q.empty() ) { q.retrieve(w); if ( !visited[w] ) { visited[w]=true; (*visit)(w); for ( all x adjacent to w ) q.append(x); } q.serve(); } } } 不是程序，不能编译

15 拓扑排序 拓扑排序不唯一！ 什么是拓扑排序？
如果G＝（V, E）是一个无环的有向图，则G上的拓扑排序指的是图中顶点满足下列条件的一种排序。 若 <v, w> ∈E，则在顶点v必须位于顶点w之前。 上图可能的拓扑排序 拓扑排序不唯一！

16 拓扑排序算法 常用拓扑排序方法： 深度优先排序 宽度优先排序
深度优先排序 （1）逆序产生拓扑排序，首先产生拓扑排序中最后一个顶点， 最后产生拓扑排序中的第一个顶点。 （2）找一个没有后继的顶点并将其作为拓扑排序的最后一个顶点。 （3）只有当一个顶点的所有后继顶点已经全部加入拓扑排序后，才可把该顶点加入到拓扑排序的最前端。

17 深度优先排序

18 拓扑排序的实现 有向图采用邻接表实现，顶点表采用顺序存储，邻接表采用链式存储。
typedef int Vertex; template <int graph_size> class Graph { int count; //顶点数 List< Vertex> neighbors[graph_size]; //邻接表 void recursive_depth_sort(Vertex v, bool visited[], List<Vertex>& topological_order); public: void depth_sort(List<Vertex>& topological_order); void breadth_sort(List<Vertex>& topological_order); };

19 深度优先排序的实现 template <int graph_size> void Graph<graph_size>::depth_sort(List<Vertex>& topological_order){ bool visited[graph_size]; Vertex v; for (v=0; v<count; v++) visited[v]=false; topological_order.clear(); for(v=0; v<count; v++) if (!visited[v]) recursive_depth_sort(v,visited, topological_order); }

20 深度优先排序的实现 template <int graph_size> void Graph<graph_size>:: recursive_depth_sort(Vertex v, bool *visited, List<Vertex>& topological_order) { visited[v]=true; int degree = neighbors[v].size(); for (int i=0; i<degree; i++) { Vertex w; neighbors[v].retrieve(i,w); if (!visited[w]) recursive_depth_sort(w,visited, topological_order); } topological_order.insert(0,v); }

21 宽度优先排序 宽度优先排序 （1）正向产生拓扑排序，首先产生拓扑排序中第一个顶点， 最后产生拓扑排序中最后一个顶点。 （2）找一个没有前趋的顶点并将其作为拓扑排序的第一个顶点。 （3）只有当一个顶点的所有前趋顶点已经全部加入拓扑排序后，才可把该顶点加入到拓扑排序的最后端。 用一个数组记录图中每个顶点的前趋的个数 int predecessor_count[graph_size];

22 宽度优先排序

23 宽度优先排序 template <int graph_size> void Graph<graph_size>::breadth_sort(List<Vertex>& topological_order){ topological_order.clear(); Vertex v, w; int predecessor_count[graph_size]; for (v=0; v<count; v++) predecessor_count[v]=0; for (v=0; v<count; v++) for (int i=0; i<neighbors[v].size(); i++) { neighbors[v].retrieve(i,w); predecessor_count[w]++; } Queue ready_to_process; for (v=0; v<count; v++) if (predecessor_count[v]==0) ready_to_process.append(v); while( !ready_to_process.empty()) { ready_to_process.retrieve(v); topological_order.insert(topological_order.size(), v); for (int j=0; j<neighbors[v].size(); j++) { neighbors[v].retrieve(j,w); predecessor_count[w]--; if (predecessor_count[w]==0) ready_to_process.append(w); } ready_to_process.serve(); } }

24 最短路径 最短路径通常是针对有向网络而言的。即边上带有权值的有向图。
假定G是一个有向网络，每条边上带有一个非负的权值，则从顶点v到顶点w的最短路径指的是从顶点v到顶点w的所有路径中权值之和最小的路径。顶点v称做源点，顶点w称做终点。

25 最短路径 顶点0和顶点1之间的最短路径是哪条路径? 怎样快速求出从某给定源点到其它顶点间的最短路径?

26 最短路径 Dijkstra算法 依最短路径的长度递增的次序求得各条路径。 设置一个集合S，该集合中存放从给定源点出发最短路径已知的所有顶点。
因此算法开始时，集合S中只有源点一个顶点。随着算法的进行，其余的顶点被逐步加入集合S。因此算法要解决的问题是确定每步应该加入哪个顶点？ 设定一个数组 int distance[graph_size]; 记录从源点到其它顶点的距离。

27 最短路径 若顶点v已在S中，则distance[v]记录了从源点到顶点v的最短距离。
若顶点v还未加入S中，则distance[v]记录了从源点到某个S中的顶点w的最短距离加上边<w,v>的权值。 distance数组的初始化。 (1)若从源点邻接到顶点v(有边的情况)，则distance[v]即为该边的权值。 (2)否则(无边的情况)，则distance[v]为无穷大。 算法进行时，从distance中找一个最小值，并将其对应的顶点加入到S中。

28 最短路径 一旦某顶点v加入S，则重新计算尚未加入S的顶点所对应的数组distance元素值。更新规则为： 若distance[w] > distance[v]+weight(<v,w>)，令 distance[w] = distance[v]+weight(<v,w>) 如此循环往复，直到把所有顶点加入S。

29 最短路径

30 Dijkstra算法的实现 有向网络用邻接矩阵实现。
template <class Weight, int graph_size> class Graph { int count; Weight adjacency[graph_size][graph_size]; public: void set_distances(Vertex source, Weight distance[]) const; };

31 Dijkstra算法的实现 template <class Weight, int graph_size> void Graph<Weight,graph_size>::set_distances(Vertex source, Weight distance[]) const { Vertex v,w; bool found[graph_size];//集合S for (v=0; v<count; v++) { found[v]=false; distance[v]=adjacency[source][v]; } found[source]=true;distance[source]=0; for (int i=0; i<count; i++ ) { Weight min=infinity;//numeric_limits<int>::max(); for (w=0; w<count; w++) if (!found[w]) if ( distance[w]<min) {v=w; min=distance[w];} found[v]=true; for (w=0; w<count; w++) if (!found[w]) if (min+adjacency[v][w] < distance[w]) distance[w]= min+adjacency[v][w]; } }

32 上机作业 在机器上用C++分别实现和图状结构有关的算法。 想一想为什么用Dijkstra算法可以求出最短路径？