《数据结构-C语言描述》课件第10章.ppt

1、第10章 图 第10章 图10.1 图的基本概念图的基本概念 10.2 图的存储结构图的存储结构 10.3 图的遍历图的遍历 10.4 拓扑排序和关键路径拓扑排序和关键路径 10.5 最小代价生成树最小代价生成树 10.6*最短路径最短路径 习题习题10 第10章 图 10.1 图的基本概念图的基本概念第10章 图 10.1.1 图的定义与术语图的定义与术语 图(graph)是数据结构G=(V，E)，其中V(G)是G中结点的有限非空集合，结点的偶对称为边(edge)，E(G)是G中边的有限集合。图中的结点常称为顶点(vertices)。若图中代表一条边的偶对是有序的，则称其为有向图(direc

2、ted graph)。用v1,v2代表有向图中的一条有向边，v1称为边的始点(尾tail)，v2称为边的终点(头head)。v1,v2和v2,v1这两个偶对代表不同的边。有向边也称为弧(arc)。第10章 图 图102 图的示例(a)无向图G1；(b)有向图G230142(a)40132(b)第10章 图 若图中代表一条边的偶对是无序的，则称其为无向图(undirected graph)。用(v1,v2)代表无向图中的边，这时(v1,v2)和(v2,v1)是同一条边。事实上，对任何一个有向图，若u,vE，必有v,uE，即E是对称的，则可以用一个无序对(u,v)代替这两个有序对，表示u 和v之间

3、的一条边，便成为无向图。图102中的G1是无向图，G2是有向图。图中：V(G1)=V(G2)=v0,v1,v2,v3,v4 E(G1)=(v0,v1),(v0,v2),(v0,v4),(v1,v2),(v2,v3),(v2,v4),(v3,v4)E(G2)=,第10章 图 如果边(vi,vi)或是允许的，这样的边称为自回路(self loop)，如图103(a)所示。两顶点间允许有多条相同边的图，称为多重图(multigraph)，如图103(b)所示。在我们以后的讨论中，不允许存在自回路和多重图。第10章 图 图103 自回路和多重图示例(a)自回路；(b)多重图1(a)1(b)024032

4、第10章 图 图104 完全图示例0123452723第10章 图 如果一个图有最多的边数，称为完全图(complete graph)。无向完全图有n(n1)/2条边；有向完全图有n(n1)条边。图104是一个无向完全图。若(v1,v2)是无向图的一条边，则称顶点v1和v2相邻接(adjacent)；若v1,v2是有向图的一条边，则称顶点v1邻接到(adjacent to)顶点v2,顶点v2邻接自(adjacent from)v1，并称边(v1,v2)或v1,v2与顶点v1 和v2相关联(incident)。图102(a)的图G1中，v1 和v2相邻接。图102(b)的图G2中，v1邻接到v2

5、，v2邻接自v1，与顶点v2相关联的弧有v1,v2、v2,v0、v2,v4和v3,v2。第10章 图 图G的一个子图(subgraph)是一个图G=(V,E)，使得V(G)V(G),E(G)E(G)。图105(a)和(b)各给出了图102所示的图G1和G2的一个子图。在无向图G中，一条从vp到vq的路径(path)是一个顶点的序列：vp,v1,v2,vn,vq，使得(vp,v1),(v1,v2),(vn,vq)是图G的边。若图G是有向图，则该路径使得vp,v1，v1,v2，vn,vq是图G的边。路径上边的数目称为路径长度(path length)。第10章 图 图105 图102所示的图的子图

6、(a)图G1的子图；(b)图G2的子图；(c)图G1的生成树1(b)1(c)4032021(a)04243第10章 图 如果一条路径上的所有结点，除起始顶点和终止顶点可以相同外，其余顶点各不相同，则称其为简单路径(simple path)。一个回路(cycle)是一条简单路径，其起始顶点和终止顶点相同。我们用结点序列来表示路径。图102的图G1中，v0,v1,v2,v4是一条简单路径,其长度为3。v0,v1,v2,v4,v0是一条回路，v0,v1,v2,v0,v4是一条路径，但不是简单路径。第10章 图 一个无向图中，若两个顶点v0和v1间存在一条从v0到v1的路径，则称v0和v1是连通的。若

7、图中任意一对顶点都是连通的，则称此图是连通图(connected graph)。一个有向图中，若任意一对顶点v0和v1间存在一条从v0到v1的路径和一条从v1到v0的路径，则称此图是强连通图(strongly connected graph)。图102的图G1是连通图，图G2不是强连通图。无向图的一个极大连通子图称为该图的一个连通分量(connected component)。有向图的一个极大强连通子图称为该图的一个强连通分量(strongly connected component)。见图106的例子。第10章 图 图106 图的强连通分量(a)图G3；(b)图G3的两个强连通分量 1(a)

8、13(b)4032402第10章 图 图中一个顶点的度(degree)是与该顶点相关联的边的数目。有向图的顶点v的入度(in-degree)是以v为头的边的数目，顶点v的出度(out-degree)是以v为尾的边的数目。图106(a)中，顶点0的度为4，入度为3，出度为1。第10章 图 一个无向连通图的生成树(spanning tree)是一个极小连通子图，它包括图中全部顶点，但只有足以构成一棵树的n1条边(见图105(c)。有向图的生成森林是这样的一个子图，它由若干棵互不相交的有根有向树组成，这些树包含了图中全部顶点。有根有向树是一个有向图，它恰有一个顶点入度为0，其余顶点的入度为1，并且如

9、果略去此图中边的方向，处理成无向图后，图是连通的。不包含回路的有向图称为有向无环图(directed acyclic graph DAG)。一棵自由树(free tree)是不包含回路的连通图。第10章 图 最后我们来看工程上经常使用的网的概念。在图的每条边上加上一个数字作权(weight)，也称为代价(cost)，带权的图称为网(weighted graph or network)。图104所示的完全图也是一个网。第10章 图 10.1.2 图图ADT 现在我们用抽象数据类型(见ADT 101)定义带权有向图。如果将一个无向图的每条边(u，v)都看成是两条有向边和，则该无向图变成有向图。AD

10、T 101 Graph 数据：顶点的非空集合V和边的集合E，每条边由V中顶点的偶对表示。运算：void CreateGraph(Graph*g,int n,T noedge)后置条件:已构造一个只有n个结点，不包含任何边的有向图。BOOL Add(Graph*g,int u,int v,T w)后置条件:向图中添加权值为w(若边上没有权，则w0)的边，若插入成功，则函数返回TRUE，否则返回FALSE。第10章 图 BOOL Delete(Graph*g,int u,int v)后置条件：从图中删除边，若删除成功，则函数返回TRUE，否则返回FALSE。BOOL Exist(Graph g,i

11、nt u,int v)后置条件：如果图中存在边，则函数返回TRUE，否则返回FALSE。int Vertices Graph g)后置条件：函数返回图中顶点数目。第10章 图 上面列出的只是图的最基本的运算。在以后的各小节中，我们将通过添加新运算，陆续扩充ADT 101 的图抽象数据类型。主要包括以下图运算：(1)深度优先搜索图：void DFS(Graph g)；(2)宽度优先搜索图：void BFS(Graph g)；(3)拓扑排序：void TopoSort(Graph g)；(4)关键路径：void CriticalPath(Graph g)；(5)普里姆算法求最小代价生成树：void

12、 Prim(Graph g，int k)；第10章 图 (6)克鲁斯卡尔算法求最小代价生成树：void Kruskal(Graph g，int edges)；(7)迪杰斯特拉算法求单源最短路径：void Dijkstra(Graph g，int k,T d,int p)；(8)弗洛伊德算法求所有顶点之间的最短路径：void Floyd(Graph g，T*&d,int*&path)。第10章 图 10.2 图的存储结构图的存储结构10.2.1 矩阵表示法矩阵表示法 1.邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。一个有n个顶点的图G=(V,E)的邻接矩阵(adjacency matrix)

13、是一个nn的矩阵A，A中每一个元素是0或1。邻接矩阵表示一个图中顶点间的相邻接的关系。第10章 图 如果G是无向图，那么A中的元素定义如下：其他或如果 0E)uv,(Ev)u,(1v)A(u,如果G是有向图，那么A中的元素定义如下：其他如果 0 E vu,1v)A(u,如果G是带权的有向图(网)，那么A中的元素定义如下：vu 0 Evu,)v,u(wv)A(u,其他如果如果其中，w(u,v)是边的权值。第10章 图 图107给出了图的邻接矩阵表示的例子。图107(d)是(a)的无向图G1的邻接矩阵，它是对称矩阵，这是因为一条无向边被认为是两条有向边。图107(f)是(c)的网G3的邻接矩阵，主

14、对角线为0，若是图中的边，则A(u,v)为边上的权值，否则A(u,v)为 。第10章 图 图107 邻接矩阵示例(a)无向图G1；(b)有向图G2；(c)网G3；(d)G1的邻接矩阵；(e)G2的邻接矩阵；(f)G3的邻接矩阵2031(a)2031(b)2031(c)411350 1 2 30 1 0 11 0 1 10 1 0 11 1 1 00123(d)0 1 2 30 0 0 01 0 1 00 0 0 11 1 0 00123(e)0 1 2 3 0 4 0 5 0 3 1 1 00123(f)第10章 图 2.关联矩阵关联矩阵 前面提到，图在工程技术中应用十分广泛。例如，在电路CA

15、D中的关联矩阵(incidence matrix)便是图的另一种表示方法。对图101的电路，根据克希霍夫定律，列出结点的电流方程为)n(ii)n(0iii)n(0iii)n(0ii42L2R33C2C2L21L2C1C11L1R结点结点结点结点第10章 图 写成矩阵形式为：1112113221221314321001000 0110010001100100010001LCLRCCRiLCLRCCRininininii 上式左边的矩阵是图的关联矩阵A，右边向量称为支路电流向量Ib，这样克希霍夫电流定律可写成矩阵表示式AIb=0。第10章 图 事实上，对于一个图，除了可用邻接矩阵表示外，还对应着一

16、个图的关联矩阵。关联矩阵是表示图中边与顶点相关联的矩阵。有向图G=(V，E)的关联矩阵是如下定义的n m阶矩阵：不相关联与弧如果顶点的终点是弧如果顶点的起点是弧如果顶点 j v 0 j v 1 j v 1)j,v(A 从上面的讨论中我们看到，一个图可以用矩阵表示，那么在计算机中就可以按照矩阵的存储方式来存储图，其中最常见的是用二维数组存储。图的结构复杂，使用广泛，所以存储表示方法也是多种多样的。对于不同的应用，往往有不同的存储方法。第10章 图 3.邻接矩阵的C语言定义 下面我们给出用邻接矩阵作为存储表示的图的C语言类型定义。图被定义成结构类型Graph。Vertices 为图中的顶点数。A是指向存储邻接矩阵的二维数组的指针，即它是一个指向类型为T的元素的指针的指针。邻接矩阵有两种：图和网的邻接矩阵。图的邻接矩阵的元素为0或1，而网的邻接矩阵中包含0、和边上的权值，权值的类型T可为整型、实型等，见图107(f)。两种邻接矩阵中，主对角线元素总是0。令Aijw，若边 E，则w1(图)或w边上的权(网)。若边 E，则w0(图)或w (网)。所以，在类型Graph中，NoEdge的值对图和网