Chapter12 Graphs Definitions Applications Properties The ADTs Graph and Digraph Representation of Graphs and Digraphs Representation of Networks Class Definitions Graph Iterators Graph Search Methods 2/22/2019

本章重点 图的基本概念 图的搜索 2/22/2019

逻辑结构 线性结构 层次结构 网状结构 2/22/2019

12.1图的基本概念 简单地说，图(graph)是一个用线或边连接在一起的顶点或节点的集合。 图G=(V,E) 是一个V和E的有限集合，元素V称为顶点(vertice, 也叫作节点或点)，元素E称为边(edge, 也叫作弧或连线)，E中的每一条边连接V中两个不同的顶点。 可以用(i，j)来表示一条边，其中i 和j 是E所连接的两个顶点。 2/22/2019

例 2/22/2019

例 2/22/2019

有向边/无向边 带方向的边叫有向边(directed edge)，而不带方向的边叫无向边(undirected edge)。 对无向边来说，(i, j) 和(j, i) 是一样的；而对有向边来说，它们是不同的。前者的方向是从i 到j，后者是从j 到i。 2/22/2019

关联/邻接 当且仅当(i, j) 是图中的边时，顶点i 和j 是邻接的(adjacent)。边(i, j) 关联(incident)于顶点i 和j。 2/22/2019

例-邻接，关联 2/22/2019

关联/邻接 在有向图中，有时候对邻接和关联的概念作更精确的定义非常有用。 有向边(i, j) 是关联至（incident to）顶点j 而关联于（incident from）顶点i。顶点i 邻接至（adjacent to）顶点j，顶点j邻接于（adjacent from）顶点i。 对于无向图来说，“至”和“于”的含义是相同的。 2/22/2019

无向图/有向图 如果图中所有的边都是无向边，那么该图叫作无向图(undirected graph)。 有向边也成为弧。 2/22/2019

观察 由定义知道，一个图中不可能包括同一条边的多个副本，因此，在无向图中的任意两个顶点之间，最多只能有一条边。在有向图中的任意两个顶点之间，最多只能有一条边从顶点i到顶点j或从j到i。 并且一个图中不可能包含自连边(self-edge)，即(i,i)类型的边，自连边也叫作环(loop)。 2/22/2019

图的基本概念 通常把无向图简称为图，有向图仍称为有向图(digraph)。 在一些图和有向图的应用中，会为每条边赋予一个权或耗费，这种情况下，用术语加权有向图(weighted graph)和加权无向图(weighted digraph)来描述所得到的数据对象。 2/22/2019

网络 术语网络(network)是指一个加权有向图或加权无向图。 2/22/2019

7 2 5 B 10 9 60 40 1 12 80 8 A C 6 3 7 30 75 6 35 15 6 3 D E 4 7 45 16 2/22/2019

路径 当且仅当对于每一个j(1≤j≤k)，边(ij,ij+1)都在E中时，顶点序列P=i1 , i2 ,…, ik 是图或有向图G= (V, E)中一条从i1 到ik 的路径。 2/22/2019

街道例 2/22/2019

例 在图12-2b的有向图中，5，2，1是从5到1的一条路径，在这个有向图中，从5到4之间没有路径。 2/22/2019

简单路径 简单路径是这样一条路径：除第一个和最后一个顶点(起点和终点)以外，路径中其他所有顶点均不同。 例：路径5,2,1是简单路径，而2,5,2,1则不是。 2/22/2019

环路(回路) 环路(cycle)的起始节点与结束节点是同一节点。 简单路径组成的回路称为简单回路。 2/22/2019

路径长度 对于图或有向图的每一条边，均可以给出一个长度。 路径的长度是路径上所有边的长度之和。对不带权的图，路径长度是指路径上边的数目；对带权的图，路径长度是指路径上各条边的权值之和。 从i 到j 的最短路径是相应网络中顶点i 到j 的最短路径。 2/22/2019

连通图 设G= (V,E)是一个无向图，当且仅当G中每一对顶点之间有一条路径时，可认为G是连通的(connected)。 2/22/2019

强连通图 在有向图中，若任意两个顶点间均有路径存在，则称其为强连通图，否则称为非强连通图。 2/22/2019

观察 假设G是连通的，G中的有些边可能不是必需的，因此即使将它从G中去掉，G仍然可以保持连通。 2/22/2019

子图 图H是图G的子图(subgraph)的充要条件是，H的顶点和边的集合是G的顶点和边的集合的子集。 2/22/2019

生成树 没有环路的无向连通图是一棵树。 一棵包含G中所有顶点并且是G的子图的树是G的生成树(spanning tree)。 2/22/2019

生成树 2/22/2019

生成树 一个n节点的连通图必须至少有?条边。 因此当通信网络的每条链路具有相同的建造费用时，在任意一棵生成树上建设所有的链路可以将网络建设费用减至最小，并且能保证每两个城市之间存在一条通信路径。 如果链路具有不同的耗费，那么需要在一棵最小耗费生成树(生成树的耗费是所有边的耗费之和)上建立链路。 2/22/2019

生成树 2/22/2019

例 会议，此次大会上的所有发言人都只会说英语，而参加会议的其他人说的语言是{L1,L2,…,Ln}之一。翻译小组能够将英语与其他语言互译。 2/22/2019

二分图 可以将顶点集合分成两个子集A和B，这样每条边在A中有一个端点，在B中有一个端点，具有这种特征的图叫作二分图(bipartite graph) 2/22/2019

覆盖 当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A‘ 覆盖集合B（或简单地说，A’ 是一个覆盖）。 在二分图中寻找最小覆盖的问题为二分覆盖(bipartite-cover)问题。 2/22/2019

二分覆盖 二分覆盖问题是N P-复杂问题。 可以利用贪婪算法寻找一种快速启发式方法。 一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。 2/22/2019

顶点的度 设G是一个无向图，顶点i 的度(degree)di 是与顶点i 相连的边的个数。 d1,d2,d3,d4? 2/22/2019

12.3性质 特性1 设G= (V, E)是一个无向图，令|V| =n, |E|=e, di为顶点i的度，则 2/22/2019

完全图 一个具有n 个顶点， n(n-1)/2条边的图是一个完全图(complete graph)。 任意两个顶点均邻接。 2/22/2019

完全图 2/22/2019

入度和出度 设G是一个有向图，顶点i 的入度(in-degree)diin 是指关联至顶点i 的边的数量。顶点i 的出度(out-degree)diout 是指关联于该顶点的边的数量。 入度和出度在无向图中可以作为度的同义词。 2/22/2019

顶点的度 与顶点相关联的边的数目。 有向图顶点的度还有入度与出度之分：顶点的入度即以该顶点为终点的边的数目；顶点的出度即以该顶点为始点的边的数目。 2/22/2019

性质 特性2 设G= (V,E)是一个有向图，令|V| =n, |E|=e, 则 2/22/2019

完全有向图 一个n 顶点的完全有向图(complete digraph)包含n (n- 1 )条有向边 2/22/2019

完全有向图 2/22/2019

思考 设G是任意无向图，度数为奇数的顶点。有偶数个还是奇数个？ 2/22/2019

强连通有向图 一个有向图是强连通( strongly connected)的充要条件是：对于每一对不同顶点i 和j，从i 到j 和从j 到i 都有一个有向路径。 1) 对于每一个n（n≥2），都存在一个包含n 条边的强连通有向图。 2) 每一个n（n≥2）顶点的强连通有向图至少包含n 条边。 2/22/2019

12.5无向图和有向图的描述 无向图和有向图最常用的描述方法都是基于邻接的方式： 邻接矩阵 邻接压缩表 邻接链表 2/22/2019

邻接矩阵 一个n顶点的图G= (V,E)的邻接矩阵(adjacency matrix)是一个n×n矩阵A，A中的每一个元素是0或1。假设V={1, 2, ..., n}。如果G是一个无向图，那么A中的元素定义如下： 2/22/2019

邻接矩阵 如果G是有向图，那么A中的元素定义如下： 2/22/2019

例 2/22/2019

例-邻接矩阵 2/22/2019

结论 2/22/2019

邻接矩阵->数组 使用映射A(i,j)=a[i][j]可以将n×n的邻接矩阵映射到一个(n+1)×(n+1)的整型数组a中。 如果sizeof(int)等于2个字节，映射的结果需要2(n+1)2字节的存储空间。 另一种方法是，采用n×n数组a[n][n]和映射A(i,j)=a[i-1][j-1]。这种映射需要2n2字节，比前一种减少了4n+2个字 2/22/2019

邻接矩阵->数组 对于无向图，邻接矩阵是对称的，因此只需要存储上三角(或下三角)的元素，所需空间仅为(n2-n)/2位。 2/22/2019

邻接矩阵-时间需求 使用邻接矩阵时，需要用Θ(n)时间来确定邻接至或邻接于一个给定节点的集合，或寻找关联的边数。另外，增加或删除一条边需要Θ(1)时间。 2/22/2019

邻接链表 在邻接链表(linked-edjacency-list)中，邻接表是作为链表保存的，可以用类Chain<int>来实现。 可使用一个Chain<int> 类型的头节点数组h 来跟踪这些邻接表。h[i].first 指向顶点i 的邻接表中的第一个节点。如果x 指向链表h[i] 中的一个节点，那么(i, x→data) 是图中的一条边。 2/22/2019

例 2/22/2019

例 2/22/2019

例 2/22/2019

邻接链表-时间需求 假设每个指针和整数均为2字节长，则一个n顶点图的邻接链表所需要的空间为2(n+m+1)，其中对于无向图，m=2e；而对于有向图，m=e。 邻接链表便于进行边的插入和删除操作。确定邻接表中顶点的数目所需要的时间与表中顶点的数目成正比。 2/22/2019

网络描述 将图和有向图的描述进行简单扩充就可得到网络的描述 2/22/2019

网络-邻接矩阵描述 用一个矩阵C来描述耗费邻接矩阵(cost-adjacency-matrix)。 如果A(i,j)是1，那么C(i,j)是相应边的耗费(或权)；如果A(i,j)是0，那么相应的边不存在，C(i,j)等于某些预置的值NoEdge。 选择NoEdge是为了便于区分边是否存在。一般来说，NoEdge的值被设为无穷大。 2/22/2019

12.7邻接矩阵类的设计 AdjacencyWDigraph AdjacencyWGraph AdjacencyDigraph AdjacencyGraph 2/22/2019

邻接链表类的设计 LinkedBase LinkedDigraph LinkedWDigraph LinkedGraph LinkedWGraph 2/22/2019

分析 加权有向图和无向图的链表节点中有一个权值域，而无权有向图和无向图中则没有。 2/22/2019

加权有向图的耗费邻接矩阵 template<class T> class AdjacencyWDigraph{ friend AdjacencyWGraph<T>; public: AdjacencyWDigraph(int Vertices=10,T noEdge=0); ~AdjacencyWDigraph(){Delete2DArray(a,n+1);} bool Exist(int i,int j)const; int Edges()const{return e;} int Vertices()const{return n;} AdjacencyWDigraph<T>& Add(int i,int j,constT& w); AdjacencyWDigraph<T>& Delete(int i,int j); int OutDegree(int i)const; int InDegree(int i)const; 2/22/2019

加权有向图的耗费邻接矩阵 private: T NoEdge;//用于没有边存在的情形 int n;//顶点数目 int e;//边数 T **a;//二维数组 }; 2/22/2019

Chain的描述 2/22/2019

增加删除方法 2/22/2019

邻接链表基类描述 2/22/2019

有向图的链表描述 2/22/2019

2/22/2019

12.8图的遍历 不论采用哪一种图类编写应用程序，都需要沿着矩阵的一行或多行向下移动，或者沿着一个或多个链表向下移动，实现这种移动的函数称为遍历器(iterator)。 邻接矩阵的遍历函数。 邻接链表的遍历函数。 2/22/2019

遍历函数 Begin(i) 对于邻接表，返回顶点i 所对应表中的第一个顶点；对于邻接矩阵，返回邻接于顶点i 的最小（即第一个）顶点。在两种情况中，如果没有邻接顶点，都将返回零值。 NextVertex(i) 返回顶点i 对应邻接表中的下一个顶点或返回邻接于顶点i的下一个最小顶点。同样，当没有下一个顶点时函数返回零。 InitializePos( ) 初始化用来跟踪每一个邻接表或(耗费)邻接矩阵每一行中当前位置的存储配置。 DeactivatePos( ) 取消InitializePos( )所产生的存储配置。 2/22/2019

邻接矩阵的遍历函数 作为AdjacencyWDigraph类的一个共享函数来加以实现。 私有成员int *pos 用来记录每一行中的位置。 2/22/2019

邻接矩阵的遍历函数 void InitializePos() {pos = new int [n+1];} void DeactivatePos() {delete [] pos;} template<class T> int AdjacencyWDigraph<T>::Begin(int i) { / /返回第一个与顶点i邻接的顶点 if (i < 1 || i > n) throw OutOfBounds(); // 查找第一个邻接顶点 for (int j = 1; j <= n; j++) if (a[i][j] != NoEdge) {// j 是第一个 pos[i] = j; return j;} pos[i] = n + 1; // 没有邻接顶点 return 0; } 2/22/2019

邻接矩阵的遍历函数 template<class T> int AdjacencyWDigraph<T>::NextVertex(int i) {// 返回下一个与顶点i邻接的顶点 if (i < 1 || i > n) throw OutOfBounds(); // 寻找下一个邻接顶点 for (int j = pos[i] + 1; j <= n; j++) if (a[i][j] != NoEdge) {// j 是下一个顶点 pos[i] = j; return j;} pos[i] = n + 1; // 不存在下一个顶点 return 0; } 2/22/2019

邻接链表的遍历函数 LinkedBase类: ChainIterator<T> *pos； void InitializePos() {pos = new ChainIterator<T> [n+1];} void DeactivatePos() {delete [] pos;} 2/22/2019

邻接链表的遍历函数 int LinkedDigraph::Begin(int i) {// 返回第一个与顶点i邻接的顶点 if (i < 1 || i > n) throw OutOfBounds(); int *x = pos[i].Initialize(h[i]); return (x) *x : 0; } 2/22/2019

邻接链表的遍历函数 int LinkedDigraph::NextVertex(int i) {// 返回下一个与顶点i邻接的顶点 if (i < 1 || i > n) throw OutOfBounds(); int *x = pos[i].Next(); return (x) *x : 0; } 2/22/2019

链接加权有向图的遍历函数 template<class T> int LinkedWDigraph<T>::Begin(int i) {// 返回第一个与顶点i邻接的顶点 if (i < 1 || i > n) throw OutOfBounds(); GraphNode<T> *x = pos[i].Initialize(h[i]); return (x) x->vertex : 0; } int LinkedWDigraph<T>::NextVertex(int i) {// 返回下一个与顶点i邻接的顶点 GraphNode<T> *x = pos[i].Next(); 2/22/2019

12.9抽象类Network class Network { public: virtual int Begin(int i) = 0; virtual int NextVertex(int i) = 0; virtual void InitializePos() = 0; virtual void DeactivatePos() = 0; } ; 2/22/2019

12.10图的操作 寻找路径，寻找生成树，判断无向图是否连通。 许多函数都要求从一个给定的顶点开始，访问能够到达的所有顶点。(当且仅当存在一条从v 到u 的路径时，顶点v 可到达顶点u。) 2/22/2019

图的搜索算法 搜索这些顶点的两种标准方法是 宽度优先搜索 深度优先搜索 2/22/2019

搜索 判断从顶点1出发可到达的所有顶点? 2/22/2019

宽度优先搜索 从一个顶点开始，识别所有可到达顶点的方法叫作宽度优先搜索(Breadth -FirstSearch, BFS)。 这种搜索可使用队列来实现。 2/22/2019

宽度优先搜索 2/22/2019

宽度优先搜索 //从顶点v 开始的宽度优先搜索 把顶点v标记为已到达顶点； 初始化队列Q，其中仅包含一个元素v; while (Q不空) { 令u 为邻接于w 的顶点; while (u) { if ( u 尚未被标记) { 把u 加入队列； 把u 标记为已到达顶点； } u = 邻接于w 的下一个顶点； } 2/22/2019

观察 BFS的执行方式与是否正在处理一个图、有向图、加权图或加权有向图无关，也与所使用的描述方法无关。 为了实现语句：u=邻接于w的下一个顶点； 必须知道当前正在使用的图类。 通过把BFS函数作为Network类的一个成员函数以及利用图遍历器从一个邻接顶点到达下一个顶点，可以避免为每种图类分别编写不同的代码。 2/22/2019

BFS的实现代码 void Network::BFS(int v,int reach[],int label) {//宽度优先搜索 //初始时对于所有顶点有reach[i]=0并且label≠0 LinkedQueue<int> Q; InitializePos();//初始化图遍历器数组 reach[v]=label; Q.Add(v); while(!Q.IsEmpty()){ int w; Q.Delete(w);//获取一个已标记的顶点 2/22/2019

BFS的实现代码 int u=Begin(w); while(u){//访问w的邻接顶点 if(!reach[u]){//一个未曾到达的顶点 Q.Add(u); reach[u]=label;}//标记已到达该顶点 u=NextVertex(w);//下一个与w邻接的顶点 } DeactivatePos();//释放遍历器数组 2/22/2019

深度优先搜索 深度优先搜索(Depth-First Search, DFS):从顶点v 出发，首先将v 标记为已到达顶点，然后选择一个与v 邻接的尚未到达的顶点u，如果这样的u 不存在，搜索中止。假设这样的u 存在，那么从u 又开始一个新的DFS。当从u 开始的搜索结束时，再选择另外一个与v 邻接的尚未到达的顶点，如果这样的顶点不存在，那么搜索终止。而如果存在这样的顶点，又从这个顶点开始DFS，如此循环下去。 2/22/2019

DFS的实现代码 voidNetwork::DFS(int v,int reach[],int label) {//深度优先搜索 InitializePos();//初始化图遍历器数组 dfs(v,reach,label);//执行dfs DeactivatePos();//释放图遍历器数组 } 2/22/2019

dfs的实现代码 voidNetwork::dfs(int v,int reach[],int label) {//实际执行深度优先搜索的代码 reach[v]=label; int u=Begin(v); while(u){//u邻接至v if(!reach[u]) dfs(u,reach,label); u=NextVertex(v);} } 2/22/2019

例 从顶点1开始的深度优先搜索? 2/22/2019

应用 寻找路径(Finding a Path ) 连通图及其构件(Connected Graphs and Components) 生成树(Spanning Trees) 2/22/2019

寻找路径 若从顶点v 开始搜索(宽度或深度优先)且到达顶点w 时终止搜索，则可以找到一条从顶点v 到达顶点w 的路径。 要实际构造这条路径，需要记住从一个顶点到下一个顶点的边。 2/22/2019

在图中寻找一个路径 bool Network::FindPath (int v, int w, int &length, int path[]) {// 寻找一条从v 到w的路径, 返回路径的长度，并将路径存入数组path[ 0 : l e n g t h ] / /如果不存在路径，则返回false / /路径中的第一个顶点总是v path[0] = v; length = 0; // 当前路径的长度 if (v == w) return true; / /为路径的递归搜索进行初始化 int n = Vertices( ) ; InitializePos(); // 遍历器 2/22/2019

在图中寻找一个路径 int *reach = new int [n+1]; for (int i = 1; i <= n; i++) reach[i] = 0; bool x = findPath(v, w, length, path, reach); DeactivatePos( ) ; delete [] reach; return x; } 2/22/2019

在图中寻找一个路径 bool Network::findPath(int v, int w, int &length, int path[], int reach[]) {// 实际搜索v到w的路径，其中v != w. // 按深度优先方式搜索一条到达w的路径 reach[v] = 1; int u = Begin(v); while (u) { if (!reach[u]) { length++; path[length] = u; // 将u 加入p a t h if (u == w) return true; if (findPath(u, w, length, path, reach)) return true; // 不存在从u 到w的路径 length--; //删除u } u = NextVertex(v) ; } return false; } 2/22/2019

连通图及其构件 通过从任意顶点开始执行D F S或B F S，并且检验所有顶点是否被标记为已到达顶点，可以判断一个无向图G是否连通。 2/22/2019

确定无向图是否连通 class Undirected : virtual public Network { public: bool Connected(); } ; 2/22/2019

确定无向图是否连通 bool Undirected::Connected() {// 当且仅当图是连通的，则返回true int n = Ve r t i c e s ( ) ; // 置所有顶点为未到达顶点 int *reach = new int [n+1]; for (int i = 1; i <= n; i++) reach[i] = 0; // 对从顶点1出发可到达的顶点进行标记 DFS(1, reach, 1); // 检查是否所有顶点都已经被标记 if (!reach[i]) return false; return true; } 2/22/2019

构件 从顶点i 可到达的顶点的集合C与连接C中顶点的边称为连通构件(connected component)。 在构件标识问题( component-labeling problem)中，对图中的顶点进行标识，当且仅当2个顶点属于同一构件时，分配给它们相同的标号。 2/22/2019

构件 可以通过反复调用D F S或B F S算法来标识构件。从每一个尚未标识的顶点开始进行搜索，并用新的标号标识新到达的顶点。 2/22/2019

构件标识 2/22/2019

生成树 在一个n 顶点的连通无向图中，如果从任一个顶点开始进行BFS，所有顶点都将被加上标记。 由于所得到的边的集合中包含一条从v 到图中其他每个顶点的路径，因此它构成了一个连通子图，该子图即为G的生成树。 2/22/2019

生成树 宽度优先生成树:按B F S所得到的生成树 深度优先生成树:按D F S所得到的生成树 2/22/2019

宽度优先生成树 2/22/2019

深度优先生成树 {(1,3),(3,5),(5,2),(5,8),(8,7),(7,4),(4,6)} 2/22/2019

第十二章 总结 图的基本概念 图的存储 图的遍历 路径、生成树 2/22/2019