《DBS第十章》PPT课件.ppt

第第1010章章 图图引引 言言 图是比线性表、树和集合更一般、更复杂的数图是比线性表、树和集合更一般、更复杂的数据结构。据结构。区别于线性结构、树结构和集合结构，在图结区别于线性结构、树结构和集合结构，在图结构中，数据元素之间的关系是任意的，每个元素都构中，数据元素之间的关系是任意的，每个元素都可以和任何其它元素相关。可以和任何其它元素相关。本章讨论图的基本概念、图的存储表示方法以本章讨论图的基本概念、图的存储表示方法以及若干常见的图运算，包括图的遍历和最小代价生及若干常见的图运算，包括图的遍历和最小代价生成树。成树。内容提要内容提要1 1、图的基本概念、图的基本概念2 2、图的存储结构、图的存储结构 包括图的邻接矩阵表示和邻接表表示法包括图的邻接矩阵表示和邻接表表示法及其实现及其实现3 3、图的遍历：深度优先和宽度优先遍历、图的遍历：深度优先和宽度优先遍历4 4、最小代价生成树：普里姆算法、最小代价生成树：普里姆算法10.1 10.1 图的基本概念图的基本概念 与线性表、树和集合不同，与线性表、树和集合不同，在图结构中，每个数据元素都可在图结构中，每个数据元素都可以与任何其它数据元素相关。图以与任何其它数据元素相关。图在许多方面都有所应用。在许多方面都有所应用。课堂提要课堂提要课堂提要课堂提要第第1010章章 图图10.1 10.1 图的基本概念图的基本概念10.2 10.2 图的存储结构图的存储结构10.3 10.3 图的遍历图的遍历10.5 10.5 最小代价生成最小代价生成 树树n n1 1 L L1 1 n n2 2 C C2 2 n n3 3 L L2 2 n n4 4R R1 1 C C2 2 C C3 3 R R2 2n n5 5(b)(a)(b)(a)的图表示的图表示(a)(a)电路示例电路示例图图10-1 10-1 电路示例及对应的图表示电路示例及对应的图表示n n1 1 R R1 1V V1 1L L1 1n n2 2C C2 2n n3 3L L2 2n n4 4C C2 2R R2 2C C3 3n n5 5图图(graph)(graph)：是数据结构是数据结构 G=(V,E)G=(V,E)，其中其中V(G)V(G)是是G G中中结点结点的有的有限非空集合限非空集合,结点的结点的偶对偶对称为称为边边(edge)(edge)；E(G)E(G)是是G G中中边边的有限的有限集合。集合。图中图中的的结点又称为结点又称为顶点顶点(vertex)(vertex)。10.1.1 10.1.1 图的定义与术语图的定义与术语1 10 02 23 34 4(a)(a)图图G G1 1图中图中 :V(GV(G1 1)=0,1,2,3,4)=0,1,2,3,4E(GE(G1 1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)有向图有向图(directed graph)(directed graph)：指图中代表指图中代表边的偶对是边的偶对是有序的。有序的。用用uv代表一条代表一条有向边有向边（又称为（又称为弧弧），则），则u u称为该边的称为该边的始点始点（尾）（尾），v v称为边的称为边的终点（头）。终点（头）。无向图无向图(undirected graph)(undirected graph)：指图中代表指图中代表边的偶对是边的偶对是无序的无序的 在无向图中在无向图中边边(u u，v v )和和(v(v，u)u)是同一条边。是同一条边。1 10 02 23 34 4(b)(b)有向图有向图G G2 21 10 02 23 34 4(a)(a)无向图无向图G G1 11 10 02 23 34 41 10 02 23 34 4(a)(a)无向图无向图G G1 1(b)(b)有向图有向图G G2 2图中图中 V(GV(G1 1)=V(G)=V(G2 2)=0,1,2,3,4)=0,1,2,3,4E(GE(G1 1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)E(GE(G2 2)=,)=,自回路自回路：如果图中存在无向边如果图中存在无向边(u,u)(u,u)或有向边或有向边，则称这样的边为则称这样的边为自回路。自回路。多重图：多重图：指图中两个顶点间允许有多条相同的边。指图中两个顶点间允许有多条相同的边。自回路和多重图自回路和多重图的例子的例子1 10 02 23 31 10 02 23 3(b)(b)多重图多重图 (a)(a)自回路自回路 邻邻接接:如如果果(u,v)(u,v)是是无无向向图图中中的的一一条条边边，则则称称顶顶点点u u和和v v相相邻邻接接，并并称称边边(u,v)(u,v)与顶点与顶点u u和和v v相关联相关联。例如：顶点例如：顶点1 1和和2 2是相邻接的。是相邻接的。完全图：完全图：如果一个图有最多的边数，称为如果一个图有最多的边数，称为完全图完全图。无向完全图有无向完全图有n(n-1)/2n(n-1)/2条边，条边，有向完全图有有向完全图有n(n-1)n(n-1)条边。条边。例如：左图是一个完全图。有例如：左图是一个完全图。有6 6条边。条边。无向完全图无向完全图 0 01 12 23 3 如如果果是是有有向向图图中中的的一一条条边边，则则称称顶顶点点u u邻邻接接到到v v；称顶点称顶点v v邻接邻接自自u u ,并称边并称边与顶点与顶点u u和和v v相关联相关联。子子 图图：图图 G G的的 一一 个个 子子 图图 是是 图图 G G=(V=(V,E,E)，其其 中中V V(G(G)V(G),V(G),E E(G(G)E(G).E(G).1 10 02 24 4图图G G1 1的子图的子图1 10 02 23 34 4图图G G2 2的子图的子图1 10 02 23 34 41 10 02 23 34 4G G1 1G G2 2路径：路径：在无向图在无向图G G中，一条从中，一条从s s到到t t的的路径路径是存在一个顶点序是存在一个顶点序 列列(s,v(s,v1 1,v,v2 2,v vk k,t,t),),使得使得(s,v(s,v1 1),(v),(v1 1,v,v2 2),),(,(v vk k,t,t)都是图都是图G G中的边。中的边。对于有向图顶点序列对于有向图顶点序列s,vs,v1 1,v,v2 2,v vk k,t,t,应使应使s,v,v ,t都是图都是图G G中的边。中的边。路径长度路径长度:指路径上边的数目。指路径上边的数目。简单路径简单路径:除起点和终点可以相同外，路径上其余顶点各不相同。除起点和终点可以相同外，路径上其余顶点各不相同。回路回路:起点和终点相同的简单路径起点和终点相同的简单路径。1 10 02 23 34 41 10 02 23 34 4G G1 1G G2 2(0,1,2,3)(0,1,2,3)；(0,1,2,3,4,2,0)(0,1,2,3,4,2,0)；(0,1,2,3,4,0)(0,1,2,3,4,0)都是都是路径路径，它们的路径，它们的路径长度分别为长度分别为3,6,53,6,5。其中其中(0,1,2,3)(0,1,2,3)和和(0,1,2,3,4,0)(0,1,2,3,4,0)是是简简单路径单路径，(0,1,2,3,4,0)(0,1,2,3,4,0)又是又是回路回路。无向图中如果两个顶点无向图中如果两个顶点u u和和v v之间存在一条路径，则称之间存在一条路径，则称顶点顶点u u和和v v是是连通的连通的，否则是，否则是不连通的不连通的。连通图连通图:无向图中如果任意两个顶点之间是连通的无向图中如果任意两个顶点之间是连通的。连通分量连通分量:无向图的无向图的极大极大连通子图连通子图。1 10 02 23 34 4 0 0和和3 3是是连通的连通的。实际上该图任意两个顶点都是连通的，实际上该图任意两个顶点都是连通的，故该图是故该图是连通图连通图。1 10 02 23 34 46 65 51 10 02 23 34 46 65 5 0 0和和6 6是是不连通的不连通的。该图是该图是非连通图非连通图，但它存在，但它存在两个连两个连通分量通分量。注意极大的含义注意极大的含义：如果某个连通：如果某个连通子图再加上一个顶点后，仍然是子图再加上一个顶点后，仍然是连通的，则它不是连通分量。连通的，则它不是连通分量。3 31 10 02 24 4强连通图：强连通图：有向图中如果任意两个顶点有向图中如果任意两个顶点u u和和v v之间，存在一之间，存在一条从条从u u到到v v的路径，同时存在一条从的路径，同时存在一条从v v到到u u的路径，则称该有的路径，则称该有向图为向图为强连通图。强连通图。强连通分量：强连通分量：有向图的极大强连通子图。有向图的极大强连通子图。1 10 02 23 34 41 10 02 23 34 41 10 02 23 34 43 34 41 10 02 24 41 10 02 23 33 31 10 02 2例如左图中，顶点例如左图中，顶点1,21,2度分别为度分别为2 2和和4 4。右图中，顶点右图中，顶点0 0的入度和出度分别为的入度和出度分别为3 3和和1 1，顶点顶点0 0的度为的度为4 41 10 02 23 34 41 10 02 23 34 4顶点顶点2 2的入度和出度分别为？的入度和出度分别为？顶点的度：顶点的度：与该顶点相关联的边的数目。与该顶点相关联的边的数目。入度：入度：有向图中有向图中顶点顶点v v的的入度入度指以指以v v为头的弧的数目；为头的弧的数目；出度：出度：有向图中有向图中顶点顶点v v的的出度出度指以指以v v为尾的弧的数目。为尾的弧的数目。有向图中有向图中，顶点的度顶点的度=入度入度+出度出度。生生成成树树：无无向向图图的的生生成成树树是是一一个个极极小小连连通通子子图图，它它包包含含图图中中所所有有顶顶点点，但但只只有有足足以以构构成成一一棵棵树树的的(n-1)(n-1)条条边边。去去掉掉一一条条就就不不连连通通，再再加加上上一一条条边边将构成回路。将构成回路。有有向向图图的的生生成成森森林林：是是一一个个子子图图，由由若若干干棵棵互互不不相交的有根有向树组成，包含图中所有的顶点。相交的有根有向树组成，包含图中所有的顶点。1 10 02 23 34 4图图G G1 1的的生成树生成树1 10 02 23 34 4图图G G1 1有有根根有有向向树树：是是一一个个有有向向图图，它它恰恰有有一一个个顶顶点点的的入入度度为为0 0，其其余余顶顶点点的的入入度度为为1 1。如如果果略略去去边边的的方方向向，处理成无向图后，则图是连通的。处理成无向图后，则图是连通的。网网：在在图图的的每每条条边边上上加加上上一一个个数数字字称称为为权权，也也称称代价代价,带权的图称为带权的图称为网。网。1 10 02 23 34 4有向无环图（有向无环图（DAGDAG图）：图）：不包含回路的有向图。不包含回路的有向图。自由树：自由树：不包含回路的连通图。不包含回路的连通图。1 10 02 23 34 41 10 02 23 34 42 23 38 86 62 25 54 4ADT 10ADT 101 Graph 1 Graph 数据：数据：顶点的非空集合顶点的非空集合V V和边的集合和边的集合E E，每条边由，每条边由V V中顶点的偶对中顶点的偶对表示。表示。运算：运算：void void CreateGraphCreateGraph(Graph*g,(Graph*g,intint n,T n,T noedgenoedge)后置条件后置条件:已构造一个只有已构造一个只有n n个结点，不包含任何边的有向图。个结点，不包含任何边的有向图。BOOL Add(Graph*g,BOOL Add(Graph*g,intint u,u,intint v,T w)v,T w)后置条件后置条件:向图中添加权值为向图中添加权值为w(w(若边上没有权，则若边上没有权，则w w0)0)的边的边uv，若，若插入成功，则函数返回插入成功，则函数返回TRUETRUE，否则返回，否则返回FALSEFALSE。BOOL Delete(Graph*g,BOOL Delete(Graph*g,intint u,u,intint v)v)后置条件：从图中删除边后置条件：从图中删除边uv，若删除成功，则函数返回，若删除成功，则函数返回TRUETRUE，否则返，否则返回回FALSEFALSE。BOOL Exist(Graph g,BOOL Exist(Graph g,intint u,u,intint v)v)后置条件：如果图中存在边后置条件：如果图中存在边uv，则函数返回，则函数返回TRUETRUE，否则返回，否则返回FALSEFALSE。intint Vertices Graph g)Vertices Graph g)后置条件：函数返回图中顶点数目。后置条件：函数返回图中顶点数目。上面列出的只是图的最基本的运算。在以后的各小节中，我们将通过添加新运上面列出的只是图的最基本的运算。在以后的各小节中，我们将通过添加新运算，陆续扩充算，陆续扩充ADT 10ADT 101 1 的图抽象数据类型。主要包括以下图运算：的图抽象数据类型。主要包括以下图运算：(1)(1)深度优先搜索图：深度优先搜索图：void DFS(Graph g)void DFS(Graph g)；(2)(2)宽度优先搜索图：宽度优先搜索图：void BFS(Graph g)void BFS(Graph g)；(3)(3)拓扑排序：拓扑排序：void void TopoSort(GraphTopoSort(Graph g)g)；(4)(4)关键路径：关键路径：void void CriticalPath(GraphCriticalPath(Graph g)g)；(5)(5)普里姆算法求最小代价生成树：普里姆算法求最小代价生成树：void Prim(Graph gvoid Prim(Graph g，intint k)k)；(6)(6)克鲁斯卡尔算法求最小代价生成树：克鲁斯卡尔算法求最小代价生成树：void void Kruskal(GraphKruskal(Graph g g，intint edges)edges)；(7)(7)迪杰斯特拉算法求单源最短路径：迪杰斯特拉算法求单源最短路径：void void Dijkstra(GraphDijkstra(Graph g g，intint k,T k,T d,d,intint p)p)；(8)(8)弗洛伊德算法求所有顶点之间的最短路径：弗洛伊德算法求所有顶点之间的最短路径：void void Floyd(GraphFloyd(Graph g g，T*&d,T*&d,intint*&path)*&path)。1 1、图的矩阵表示法及其实现、图的矩阵表示法及其实现2 2、图的邻接表表示法及其实现、图的邻接表表示法及其实现10.2 10.2 图的存储结构图的存储结构10.2.1 10.2.1 图的图的矩阵表示法矩阵表示法1 1、邻接矩阵、邻接矩阵 一个有一个有n n个顶点的图个顶点的图G=(V,E)G=(V,E)的邻接矩阵是一个的邻接矩阵是一个n n n n的的矩阵矩阵A A，A A的每个元素是的每个元素是0 0或或1 1。课堂提要课堂提要课堂提要课堂提要第第1010章章 图图10.1 10.1 图的基本概念图的基本概念10.2 10.2 图的存储结构图的存储结构10.3 10.3 图的遍历图的遍历10.5 10.5 最小代价生成最小代价生成 树树 设设V=0,1,2,V=0,1,2,n-1,n-1,如如果果G G是是无无向向图图，则则A A的元素定义为：的元素定义为：如果如果G G是有向图，则是有向图，则A A的元素定义为：的元素定义为：1(u,v)1(u,v)E E或或(v,u)(v,u)E E Auv=Auv=0 0 其它其它 1 1 E E Auv=Auv=0 0 其它其它如果如果G G是带权的有向图是带权的有向图(网网)，那么，那么A A中的元素定义如下：中的元素定义如下：(e)(e)图图G G2 2的邻接矩阵的邻接矩阵 0 1 2 3 0 1 2 30 0 0 0 00 0 0 0 01 1 0 1 01 1 0 1 02 0 0 0 12 0 0 0 13 1 1 0 03 1 1 0 0(b)(b)有向图有向图G G2 20 01 13 32 2(c)(c)网网G G3 30 01 13 32 2 1 1 5 1 1 5 4 43 3 0 1 2 3 0 1 2 30 0 0 0 1 4 0 5 1 4 0 5 2 2 0 0 3 33 1 1 3 1 1 0 0(f)(f)网网G G3 3的邻接矩阵的邻接矩阵0 01 13 32 2(a)(a)无向图无向图G G1 1(d)(d)图图G G1 1的邻接矩阵的邻接矩阵 0 1 2 3 0 1 2 30 0 1 0 10 0 1 0 11 1 0 1 11 1 0 1 12 0 1 0 12 0 1 0 13 1 1 1 03 1 1 1 0图图 10.7 10.7 图的邻接矩阵图的邻接矩阵0 0邻接矩阵邻接矩阵例如例如：0 01 12 24 45 53 31 12 24 45 53 34 45 50 0 1 1 2 2 3 34 45 51 12 23 30 0如果如果G G是有向图，则是有向图，则A A的元素定义为：的元素定义为：1 1 E E Auv=Auv=0 0 其它其它1 1 1 11 11 11 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0强连通分量强连通分量1 1、邻接矩阵、邻接矩阵C C语言定义语言定义10.2.2 10.2.2 图的邻接矩阵实现图的邻接矩阵实现typedeftypedef structstruct graph graph T T NoEdgeNoEdge;/两结点间无边时的值两结点间无边时的值(0(0或或)intint Vertices;Vertices;/图中顶点数图中顶点数 T*A;T*A;/指向存储邻接矩阵的二维数组的指针指向存储邻接矩阵的二维数组的指针 Graph;Graph;建立邻接矩阵（建立邻接矩阵（【程序程序101】）。）。void CreateGraph(Graph*g,int n,T noedge)int i,j;g-NoEdge=noedge;g-Vertices=n;g-A=(T*)malloc(n*sizeof(T*);for(i=0;iAi=(T*)malloc(n*sizeof(T);for(j=0;jAij=noedge;g-Aii=0;-11nna-1101nanajia-11 na 11 a01 a-10na 10 a00 aLOMMOLL0000noedgenoedgenoedgenoedgenoedgenoedgeBOOL Exist(Graph g,int u,int v)if(u0|vn-1|vn-1|u=v|auv=noEdge)return false;return true;3 3、边的搜索、插入和删除、边的搜索、插入和删除0 01 13 32 2 0 1 2 3 0 1 2 30 0 0 0 00 0 0 0 01 1 0 1 01 1 0 1 02 0 0 0 12 0 0 0 13 1 1 0 03 1 1 0 0/判边是否存在判边是否存在3,13,1是否有边？是否有边？1,31,3是否有边？是否有边？有边有边!无边无边!BOOL Add(Graph*g,int u,int v,T w)int n=g-Vertices;if(u0|vn-1|vn-1|u=v|g-Auv!=g-NoEdge)printf(BadInputn);return FALSE;g-Auv=w;return TRUE;/边的插入边的插入0 01 13 32 2 0 1 2 3 0 1 2 30 0 0 0 00 0 0 0 01 1 0 1 01 1 0 1 02 0 0 0 12 0 0 0 13 1 1 0 03 1 1 0 01 1插入插入0,20,2边边/边的删除边的删除BOOL Delete(Graph*g,int u,int v)int n=g-Vertices;if(u0|vn-1|vn-1|u=v|g-Auv=g-NoEdge)printf(BadInputn);return FALSE;g-Auv=g-NoEdge;return TRUE;0 01 13 32 2 0 1 2 3 0 1 2 30 0 0 0 00 0 0 0 01 1 0 1 01 1 0 1 02 0 0 0 12 0 0 0 13 1 1 0 03 1 1 0 01 1删除删除0,20,2边边10.2.3 10.2.3 邻接表表示法邻接表表示法要点：要点：1 1、为图中每一个顶点建立一个单链表；、为图中每一个顶点建立一个单链表；2 2、顶点、顶点u u的单链表中的每一个结点指示的单链表中的每一个结点指示u u的一个的一个邻接点邻接点v，即代表一条边即代表一条边(u,v)(u,v)或或 顶点顶点u u的单链表记录了与的单链表记录了与u u相邻接相邻接(邻接自邻接自u)u)的所有顶点。的所有顶点。每个每个单链表相当于邻接单链表相当于邻接矩阵的一行矩阵的一行,它指示了该行中的非零的它指示了该行中的非零的元素。元素。0 01 13 32 20 01 12 23 3 1 1 3 3 0 0 0 0 2 2 3 3、边结点的结构、边结点的结构adjVexadjVex W W nextArcnextArc(b)(b)带权的边结点带权的边结点adjVexadjVex nextArcnextArc(a)(a)边结点边结点指示顶点指示顶点u u的的一个邻接点一个邻接点指向指向u u的下一的下一个边结点个边结点边上的权值边上的权值 u u 1 1 3 3 v v 0 0 2 2 element element firstArcfirstArc(c)(c)顶点结点顶点结点存放顶点的名存放顶点的名称及其他信息称及其他信息指向指向u u的第一的第一个边结点个边结点 u u 1 1 3 3 v v 0 0 2 2 4 4、每个单链表可设立一个存放顶点每个单链表可设立一个存放顶点u u的有关信息的表头结点，也的有关信息的表头结点，也称顶点结点称顶点结点。顶点结点存入一个一维数组。顶点结点存入一个一维数组。0 01 12 23 32 2 1 1 0 0 3 3 1 1 3 3 1 1 3 3 2 2 0 0(a)(a)图图G G1 1的邻接表的邻接表0 01 13 32 2图图G G1 10 01 12 23 3 1 1 3 3 0 0 0 0 2 2 (b)(b)图图G G2 2的邻接表的邻接表0 01 13 32 2图图G G2 20 01 12 23 3 3 3 3 3 0 0 1 1 1 1 1 1 2 2 5 5 0 0 4 4 (c)(c)图图G G3 3的邻接表的邻接表4 40 01 13 32 2图图G G3 33 31 11 15 5typedef struct enode int AdjVex;T W;struct enode*NextArc;ENode;typedef struct graph int Vertices;ENode*A;Graph;边结点的结构类型边结点的结构类型图中的顶点数图中的顶点数0 01 12 23 3 1 1 3 3 0 0 0 0 2 2 A邻接表的表头组成一维指针数组，邻接表的表头组成一维指针数组，A A是指向该数组的指针是指向该数组的指针3.3.建立邻接表建立邻接表 函数函数CreateGraphCreateGraph构造一个有构造一个有n n个顶点，但个顶点，但不包含边不包含边的有向图。由于图的有向图。由于图的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组。void void CreateGraph(GraphCreateGraph(Graph*g,*g,intint n)n)intint i;i;g-Vertices=n;g-Vertices=n;g-A=(g-A=(ENodeENode*)*)malloc(nmalloc(n*sizeof(ENodesizeof(ENode*);*);for(i=0;iAi=for(i=0;iAi=NULLNULL;0 01 1.n-1n-1.搜索、插入或删除从顶点搜索、插入或删除从顶点u u发出的边，只在发出的边，只在AuAu 所指所指向的单链表中操作向的单链表中操作。程序如下：。程序如下：3 3、边的搜索、插入和删除、边的搜索、插入和删除0 01 12 23 32 2 1 1 0 0 3 3 1 1 3 3 1 1 3 3 2 2 0 0 1,21,2是否有边？是否有边？/搜索边的函数搜索边的函数BOOL Exist(Graph g,int u,int v)BOOL Exist(Graph g,int u,int v)int n;int n;ENode*p;ENode*p;n=n=g.Verticesg.Vertices;if(if(u u0n-1un-1)return FALSE;)return FALSE;for(pfor(p=g.Aug.Au;p&pp&p-AdjVexAdjVex!=v;)!=v;)p=p-p=p-NextArcNextArc;if(!p)return FALSE;if(!p)return FALSE;return TRUE;return TRUE;/插入边的函数插入边的函数BOOL Add(Graph*g,int u,int v,T w)int n;ENode*p;n=g-Vertices;if(u0|vn-1|vn-1|u=v|Exist(*g,u,v)printf(BadInputn);return FALSE;p=NewENode(v,w,g-Au);g-Au=p;return TRUE;0 01 12 23 3 1 1 3 3 0 0 0 0 2 2 p p3 30 01 13 32 2插入邻接表中由指针插入邻接表中由指针AuAu 所所指示的单链表的最前面指示的单链表的最前面ENodeENode*NewENodeNewENode(intint vex,T weight,vex,T weight,ENodeENode*nextarcnextarc)ENodeENode*p;*p;p=(p=(ENodeENode*)*)malloc(sizeof(ENodemalloc(sizeof(ENode););p-p-AdjVexAdjVex=vex;=vex;p-W=weight;p-W=weight;p-p-NextArcNextArc=nextarcnextarc;return p;return p;/删除边的函数删除边的函数BOOL BOOL Delete(GraphDelete(Graph*g,*g,intint u,u,intint v)v)intint n=g-n=g-Vertices;ENodeVertices;ENode*p,*q;*p,*q;if(uif(u-1&u-1&u p=g-AuAu;q=NULL;q=NULL;while(p&p-while(p&p-AdjVexAdjVex!=v)!=v)q=p;p=p-q=p;p=p-NextArcNextArc;if(p)if(p)if(q)q-if(q)q-NextArcNextArc=p-=p-NextArcNextArc;else g-else g-AuAu=p-=p-NextArcNextArc;free(pfree(p);return TRUE;);return TRUE;printf(BadInputnprintf(BadInputn););return FALSE;return FALSE;0 01 12 23 3 1 1 3 3 0 0 0 0 2 2 0 01 13 32 23 3P Pq=NULLq=NULL在由指针在由指针AuAu 所指示的单所指示的单链表中，搜索链表中，搜索AdjVexAdjVex域的域的值为值为v v的边结点的边结点10.3 10.3 图的遍历图的遍历图的遍历图的遍历:指从图指从图G G的任意一个顶点的任意一个顶点v v出出发，访问图中所有结点且每个结点仅访发，访问图中所有结点且每个结点仅访问一次的过程。问一次的过程。图遍历的方法图遍历的方法:深度优先搜索深度优先搜索（类似于（类似于树的先序遍历）和树的先序遍历）和宽度优先搜索宽度优先搜索（类似（类似于树的按层次遍历）于树的按层次遍历）课堂提要课堂提要课堂提要课堂提要第第1010章章 图图10.1 10.1 图的基本概念图的基本概念10.2 10.2 图的存储结构图的存储结构10.3 10.3 图的遍历图的遍历10.5 10.5 最小代价生成最小代价生成 树树10.3.2 10.3.2 深度优先遍历深度优先遍历图遍历与树遍历的差异图遍历与树遍历的差异:1 1、从图中任意一个顶点出发未必能到达其它所有顶点；、从图中任意一个顶点出发未必能到达其它所有顶点；2 2、图中存在回路时，又可能多次经过同一个顶点。、图中存在回路时，又可能多次经过同一个顶点。为为了了避避免免发发生生上上述述两两种种情情况况，图图的的搜搜索索算算法法通通常常为为图图的的每每个顶点保留一个标志位个顶点保留一个标志位(mark bit)(mark bit)。算法开始时，所有顶点的标志位清零。算法开始时，所有顶点的标志位清零。在在遍遍历历过过程程中中，当当某某个个顶顶点点被被访访问问时时，其其标标志志位位被被标标记记。在在搜索中遇到被标记过的顶点则不再访问它。搜索中遇到被标记过的顶点则不再访问它。搜搜索索结结束束后后，如如果果还还有有未未标标记记过过的的顶顶点点，遍遍历历算算法法可可以以选选一一个未标记的顶点，从它出发开始继续搜索。个未标记的顶点，从它出发开始继续搜索。1 1、深度优先搜索算法、深度优先搜索算法 从图从图G G中某个顶点中某个顶点v v出发出发,深度优先搜深度优先搜索索图的图的DFSDFS算法如下：算法如下：1 1、访问顶点、访问顶点v v并并打上标记。打上标记。2 2、依次从、依次从v v的的未访问过的邻接点出发，未访问过的邻接点出发，深度优先搜索深度优先搜索图图G.G.从从A A出发出发将访问走过的边保留，去掉访问时未走过将访问走过的边保留，去掉访问时未走过的边，就得到以的边，就得到以A A为根的为根的DFSDFS生成树。生成树。如果是连通的无向图或强连通的有向图，上述如果是连通的无向图或强连通的有向图，上述DFSDFS算法必定可以算法必定可以系统地访问图中的全部顶点。系统地访问图中的全部顶点。一条无向边被视作两条有向边，被查看两次。一条无向边被视作两条有向边，被查看两次。(a)(a)有向图有向图G GB BF FD DE EA AC CG G对有向图对有向图G G，从，从A A出发出发DFSDFS，访问的次序是访问的次序是A,B,D,CA,B,D,C；遍历了所有从；遍历了所有从A A出发可到达的顶点，即出发可到达的顶点，即A A的可达集。的可达集。另选一个顶点出发搜索图另选一个顶点出发搜索图G G的其余部分的其余部分。0 0 2 2 3 3 0 01 12 23 34 45 56 6A AB BC CD DF FG GE E4 4 1 1 5 5 3 3 4 40 0 2 2 (b)(b)图图G G的邻接表的邻接表1A AB BD DC CF FG GE E(a)(a)有向图有向图G GB BF FD DE EA AC CG GB BF FD DE EA AC CG G(c)(c)图图G G深度优先搜索的生成森林深度优先搜索的生成森林思考思考:图的图的DFSDFS序列是否惟一？序列是否惟一？(指从同一顶点出发指从同一顶点出发)A AB BD DC CF FG GE E图中所有顶点，以及在图中所有顶点，以及在遍历时经过的边构成的遍历时经过的边构成的子图，称为图的子图，称为图的深度优深度优先搜索生成树先搜索生成树(dfsdfs spanning tree)(spanning tree)(或或生生成森林成森林)。DFSDFS递归算法（递归算法（【程序程序10105 5】）。void DFS(Graph g,int v,BOOL*visited)ENode*w;visitedv=TRUE;printf(%d ,v);for(w=g.Av;w;w=w-NextArc)if(!visitedw-AdjVex)DFS(g,w-AdjVex,visited);void Traversal_DFS(Graph g)BOOL visitedMaxSize;int i,n=g.Vertices;for(i=0;in;i+)visitedi=FALSE;for(i=0;i;w;w=w-NextArcNextArc)if(!if(!visitedwvisitedw-AdjVexAdjVex)printf(%dprintf(%d ,w-,w-AdjVexAdjVex););visitedwvisitedw-AdjVexAdjVex=TRUE;=TRUE;Append(&qAppend(&q,w-,w-AdjVexAdjVex););u u的邻接顶点入队的邻接顶点入队访问访问队头元素队头元素u u的所有未访问过的所有未访问过的邻接点的邻接点void void Traversal_BFS(GraphTraversal_BFS(Graph g)g)BOOL BOOL visitedMaxSizevisitedMaxSize;intint i,n=i,n=g.Verticesg.Vertices;for(ifor(i=0;in;i+)=0;in;i+)visitedivisitedi=FALSE;=FALSE;for(i=0;in;i+)for(i=0;in;i+)if(!if(!visitedivisitedi)BFS(gBFS(g,i,visited);,i,visited);BFSBFS算法的算法的特点特点：1 1、每个顶点进出队列各一次。、每个顶点进出队列各一次。2 2、对于每个出队的顶点，都要检查其所有的邻接点，对、对于每个出队的顶点，都要检查其所有的邻接点，对于无向图每条边被检查于无向图每条边被检查2 2次。次。3 3、n n个顶点，个顶点，e e条边的图采用邻接表存储，条边的图采用邻接表存储，BFSBFS算法的时算法的时间为间为O(n+e),O(n+e),而采用邻接矩阵表示，时间为而采用邻接矩阵表示，时间为O(nO(n2 2)。如同二叉树的遍历算法，图的如同二叉树的遍历算法，图的DFSDFS和和BFSBFS算法是最重算法是最重要、最基本的算法，许多有关图的算法都可以对它们稍要、最基本的算法，许多有关图的算法都可以对它们稍加修改得到。例如，求无向图的连通分量、有向图的强加修改得到。例如，求无向图的连通分量、有向图的强连通分量、生成树连通分量、生成树(森林森林)等。等。已知一有向图的邻接表存储结构如下图所示，请问：每个顶已知一有向图的邻接表存储结构如下图所示，请问：每个顶点的入度和出度，并给出从顶点点的入度和出度，并给出从顶点1 1出发的深度优先遍历和出发的深度优先遍历和宽度宽度优先遍历