算法与数据结构第16章 图

1、 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures第16章 图1 16.1 图的基本概念 16.2 抽象数据类型图 16.3 图的表示法 16.4 用邻接矩阵实现图 16.5 用邻接表实现图 16.6 用邻接矩阵实现赋权图 16.7 用邻接表实现赋权图16.8 图的遍历搜索算法2011-6-3福州大学数学与计算机科学学院1 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures学习要点:

2、 理解图的定义和与图相关的有向图、无向图、赋权图、连通图等术语。 理解图是一个表示复杂非线性关系的数据结构。 掌握图的邻接矩阵表示及其实现方法。 掌握图的邻接表表示及其实现方法。 了解图的紧缩邻接表表示方法。 掌握图的广度优先搜索方法。 掌握图的深度优先搜索方法。 掌握单源最短路径问题的Dijkstra算法。 掌握所有顶点对之间最短路径问题的Floyd算法。 掌握构造最小支撑树的Prim算法。 掌握构造最小支撑树的Kruskal算法。 理解图的最大匹配问题的增广路径算法。2011-6-3福州大学数学与计算机科学学院2 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorit

3、hms andand DataData StructuresStructures16.1 图的基本概念 图(Graph)图G是由两个集合V(G)和E(G)组成 记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对 有向图有向图G是由两个集合V(G)和E(G)组成其中：V(G)是顶点的非空有限集E(G)是有向边的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为有向边的起点，w为有向边的终点 无向图无向图G是由两个集合V(G)和E(G)组成其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v

4、,w)=(w,v)本书约定：不考虑顶点到其自身的边；不允许一条边在图中重复出现。即只讨论简单图。2011-6-3福州大学数学与计算机科学学院3 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures例2 4513 6G1图G1中：V(G1)=1,2,3,4,5,6E(G1)=, , , , , , 例1573246G2图G2中：V(G2)=1,2,3,4,5,6,7E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)2011-6-3福州大学数

5、学与计算机科学学院4 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures 完全图设|V|=n,|E|=e。对有向图G，若e=n(n-1)，则称G为完全的有向图；对无向图G，若e=n(n-1)/2，则称G为完全的无向图。 邻接、关联若(u,v)是一条无向边，则称顶点u和v互为邻接点，或称u和v相邻接；并称边(u,v)关联于顶点u和v，或称边(u,v)与顶点u和v相关联。若(u,v)是一条有向边，则称v是u的邻接顶点；并称边(u,v)关联于顶点u和v，或称边(u,v)与顶点u和v相关联。 顶点

6、的度 无向图中，顶点v的度为关联于该顶点相连的边数，记为D(v) 有向图中，顶点v的度分成入度与出度 入度：以顶点v为终点的边的数目，记为ID(v) 出度：以顶点v为起点的边的数目，记为OD(v) D(v)=ID(v)+OD(v)无论是有向图还是无向图，顶点数n，边数e和度数之间有如下关系：1ne = D (vi )2i =12011-6-3福州大学数学与计算机科学学院5 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures子图如果图G(V,E)和图G(V,E),满足：VVEE则称G为G的子

7、图有向图G1的若干子图无向图G2的若干子图2011-6-3福州大学数学与计算机科学学院6 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures路径：在无向图G中，若存在一个顶点序列u(1),u(2),，u(m),使得(u(i),u(i+1)E(G)，i=1,2,，m-1,则称该顶点序列为顶点u(1)和u(m)之间的一条路径。其中u(1)称为该路径的起点，u(m)称为该路径的终点。若图G是有向图，则路径也是有向的，其中每条边(u(i),u(i+1)，i=1,2,，m-1均为有向边。路径的长度：

8、路径所包含的边数m-1称之。 简单路若一条路径上除了起点和终点可能相同外，其余顶点均不相同，则称此路径为一条简单路径。 回路起点和终点相同的简单路径称为简单回路或简单环或圈。 有根图在一个有向图中，若有一个顶点v，从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图。v称为该有根图的根。2011-6-3福州大学数学与计算机科学学院7 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures连通无向图G中，若从顶点V到顶点W有一条路径，则说V和W是连通的连通图无向图中任意两个顶点都是连通的

9、叫连通图 连通分支无向图的极大连通子图叫连通分支下图有两个连通分支：2011-6-3福州大学数学与计算机科学学院8 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures强连通图有向图中，如果对每一对Vi,VjV, ViVj, 从Vi到Vj 和从Vj到 Vi都存在路径，则称G是强连通图 强连通分支有向图的极大强连通子图叫强连通分支显然，强连通图只有一个强连通分支，即其自身。非强连通的有向图有多个强连通分支。如下图中的图不是强连通图，但它有2个强连通分支。2011-6-3福州大学数学与计算机科学

10、学院9 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures 赋权图和网络若无向图的每条边都带一个权，则称相应的图为赋权无向图。同理，若有向图的每条边都带一个权，则称相应的图为赋权有向图。通常，权是具有某种实际意义的数，比如，2个顶点之间的距离，耗费等。赋权无向图和赋权有向图统称为网络。下图就是一个网络的例子。2011-6-3福州大学数学与计算机科学学院10 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData Structure

11、sStructures16.2 抽象数据类型图ADT图支持的基本运算以有向图为基本模型。ADT图支持的基本运算如下： (1) create(n): 创建n个孤立顶点的图。 (2) exist(i,j): 判断边(i,j)是否存在。 (3) e(): 返回图的边数。 (4) v(): 返回图的顶点数。 (5) insert(i,j): 在图中加入边(i,j)。 (6) erase(i,j): 删除边(i,j)。 (7) degout(i): 返回顶点i的出度。 (8) degin(i): 返回顶点i的入度。2011-6-3福州大学数学与计算机科学学院11 算算 法法 与与 数数 据据 结结 构构

12、 AlgorithmsAlgorithms andand DataData StructuresStructures16.3 图的表示法16.3.1邻接矩阵表示顶点间邻接关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵1, 若(v , v )或 E(G)Ai, j = ijij2011-6-3福州大学数学与计算机科学学院12例 1 23 4G1例12345G2 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures 01100000 0001000 1

13、 0101010101 01011 10100110 00 2011-6-3福州大学数学与计算机科学学院13 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures2011-6-3福州大学数学与计算机科学学院14 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的

14、有向图需存储空间为n 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中： 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和 网络的邻接矩阵可定义为：w ,若(v , v )或 E(G)Ai, j = ijijij2011-6-3福州大学数学与计算机科学学院15 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures例15273512416342 573548721426816 3 2011-6-3福州大学数学与计算机科学学院16 算算 法法 与与 数

15、数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.3.2邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表存放顶点Vi的所有邻接顶点。2011-6-3福州大学数学与计算机科学学院17 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures2011-6-3福州大学数学与计算机科学学院18 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataDat

16、a StructuresStructures2011-6-3福州大学数学与计算机科学学院19算法与数据结构 算 法 与 数 据 结 构 Algorithms and Data StructuresAlgorithms and Data Structures特点无向图中顶点Vi的度为第i个单链表中的结点数求解麻有向图中烦！顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为终点的边的单链表例1213314422011-6-3福州大学数学与计算机科学学院20 算算 法法 与与 数数 据据 结结 构构 Algorith

17、msAlgorithms andand DataData StructuresStructures16.3.3紧缩邻接表紧缩邻接表将图G的每个顶点的邻接表紧凑地存储在2个一维数组List和h中。其中一维数组List依次存储顶点1,2,n的邻接顶点。数组单元hi存储顶点i的邻接表在数组List中的起始位置。如图G2和G1的紧缩邻接表表示分别如下图(a)和(b)：2011-6-3福州大学数学与计算机科学学院21 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures2011-6-3福州大学数学与计

18、算机科学学院22 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.4用邻接矩阵实现图16.4.1 用邻接矩阵实现图的方法从图的结构和概念上看，可将图分为有向赋权图、无向赋权图、有向图和无向图4种不同类型。在上述4种不同类型的图中，有向赋权图具有较一般的特征。 struct edge int u,v; / 与边关联的个顶点edge(int u=-1,int v=-1):u(u),v(v) / 构造函数;2011-6-3福州大学数学与计算机科学学院23 算算 法法 与与 数数 据据 结

19、结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures用邻接矩阵表示的图类adj_graph描述如下： class adj_graph public:#include “giter.h”/图顶点迭代器typedef edge E;/ 边类型adj_graph(int n,bool dir);/ 构造函数void insert(E e);/ 插入边void erase(E e);/ 删除边bool exist(E e)const;/ 存在边 private:int vn,en; / vn顶点数en边数bool dir;/ 有向

20、图标志vectorvector a;/ 邻接矩阵 ;2011-6-3福州大学数学与计算机科学学院24 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures插入边 void adj_graph:insert(E e) / 插入边int u=e.u,v=e.v;if(u0|v=vn|v=vn|u=v)throw bad_input();if(!auv) en+;else return;/ 边已存在auv=true;/ 加入边(u,v)if(!dir)avu=true;/ 对于无向图还要加入边(v

21、,u)2011-6-3福州大学数学与计算机科学学院25 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures删除边 void adj_graph:erase(E e) / 删除边int u=e.u,v=e.v;if(u0|v=vn|v=vn|u=v)throw bad_input();if(auv) en-;else return;/ 边不存在则返回auv=false;/ 删除边(u,v)if(!dir)avu=false;/ 对于无向图还要删除边(v,u)2011-6-3福州大学数学与计算

22、机科学学院26 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures存在边 bool adj_graph:exist(E e)const / 存在边int u=e.u,v=e.v;if (u0|v=vn|v=vn|u=v)return false;return auv;2011-6-3福州大学数学与计算机科学学院27 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.4.2邻接矩阵

23、图的顶点迭代器 struct graph_iterator / 图顶点迭代器typedef graph_iterator iterator;/ 图顶点迭代器类型typedef graph_iterator const_iterator;/ 图顶点迭代器类型int i,j;/ 当前访问的顶点adj_graph *g;/ 图graph_iterator() / 构造函数graph_iterator(adj_graph *g,int i,int j=-1):g(g),i(i),j(j)if(j0)next();int operator*()constreturn j; / 提领运算iterator&

24、 operator+()next();return *this;iterator operator+(int)iterator tmp=*this;next();return tmp;/ 实施递增运算void next()for(j+;jv();j+)if(g-aij = true) return;bool operator=(const graph_iterator& rhs)/ 判等运算return i=rhs.i & j=rhs.j; ;2011-6-3福州大学数学与计算机科学学院28 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand Da

25、taData StructuresStructures16.5用邻接表实现图16.5.1用邻接表实现图的方法 class link_graph public:typedef edge E;/ 边类型link_graph(int n,bool dir);/ 构造函数void insert(E e);/ 插入边void erase(E e);/ 删除边bool exist(E e);/ 存在边iterator begin(int i)return hi.begin();/ 指向表首顶点的迭代器iterator end(int i)return hi.end();/ 表尾顶点的下一顶点的迭代器 pr

26、ivate:int vn,en; / vn顶点数en边数bool dir;/ 有向图标志vectorlisth;/ 邻接表向量 ;2011-6-3福州大学数学与计算机科学学院29 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures插入边 void link_graph:insert(E e) / 插入边int u=e.u,v=e.v;if(u0|v=vn|v=vn|u=v)throw bad_input();if(!exist(e)en+;else return;/ 边已存在hu.push

27、_back(v);/ 加入边(u,v)if(!dir)hv.push_back(u);/ 对于无向图还要加入边(v,u)2011-6-3福州大学数学与计算机科学学院30 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures删除边 void link_graph:erase(E e) / 删除边int u=e.u,v=e.v;if(u0|v=vn|v=vn|u=v)throw bad_input();if(exist(e)en-;else return;/ 边不存在则返回hu.remove(v

28、);/ 删除边(u,v)if(!dir)hv.remove(u);/ 对于无向图还要删除边(v,u)2011-6-3福州大学数学与计算机科学学院31 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures存在边 bool link_graph:exist(E e) / 存在边int u=e.u,v=e.v;if(u0|v=vn|v=vn|u=v)return false;for(iterator it=begin(u);it !=end(u);it+)if(*it=v)return true;

29、return false;2011-6-3福州大学数学与计算机科学学院32 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.5.2邻接表图的顶点迭代器 typedef list:iterator iterator;/ 图顶点迭代器类型 typedef list:const_iterator const_iterator;/ 图顶点迭代器类型2011-6-3福州大学数学与计算机科学学院33 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andan

30、d DataData StructuresStructures16.6用邻接矩阵实现赋权图 用下面的结构来表示赋权图中各边的信息。 template struct wedgeT w; / 边权int u,v; / 与边关联的个顶点wedge() / 构造函数wedge(int u,int v,T w); / 构造函数bool operator(const wedge& a)constreturn w(const wedge& a)constreturn wa.w;2011-6-3福州大学数学与计算机科学学院34 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms

31、 andand DataData StructuresStructures16.6.1用邻接矩阵实现赋权图的方法 template class adj_weight_graph public:adj_weight_graph(int n,bool dir=false);/ 构造函数T& w(E* e)return e-w;/ 边权T& w(int u,int v)return auv-w;/ 边权T& w(iterator& it)return it-w;/ 边权void insert(E* e);/ 插入边void erase(E* e);/ 删除边bool exist(E* e)const

32、;/ 存在边 private:int vn,en; / vn顶点数en边数bool dir;/ 有向图标志vectorvector a;/ 邻接矩阵 ;2011-6-3福州大学数学与计算机科学学院35 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures插入边 template void adj_weight_graph:insert(E* e) / 插入边int u = e-u, v= e-v;if(u0|v=vn|v=vn|u=v)throw bad_input();if(!auv) e

33、n+;else return;/ 边已存在auv=e;/ 加入边(u,v)if(!dir)avu=e;/ 对于无向图还要加入边(v,u)2011-6-3福州大学数学与计算机科学学院36 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures删除边 template void adj_weight_graph:erase(E* e) / 删除边int u = e-u, v= e-v;if(u0|v=vn|v=vn|u=v)throw bad_input();if(auv) en-;else re

34、turn;/ 边不存在则返回auv=0;/ 删除边(u,v)if(!dir)avu=0;/ 对于无向图还要删除边(v,u)2011-6-3福州大学数学与计算机科学学院37 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures存在边 template bool adj_weight_graph:exist(E* e)const / 存在边int u = e-u, v= e-v;if(u0|v=vn|v=vn|u=v)return false;return(auv!=0);2011-6-3福州大

35、学数学与计算机科学学院38 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.6.2邻接矩阵赋权图的顶点迭代器 template struct wgraph_iterator / 赋权图顶点迭代器typedef typename wgraph_iterator iterator;/ 赋权图顶点迭代器typedef typename adj_weight_graph graph;/ 赋权图类型int i,j;/ 当前访问的顶点graph *g;/ 赋权图wgraph_iterator(

36、) / 构造函数wgraph_iterator(graph *g,int i,int j=-1):g(g),i(i),j(j)if(j()constreturn g-aij; / 边指针运算iterator& operator+()next();return *this; / 前置递增运算iterator operator+(int)iterator tmp=*this;next();return tmp; / 后置递增void next()for(j+;j v();j+)if(g-aij)return; / 实施递增运算 ;2011-6-3福州大学数学与计算机科学学院39 算算 法法 与与

37、数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.7用邻接表实现赋权图16.7.1 用邻接表实现赋权图的方法 template class link_weight_graph public:link_weight_graph(int n,bool dir=false);/ 构造函数T& w(E* e)return e-w;/ 边权T& w(int u,int v);/ 边权T& w(iterator& it)return it-w;/ 边权void insert(E* e);/ 插入边void era

38、se(E* e);/ 删除边bool exist(E* e);/ 存在边 private:int vn,en; / vn顶点数en边数bool dir;/ 有向图标志vectorlisth;/ 邻接表向量 ;2011-6-3福州大学数学与计算机科学学院40 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures插入边 template void link_weight_graph:insert(E* e) / 插入边int u=e-u,v=e-v;if(u0|v=vn|v=vn|u=v)thr

39、ow bad_input();if(!exist(e)en+;else return;/ 边已存在hu.push_back(e);/ 加入边(u,v)if(!dir)hv.push_back(e);/ 对于无向图还要加入边(v,u)2011-6-3福州大学数学与计算机科学学院41 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures删除边 template void link_weight_graph:erase(E* e) / 删除边int u=e-u,v=e-v;if(u0|v=vn|v

40、=vn|u=v)throw bad_input();if(exist(e)en-;else return;/ 边不存在则返回hu.remove(e);/ 删除边(u,v)if(!dir)hv.remove(e);/ 对于无向图还要删除边(v,u)2011-6-3福州大学数学与计算机科学学院42 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures存在边 template bool link_weight_graph:exist(E* e) / 存在边int u=e-u,v=e-v;if(u0

41、|v=vn|v=vn|u=v)return false;for(iterator it=begin(u);it !=end(u);it+)if(*it=v)return true;return false;2011-6-3福州大学数学与计算机科学学院43 算算 法法 与与 数数 据据 结结 构构 AlgorithmsAlgorithms andand DataData StructuresStructures16.7.2 邻接表赋权图的顶点迭代器 template struct lwgraph_iterator / 赋权图顶点迭代器typedef typename lwgraph_iterator iterator; / 赋权图顶点迭代器typedef typename link_weight_graph graph; / 赋权图类型typedef ty