第8章图-图的基本概念

1、18.1 图的基本概念图的基本概念第第8章章 图图8.2 图的存储结构图的存储结构8.3 图的遍历图的遍历8.4 生成树和最小生成树生成树和最小生成树8.5 最短路径最短路径8.6 拓扑排序拓扑排序8.7 AOE网与关键路径网与关键路径2图的示例图的示例V1V4V2V3V5V4V3V2V1 结点之间的关系：结点之间的关系：多对多，任意两个结点之间都可能有关系存在多对多，任意两个结点之间都可能有关系存在边边弧弧顶点顶点3图的抽象数据类型图的抽象数据类型ADT Graph 数据对象：数据对象：D=ai|1in，n0，ai属属ElemType类型类型 数据关系：数据关系：R=|ai,ajD,1in,

2、 1jn,其中每个元素其中每个元素可以有零个或多个直接前驱，可以有零个或多个直接后继可以有零个或多个直接前驱，可以有零个或多个直接后继 基本操作基本操作P：InitGraph(&g) /初始化图：构造一个空图初始化图：构造一个空图gClearGraph(&g)/销毁图：释放图销毁图：释放图g占用的存储空间占用的存储空间DFS(g)/深度优先遍历图深度优先遍历图gBFS(g)/广度优先遍历图广度优先遍历图gADT Graph 48.1.1 8.1.1 图的定义图的定义 图图(Graph)G由两个集合由两个集合V(Vertex)和和E(Edge)组成组成,记记为为G=(V,E)，其

3、中，其中V是是顶点顶点的有限集合，的有限集合，E是连接是连接V中两中两个不同顶点个不同顶点(顶点对顶点对)的的边边的有限集合。的有限集合。 在图在图G中，如果代表边的顶点对是中，如果代表边的顶点对是无序无序的，则称的，则称G为为无向图无向图，无向图中代表边的无序顶点对通常用，无向图中代表边的无序顶点对通常用圆括圆括号号括起来，用以表示一条无向边。括起来，用以表示一条无向边。 如果表示边的顶点对是如果表示边的顶点对是有序有序的，则称的，则称G为为有向图有向图，在有向图中代表边的顶点对通常用在有向图中代表边的顶点对通常用尖括号尖括号括起来括起来 。 8.1 图的基本概念图的基本概念51. 端点和邻

4、接点端点和邻接点 在一个无向图中在一个无向图中,若存在一条边若存在一条边(vi,vj),则称则称vi和和vj为此边的两个端点为此边的两个端点,并称它们互为并称它们互为邻接点邻接点。 在一个有向图中在一个有向图中,若存在一条边若存在一条边,则称此边是顶点则称此边是顶点vi的一条的一条出出边边,同时也是顶点同时也是顶点vj的一条的一条入边入边； 称称vi和和vj分别为此边的分别为此边的起始端点起始端点(简称为起点简称为起点)和和终止端点终止端点(简称终点简称终点)；称称vi和和vj互为邻接点。互为邻接点。 1 3 0 2 4 1 3 0 2 4 (a) (b) 8.1.2 图的基本术语图的基本术语

5、6 2. 顶点的度、入度和出度顶点的度、入度和出度 在无向图中，顶点所具有的在无向图中，顶点所具有的边的边的数目数目称为该称为该顶点的度顶点的度。 在有向图中，以顶点在有向图中，以顶点vi为终点的为终点的入边的数目入边的数目,称为该顶点的称为该顶点的入度入度。 以顶点以顶点vi为始点的出边的数目，为始点的出边的数目，称为该顶点的称为该顶点的出度出度。 一个顶点的一个顶点的入度与出度的和入度与出度的和为该为该顶点的度。顶点的度。 若一个图中有若一个图中有n个顶点和个顶点和e条边，条边，每个顶点的度为每个顶点的度为di(1in)，则有：，则有： 1 3 0 2 4 1 3 0 2 4 (a) (b

6、) n1iid21e7 3. 完全图完全图 若无向图中的每两个顶点之间若无向图中的每两个顶点之间都存在着一条边，有向图中的每都存在着一条边，有向图中的每两个顶点之间都存在着方向相反两个顶点之间都存在着方向相反的两条边，则称此图为的两条边，则称此图为完全图完全图。 完全无向图包含有完全无向图包含有n(n-1)/2条边条边 完全有向图包含有完全有向图包含有n(n-1)条边。条边。 1 0 2 3 1 0 2 3 (a) (b) 8 4. 稠密图、稀疏图稠密图、稀疏图 当一个图接近完全图时，则称当一个图接近完全图时，则称为为稠密图稠密图。相反，当一个图含有。相反，当一个图含有较少的边数较少的边数(即

7、当即当en(n-1)时，时，则称为则称为稀疏图稀疏图。 5. 子图子图 设 有 两 个 图设 有 两 个 图 G = ( V, E ) 和和G=(V,E)，若，若V是是V的子集的子集,即即V V，且，且E是是E的子集，即的子集，即E E，则称，则称G是是G的的子图子图。 例如图例如图(b)是图是图(a)的子图，而图的子图，而图(c)不是图不是图(a)的子图。的子图。 1 3 0 2 4 (a) (b) 1 3 0 2 4 1 3 0 2 4 (c) 96. 路径和路径长度路径和路径长度(略略) 在一个图在一个图G=(V,E)中中,从顶点从顶点vi到顶点到顶点vj的一条路径是的一条路径是一个一个

8、顶点序列顶点序列(vi,vi1,vi2,vim,vj)； 若此图若此图G是无向图是无向图,则边则边(vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)属于属于E(G)； 若此图是有向图若此图是有向图,则则,属于属于E(G)。 路径长度是指一条路径上经过的路径长度是指一条路径上经过的边的数目边的数目。 若一条路径上除开始点和结束点可以相同外，其余若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为顶点均不相同，则称此路径为简单路径简单路径。 例如，例如，(v0,v2,v1)就是一条简单路径，其长度为就是一条简单路径，其长度为2。 1 0 2 3 10

9、7. 回路或环回路或环(略略) 若一条路径上的开始点与结束若一条路径上的开始点与结束点为同一个顶点，则此路径被称为点为同一个顶点，则此路径被称为回路或环回路或环。 开始点与结束点相同的简单路开始点与结束点相同的简单路径被称为径被称为简单回路或简单环简单回路或简单环。 例如，例如，(v0,v2,v1,v0)就是一条简就是一条简单回路，其长度为单回路，其长度为3。 1 0 2 3 11 8. 连通、连通图和连通分量连通、连通图和连通分量 在无向图在无向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径有路径，则称，则称vi和和vj是是连通连通的。的。 若图若图G中任意两个顶点都连通，则称中任意

10、两个顶点都连通，则称G为为连通图连通图，否则称为否则称为非连通图非连通图。 无向图无向图G中的极大连通子图称为中的极大连通子图称为G的连通分量。的连通分量。 任何连通图的连通分量只有一个，即本身，而非任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。连通图有多个连通分量。CABDEFBDEFCA12 9. 强连通图和强连通分量强连通图和强连通分量(略略) 在有向图在有向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径，则称从有路径，则称从vi到到vj是是连通连通的。的。 若图若图G中的任意两个顶点中的任意两个顶点vi和和vj都都连通，即从连通，即从vi到到vj和从和从vj到

11、到vi都存在都存在路径，则称图路径，则称图G是强连通图。是强连通图。 有向图有向图G中的极大强连通子图称中的极大强连通子图称为为G的强连通分量。的强连通分量。 1 0 2 3 （a） 1 0 2 （b） 1310. 权和网权和网 图中图中每一条边每一条边都可以附有一个对应的数值，这种都可以附有一个对应的数值，这种与与边相关的数值边相关的数值称为权。称为权。 权可以表示从一个顶点到另一个顶点的距离或花费权可以表示从一个顶点到另一个顶点的距离或花费的代价。的代价。 边上带有权的图称为边上带有权的图称为带权图带权图，也称作，也称作网网。v2v4v1v5v3v616211114336191865201

12、531050v2v1v5v3v4v0202010301545无向网无向网有向网有向网14思思 考考 要连通具有要连通具有n个顶点的无向图，至少需要个顶点的无向图，至少需要（ ）条边？）条边？ 要连通具有要连通具有n个顶点的有向图，至少需要个顶点的有向图，至少需要（ ）条弧？）条弧？n-1n158.2 图的存储结构图的存储结构 几种常用的存储结构几种常用的存储结构 邻接矩阵邻接矩阵 邻接表邻接表 十字链表十字链表 邻接多重表邻接多重表168.2.1 邻接矩阵存储方法邻接矩阵存储方法 邻接矩阵是表示邻接矩阵是表示顶点之间相邻关系顶点之间相邻关系的矩阵。的矩阵。 设设G=(V,E)是具有是具有n(n

13、0)个顶点个顶点的图，顶点的顺序的图，顶点的顺序依次为依次为(v0,v1,vn-1)，则，则G的邻接矩阵的邻接矩阵A是是n阶方阵阶方阵。 其定义如下：其定义如下： (1) 如果如果G是无向图是无向图,则：则： Aij= 1:若若(vi,vj)E(G) 0:其他其他 (2) 如果如果G是有向图是有向图,则：则： Aij= 1:若若E(G) 0:其他其他 (3) 如果如果G是带权无向图是带权无向图,则：则： Aij= wij :若若vivj且且(vi,vj)E(G) :其他其他 (4) 如果如果G是带权有向图是带权有向图,则：则： Aij= wij :若若vivj且且E(G) :其他其他17011

14、011011111010011011101001001000001100001100010101320413204A10 1 2 3 401234A20 1 2 3 401234对称对称不对称不对称18（1）对于有）对于有n个顶点个顶点e条边的无向图，邻接矩阵条边的无向图，邻接矩阵表示时有多少个元素，多少个非表示时有多少个元素，多少个非0元素？元素？（2）对于有）对于有n个顶点个顶点e条边的有向图，邻接矩阵条边的有向图，邻接矩阵表示时有多少个元素，多少个非表示时有多少个元素，多少个非0元素？元素？（3）邻接矩阵中如何求顶点的度？）邻接矩阵中如何求顶点的度？思思 考考19 (1) 图的邻接矩阵表

15、示是唯一的。图的邻接矩阵表示是唯一的。 (2) 对于含有对于含有n个顶点的图，采用邻接矩阵存储时，无论是个顶点的图，采用邻接矩阵存储时，无论是有向图还是无向图，也无论边的数目是多少，其存储空间均有向图还是无向图，也无论边的数目是多少，其存储空间均为为O(n2)，所以，所以邻接矩阵适合于存储边数较多的稠密图邻接矩阵适合于存储边数较多的稠密图。 (3) 无向图的邻接矩阵一定是一个无向图的邻接矩阵一定是一个对称矩阵对称矩阵。按照压缩存储。按照压缩存储的思想，只需存放上的思想，只需存放上(或下或下)三角形阵的元素即可。三角形阵的元素即可。 (4) 对于无向图，邻接矩阵的对于无向图，邻接矩阵的第第i行行

16、(或第或第i列列)非零元素非零元素(或非或非元素元素)的个数正好是的个数正好是第第i个顶点的度个顶点的度。 (5) 对于有向图，邻接矩阵的对于有向图，邻接矩阵的第第i行行(或第或第i列列)非零元素非零元素(或非或非元素元素)的个数正好是的个数正好是第第i个顶点的出度个顶点的出度(或入度或入度)。 (6) 用邻接矩阵方法存储图，很容易确定图中任意两个顶用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。须按行、按列对每个元素进行检测，所花费的时间

17、代价很大。邻接矩阵的特点邻接矩阵的特点20#define MAXV typedef struct int no;/*顶点编号顶点编号*/ InfoType info; /*顶点其他信息顶点其他信息*/ VertexType;/*顶点类型顶点类型*/typedef struct /*图的定义图的定义*/ int edgesMAXVMAXV; /*邻接矩阵邻接矩阵*/ int vexnum,arcnum; /*顶点数，边数顶点数，边数*/ VertexType vexsMAXV;/*存放顶点信息存放顶点信息*/ MGraph;邻接矩阵的数据类型定义邻接矩阵的数据类型定义21顺序分配与链式分配相结合

18、顺序分配与链式分配相结合的存储方法。的存储方法。在邻接表中，对图中每个顶点建立一个单链表，在邻接表中，对图中每个顶点建立一个单链表，第第i个单链表中的结点表示依附于顶点个单链表中的结点表示依附于顶点vi的边的边(对有对有向图是以顶点向图是以顶点vi为尾的弧为尾的弧)。每个单链表上附设一个表头结点。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：表结点和表头结点的结构如下： 表结点表结点 表头结点表头结点adjvexnextarcinfodatafirstarc8.2.2 邻接表存储方法邻接表存储方法221320413204data firstarcadjvex nextarc表头结点

19、表头结点表结点表结点23（1）对于有）对于有n个顶点个顶点e条边的无向图，邻接表条边的无向图，邻接表表示时有多少个表头结点，多少个表结点？表示时有多少个表头结点，多少个表结点？（2）对于有）对于有n个顶点个顶点e条边的有向图，邻接表条边的有向图，邻接表表示时有多少个表头结点，多少个表结点？表示时有多少个表头结点，多少个表结点？（3）邻接表中如何求顶点的度？）邻接表中如何求顶点的度？思思 考考24 (1) 邻接表表示邻接表表示不唯一不唯一。这是因为在每个顶点对应的单链表。这是因为在每个顶点对应的单链表中，各边结点的中，各边结点的链接次序可以是任意的链接次序可以是任意的，取决于建立邻接表的，取决于

20、建立邻接表的算法以及边的输入次序。算法以及边的输入次序。 (2) 对于有对于有n个顶点和个顶点和e条边的无向图，其邻接表有条边的无向图，其邻接表有n个表头结个表头结点和点和2e个边结点个边结点。对于有。对于有n个顶点和个顶点和e条边的有向图，其邻接表条边的有向图，其邻接表有有n个表头结点和个表头结点和e个边结点个边结点。对于稀疏图，邻接表比邻接矩阵。对于稀疏图，邻接表比邻接矩阵节省空间。节省空间。 (3) 对于无向图，邻接表的顶点对于无向图，邻接表的顶点vi对应的第对应的第i个链表的边结点个链表的边结点数目正好是顶点数目正好是顶点vi的度。的度。 (4) 对于有向图，邻接表的顶点对于有向图，邻

21、接表的顶点vi对应的第对应的第i个链表的边结点个链表的边结点数目仅仅是数目仅仅是vi的出度。其入度为邻接表中所有的出度。其入度为邻接表中所有adjvex域值为域值为i的的边结点数目。边结点数目。邻接表的特点邻接表的特点25typedef struct ANode /*弧的结点结构类型弧的结点结构类型*/int adjvex; /*该弧的终点位置该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针指向下一条弧的指针*/ InfoType info; /*该弧的相关信息该弧的相关信息*/ ArcNode;typedef struct Vnode /*邻接表头结点

22、的类型邻接表头结点的类型*/Vertex data; /*顶点信息顶点信息*/ ArcNode *firstarc; /*指向第一条弧指向第一条弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是邻接表类型是邻接表类型*/typedef struct AdjList adjlist; /*邻接表邻接表*/ int n,e; /*图中顶点数图中顶点数n和边数和边数e*/ ALGraph; /*图的类型图的类型*/邻接表存储结构的定义邻接表存储结构的定义26 已知无向图采用邻接表存储，写出删除边已知无向图采用邻接表存储，写出删除边(i，j)的算法。的算法。v

23、oid DeletEdge(ALGraph g,int i,j) p= g. adjlisti.firstarc; pre=null; pre是前驱指针是前驱指针 while(p) if(p-adjvex=j) if(pre=null) g. adjlisti. firstarc=p-next; else pre-next=p-next; free(p); 释放空间释放空间 else pre=p; p=p-next; 沿链表继续查找沿链表继续查找 p=g . adjlistj. firstarc; pre=null; 删顶点删顶点j 的边结点的边结点(j,i) while(p) if(p-ad

24、jvex=i) if(pre=null) g. adjlistj. firstarc=p-next; else pre-next=p-next; free(p); 释放空间释放空间 else pre=p; p=p-next; 沿链表继续查找沿链表继续查找 DeletEdge27图的存储结构：逆邻接表图的存储结构：逆邻接表 若问题对入度更关心，则可以把线性链表改为：若问题对入度更关心，则可以把线性链表改为：所有以头结点为弧头的弧组成的线性链表。所有以头结点为弧头的弧组成的线性链表。 此时该邻接表称为此时该邻接表称为逆邻接表逆邻接表。v3v2v10 v11 v22 v3011对于有向图，逆邻接表表

25、示了顶点的入度对于有向图，逆邻接表表示了顶点的入度28有向图的存储结构：十字链表有向图的存储结构：十字链表u有向图的十字链表可以同时表示一个有向图的十字链表可以同时表示一个顶点和其他顶点的所有关系：出度和顶点和其他顶点的所有关系：出度和入度入度u十字链表十字链表(orthogonal list)把邻接表和把邻接表和逆邻接表结合起来逆邻接表结合起来29无向图的存储结构：邻接多重表无向图的存储结构：邻接多重表 问题问题： 在无向图中，边是一种在无向图中，边是一种“对称对称”关系，因此在邻接关系，因此在邻接表中，表示任一条边的结点都有两个，而且分别在表中，表示任一条边的结点都有两个，而且分别在两个不

26、同的链表中。即：存储表示中信息有冗余，两个不同的链表中。即：存储表示中信息有冗余，维护不容易。维护不容易。 改进方法：改进方法： 用一个结点完整地表示一条边，在整个存储结构中，用一个结点完整地表示一条边，在整个存储结构中，有且仅有一个存储单元来表示该边。有且仅有一个存储单元来表示该边。v3v2v4v10 v11 v22 v33 v410002211333230各种存储结构的适用类型各种存储结构的适用类型 邻接矩阵：有向图和无向图邻接矩阵：有向图和无向图 邻接表（逆邻接表）：有向图和无向图邻接表（逆邻接表）：有向图和无向图 十字链表：有向图十字链表：有向图 邻接多重表：无向图邻接多重表：无向图3

27、18.3.1 图的遍历的概念图的遍历的概念 图的遍历：图的遍历：从给定图中任意指定的顶点从给定图中任意指定的顶点(称为称为初始点初始点)出发，出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点个顶点仅被访问一次仅被访问一次。 如果给定图是如果给定图是连通的无向图或者是强连通的有向图，连通的无向图或者是强连通的有向图，则遍历过程一次就能完成则遍历过程一次就能完成，并可按访问的先后顺序，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。得到由该图所有顶点组成的一个序列。 根据搜索方法的不同，图的遍历方法有两种：根据搜索方法的不同，图

28、的遍历方法有两种：深度优先搜索法深度优先搜索法(DFS)广度优先搜索法广度优先搜索法(BFS)8.3 图的遍历图的遍历需 要 用 一 个 数 组需 要 用 一 个 数 组visitedn记录每个顶点记录每个顶点的访问情况，以免同一的访问情况，以免同一个顶点被访问多次个顶点被访问多次32 1、从图中某个初始顶点、从图中某个初始顶点v出发，访问该顶点出发，访问该顶点 2、选择一个、选择一个与顶点与顶点v相邻且没被访问过的顶点相邻且没被访问过的顶点w为为初始顶点，再从初始顶点，再从w出发进行深度优先搜索，直到图出发进行深度优先搜索，直到图中与当前顶点中与当前顶点v连通的所有顶点都被访问过为止。连通的

29、所有顶点都被访问过为止。 显然，这个遍历过程是个显然，这个遍历过程是个递归过程递归过程。 3、此时若图中尚有顶点未被访问，则另选图中下、此时若图中尚有顶点未被访问，则另选图中下一个未被访问的顶点作起始点，访问该顶点，继续一个未被访问的顶点作起始点，访问该顶点，继续过程过程2。8.3.2 深度优先遍历深度优先遍历33abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志: :访问次序访问次序: :achdkfe34图的深度优先遍历图的深度优先遍历 已知图已

30、知图G的邻接表如图所示，其从顶点的邻接表如图所示，其从顶点V1出发的深度优先搜索序列为出发的深度优先搜索序列为_。V6V1143V2V3V4V5245352012345V6v1 v2 v3v6 v5 v4 35typedef struct ANode /*弧的结点结构类型弧的结点结构类型*/int adjvex; /*该弧的终点位置该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针指向下一条弧的指针*/ InfoType info; /*该弧的相关信息该弧的相关信息*/ ArcNode;typedef struct Vnode /*邻接表头结点的类型邻接表

31、头结点的类型*/Vertex data; /*顶点信息顶点信息*/ ArcNode *firstarc; /*指向第一条弧指向第一条弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是邻接表类型是邻接表类型*/typedef struct AdjList adjlist; /*邻接表邻接表*/ int n,e; /*图中顶点数图中顶点数n和边数和边数e*/ ALGraph; /*图的类型图的类型*/邻接表存储结构的定义邻接表存储结构的定义36void DFS(ALGraph *G,int v) ArcNode *p; visitedv=1; /*置已访问

32、标记置已访问标记*/ printf(%d ,v); /*输出被访问顶点的编号输出被访问顶点的编号*/ p=G-adjlistv.firstarc; /*p指向顶点指向顶点v的第一条弧的弧头结点的第一条弧的弧头结点*/ while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); /*若若p-adjvex顶点未访问顶点未访问,递归访问它递归访问它*/ p=p-nextarc; /*p指向顶点指向顶点v的下一条弧的弧头结点的下一条弧的弧头结点*/ v是初始顶点编号，是初始顶点编号，visited是一个是一个全局数组全局数组，初始，初始时所有元素均为

33、时所有元素均为0表示所有顶点尚未访问过表示所有顶点尚未访问过37图的深度优先遍历图的深度优先遍历int visitedMAXNODE / 访问标志数组访问标志数组void DFSTraverse(ALGraph G) for(i=0；in；i+) visitedi=0； for(i=0；in；i+) if(visitedi=0) DFS(G, i)； / DFSTraverseDFS的调用次数即的调用次数即为连通分量的个数为连通分量的个数38 1、访问初始点、访问初始点vi 2、接着访问、接着访问vi的所有未被访问过的邻接点的所有未被访问过的邻接点v1,v2,vt 3、然后再按照、然后再按照v

34、1,v2,vt的次序，访问每一个顶点的次序，访问每一个顶点的所有未被访问过的邻接点的所有未被访问过的邻接点 依次类推，直到图中所有和初始点依次类推，直到图中所有和初始点vi有路径相通的有路径相通的顶点都被访问过为止。顶点都被访问过为止。8.3.3 广度优先遍历广度优先遍历39图的广度优先遍历图的广度优先遍历v2v4v1v5v3v6v7v8广度优先搜索广度优先搜索v1-v2-v3-v4-v5-v6-v7-v8v2v4v1v5v3v6v7v8回边回边40图的广度优先遍历图的广度优先遍历 已知图已知图G的邻接表如图所示，其从顶点的邻接表如图所示，其从顶点V1出出发的广度优先搜索序列为发的广度优先搜索

35、序列为_。 V6V1143V2V3V4V5245352012345V6v1 v2 v5v4 v3 v6 41void BFS(ALGraph *G,int v) ArcNode *p; int w,i; int queueMAXV,front=0,rear=0;/*定义循环队列定义循环队列*/ int visitedMAXV; /*定义存放结点的访问标志的数组定义存放结点的访问标志的数组*/ for (i=0;in;i+) visitedi=0; /*访问标志数组初始化访问标志数组初始化*/ printf(%2d,v); /*输出被访问顶点的编号输出被访问顶点的编号*/ visitedv=1;

36、 /*置已访问标记置已访问标记*/ rear=(rear+1)%MAXV; queuerear=v; /*v进队进队*/ while (front!=rear) /*若队列不空时循环若队列不空时循环*/ front=(front+1)%MAXV; w=queuefront; /*出队并赋给出队并赋给w*/ p=G-adjlistw.firstarc; /*找找w的第一个邻接点的第一个邻接点*/ while (p!=NULL) if (visitedp-adjvex=0) printf(“%2d”,p-adjvex); /*访问之访问之*/visitedp-adjvex=1; rear=(rea

37、r+1)%MAXV;/*该顶点进队该顶点进队*/queuerear=p-adjvex; p=p-nextarc; /*找下一个邻接顶点找下一个邻接顶点*/ printf(n);42思考思考 题题 1 对一个图进行遍历为什么可以得到不同的对一个图进行遍历为什么可以得到不同的遍历序列？遍历序列？ 主要因素有：主要因素有： 开始遍历的顶点不同；开始遍历的顶点不同； 邻接点的顺序不同；邻接点的顺序不同；43思考思考 题题 2 遍历图的过程实质上是遍历图的过程实质上是_，breath-first search和和depth-first search的不同之处在于的不同之处在于_，反映在数据结构上的差别是

38、，反映在数据结构上的差别是_。 （1）：查找顶点的邻接点的过程；）：查找顶点的邻接点的过程； （2）：访问顶点的顺序不同；）：访问顶点的顺序不同； （3）：队列和栈）：队列和栈448.3.4 非连通图的遍历非连通图的遍历（略）（略） 在对无向图进行遍历时：在对无向图进行遍历时： 对于对于连通图连通图，仅需调用遍历过程，仅需调用遍历过程(DFS或或BFS)一次一次，从图中，从图中任一顶点出发，便可以遍历图中的各个顶点。任一顶点出发，便可以遍历图中的各个顶点。 对于对于非连通图非连通图，则需，则需多次调用多次调用遍历过程，每次调用得到的遍历过程，每次调用得到的顶点集连同相关的边就构成图的一个连通分

39、量。顶点集连同相关的边就构成图的一个连通分量。调用两次调用两次DFSDFS（分别从（分别从A、D出发），得到的顶点访问序列出发），得到的顶点访问序列分别为：分别为： A, B, C D, E, F ACBDEFDEFBCA45确定连通分量的个数确定连通分量的个数 number=0; for(i=0；in; i+) if(visitedi=0) + number; DFS(G, i)； 468.4.1 生成树的概念生成树的概念 一个连通图的生成树是一个一个连通图的生成树是一个极小连通子图极小连通子图，它含有，它含有图中全部顶点，但只有构成一棵树的图中全部顶点，但只有构成一棵树的n-1条边。条边。

40、 如果一个图有如果一个图有n个顶点和小于个顶点和小于(n-1)条边，则是非连通条边，则是非连通图。如果它多于图。如果它多于n-1条边，则一定有回路。条边，则一定有回路。 生成树的构成：生成树的构成： 设设G=(V,E)为连通图，则从图中任一顶点出发遍历图时，为连通图，则从图中任一顶点出发遍历图时，必定将必定将E(G)分成两个集合分成两个集合T和和B，其中，其中T是遍历图过程中是遍历图过程中走走过的边过的边的集合，的集合，B是是剩余的边剩余的边的集合。的集合。 G=(V,T)是是G的极小连通子图，即的极小连通子图，即G是是G的一棵生成树。的一棵生成树。 8.4 生成树和最小生成树生成树和最小生成

41、树47 深度优先遍历得到的生成树称为深度优先遍历得到的生成树称为深度优先生成树深度优先生成树；由广度优先遍历得到的生成树称为由广度优先遍历得到的生成树称为广度优先生成树广度优先生成树。8.4.2 无向图的连通分量和生成树无向图的连通分量和生成树生成树不唯一生成树不唯一v3v2v1v4v3v2v1v4v3v2v4v1例例8.1148最小生成树最小生成树图的最小生成树：图的最小生成树：图的所有生成树中，图的所有生成树中，边上的权边上的权值之和最小值之和最小的树。的树。 实际问题：实际问题： 假设要在假设要在n个城市之间建立通信网络。则连通这个城市之间建立通信网络。则连通这n个城市只需要个城市只需要

42、n-1条通信线路，条通信线路，如何在最节省经如何在最节省经费的前提下建立这个通讯网？费的前提下建立这个通讯网？ 该问题等价于：该问题等价于： 在含有在含有n个顶点的连通图的所有生成树中，选择个顶点的连通图的所有生成树中，选择一棵，使得一棵，使得各边权值之和最小各边权值之和最小。49 假设假设G=(V,E)是一个具有是一个具有n个顶点的带权连通无向图，个顶点的带权连通无向图，T=(U,TE)是是G的最小生成树。的最小生成树。 由由G构造最小生成树构造最小生成树T的步骤如下：的步骤如下：(1)初始化初始化U=v，以以v到其他顶点的所有边为候选边到其他顶点的所有边为候选边；(2)重复以下步骤重复以下

43、步骤n-1次次,使得其他使得其他n-1个顶点被加入到个顶点被加入到U中：中： 从候选边中挑选从候选边中挑选权值最小的边权值最小的边加入加入TE，设该边，设该边在在V-U中的顶点是中的顶点是vk，将，将vk加入加入U中；中； 考察当前考察当前V-U中的所有顶点中的所有顶点vj，修改候选边修改候选边：若：若(vk,vj)的权值小于原来和的权值小于原来和vj关联的候选边，则用关联的候选边，则用(vk,vj)取代后者作为候选边。取代后者作为候选边。8.4.3 普里姆算法普里姆算法50Prim算法的实现算法的实现 设立辅助数组设立辅助数组closedge，对每个顶点，对每个顶点 ，存在一个相应分量存在一

44、个相应分量 ，记录从，记录从U到到 vi的所有边中代价最小的边。的所有边中代价最小的边。 数组数组closedge包括两个域：包括两个域： lowcost域域存放该边上的权存放该边上的权 adjvex域域存放该边依附的在存放该边依附的在U中的顶点中的顶点 显然：显然：（其中（其中 表示赋予边的权）表示赋予边的权）UVvii1.cosmincos ( ,)|closedge ilowtt u vuU 1 iclosedgeicos ( ,)t u v51Prim算法举例算法举例5 0 2 1 3 4 5 (a) 1 5 6 3 5 6 6 4 2 0 2 1 3 4 5 (b) 1 0 2 1

45、3 4 5 (c) 1 4 0 2 1 3 4 5 (d) 1 4 2 0 2 1 3 4 5 (e) 1 5 4 2 0 2 1 3 4 5 (f) 1 3 4 2 5 52Prim算法举例算法举例Adjvexlowcost 0 0 0 0 00,1,2,3,4,5 closedge 12 3 4 5 U VUAdjvexlowcost0601 10501,2,3,4,5Adjvexlowcost2500526240,21,3,4,5Adjvexlowcost25 0522600,2,51,3,4Adjvexlowcost25 0 02600,2,3,51,4Adjvexlowcost 0

46、0 013 00,1,2,3,54i 53克鲁斯卡尔克鲁斯卡尔(Kruskal)算法是一种算法是一种按权值的递增次序按权值的递增次序选择合适的边来构造最小生成树的方法。选择合适的边来构造最小生成树的方法。假设假设G=(V,E)是一个具有是一个具有n个顶点的带权连通无向图，个顶点的带权连通无向图，T=(U,TE)是是G的最小生成树，则构造最小生成树的步的最小生成树，则构造最小生成树的步骤如下：骤如下：(1) 置置U的初值等于的初值等于V(即包含有即包含有G中的全部顶点中的全部顶点)，TE的初值的初值为空集为空集(即图即图T中每一个顶点都构成一个分量中每一个顶点都构成一个分量)。(2) 将图将图G

47、中的边按权值从小到大的顺序依次选取：中的边按权值从小到大的顺序依次选取：若选取的若选取的边未使生成树边未使生成树T形成回路，则加入形成回路，则加入TE；否则舍弃，直到；否则舍弃，直到TE中包中包含含(n-1)条边为止。条边为止。8.4.4 克鲁斯卡尔算法克鲁斯卡尔算法54克鲁斯卡尔算法举例克鲁斯卡尔算法举例5 0 2 1 3 4 5 1 5 6 3 5 6 6 4 2 (e) 4 1 0 2 1 3 4 5 (a) 1 0 2 1 3 4 5 (b) 1 0 2 1 3 4 5 (c) 1 0 2 1 3 4 5 (d) 1 4 2 (e) 0 2 1 3 4 5 1 3 4 2 5 2 2

48、3 3 0 0 3 5 4 1 0 0 3 3 1 1 0 0 3 3 1 1 0 0 0 0 1 1 1 1 1 1 558.5.1 路径的概念路径的概念 在一个无权的图中，若从一顶点到另一顶点存在一个无权的图中，若从一顶点到另一顶点存在着一条路径，则称该在着一条路径，则称该路径长度路径长度为该路径上所经过为该路径上所经过的边的数目，它等于该路径上的顶点数减的边的数目，它等于该路径上的顶点数减1。 由于从一顶点到另一顶点可能存在着多条路径由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同，即路径长度不每条路径上所经过的边数可能不同，即路径长度不同，我们把同，我们把路径长

49、度最短路径长度最短(即经过的边数最少即经过的边数最少)的那的那条路径叫做最短路径，其路径长度叫做条路径叫做最短路径，其路径长度叫做最短路径长最短路径长度或最短距离度或最短距离。8.5 最短路径（略）最短路径（略）56 对于对于带权的图带权的图，考虑路径上各边上的权值，则通，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的常把一条路径上所经边的权值之和定义为该路径的路径长度路径长度或称或称带权路径长度带权路径长度。 从源点到终点可能不止一条路径，把从源点到终点可能不止一条路径，把带权路径长带权路径长度最短的那条路径称为最短路径度最短的那条路径称为最短路径，其路径长度，其路

50、径长度(权值权值之和之和)称为最短路径长度或者最短距离。称为最短路径长度或者最短距离。57问题：问题： 给定一个带权有向图给定一个带权有向图G与与源点源点v，求从，求从v到到G中其他中其他顶点的最短路径，并限定各边上的权值大于或等于顶点的最短路径，并限定各边上的权值大于或等于0。 8.5.2 从一个顶点到其余各顶点的最短路径从一个顶点到其余各顶点的最短路径采用采用狄克斯特拉狄克斯特拉(Dijkstra)算法算法求解求解基本思想是：基本思想是：按按最短路径长度递增最短路径长度递增的次序产生每条最短路径的次序产生每条最短路径源点源点v1v258源点源点v1v2 从源点到顶点从源点到顶点v1的最短路

51、径是所有最短路径中长度最短者的最短路径是所有最短路径中长度最短者 在这条最短路径上，在这条最短路径上，必定只包含一条权值最小的弧必定只包含一条权值最小的弧，由此，由此，只要在所有从源点出发的弧中查找权值最小者即可只要在所有从源点出发的弧中查找权值最小者即可 长度次短者长度次短者可能有两种情况可能有两种情况： 1. 它可能是从源点直接到该顶点的路径；它可能是从源点直接到该顶点的路径； 2. 也可能是：从源点先到也可能是：从源点先到v1，再从，再从v1到该顶点；到该顶点； 其余依次类推其余依次类推 设设G=(V,E)是一个带权有向图，把图中顶点集合是一个带权有向图，把图中顶点集合V分成两组：分成两

52、组： 第一组为第一组为已求出最短路径的顶点集合已求出最短路径的顶点集合S； 第二组为其余未确定最短路径的顶点集合第二组为其余未确定最短路径的顶点集合U。59 v j k cvk wkj cvj 源点源点v到到j的最小距离的最小距离MIN(cvk+wkj,cvj)60 1 4 0 2 6 3 5 8 1 6 6 4 2 5 6 6 1 4 7 S U dist 1 2 3 4 5 60 1,2,3,4,5,6 4, 6, 6, , , 0,1 2,3,4,5,6 , 5, 6, 11, , 0,1,2 3,4,5,6 , , 6, 11, 9, 0,1,2,3 4,5,6 , , , 11, 9

53、, 0,1,2,3,5 4,6 , , , 10, , 170,1,2,3,5,4 6 , , , , , 160,1,2,3,5,4,6 , , , , , 从源点到从源点到vj的的最短路径长度最短路径长度61 问题：对于一个各边权值均大于零的有向图，对问题：对于一个各边权值均大于零的有向图，对每一对顶点每一对顶点vivj，求出，求出vi与与vj之间的最短路径和最短之间的最短路径和最短路径长度。路径长度。 可以通过以每个顶点作为源点循环求出每对顶点可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径。之间的最短路径。 弗洛伊德弗洛伊德(Floyd)算法也可用于求两顶点之间最短算法也可用于

54、求两顶点之间最短路径。路径。 8.5.3 每对顶点之间的最短路径每对顶点之间的最短路径62 假设有向图假设有向图G=(V,E)采用邻接矩阵采用邻接矩阵cost存储，另外设存储，另外设置一个二维数组置一个二维数组A用于存放当前顶点之间的最短路径用于存放当前顶点之间的最短路径长度，分量长度，分量Aij表示当前顶点表示当前顶点vi到顶点到顶点vj的最短路径的最短路径长度长度。 弗洛伊德算法的弗洛伊德算法的基本思想基本思想： 递推产生一个矩阵序列递推产生一个矩阵序列A0,A1,Ak,An 其中其中Akij表示从顶点表示从顶点vi到顶点到顶点vj的路径上所经的路径上所经过的顶点编号不大于过的顶点编号不大

55、于k的最短路径长度。的最短路径长度。 初始时初始时,有有A-1ij=costij63 当求从顶点当求从顶点vi到顶点到顶点vj的路径上所经过的顶点编号的路径上所经过的顶点编号不不大于大于k+1的最短路径长度时的最短路径长度时,要分两种情况考虑：要分两种情况考虑： 一种情况是该路径一种情况是该路径不经过不经过顶点编号为顶点编号为k+1的顶点的顶点,此此时该路径长度与从顶点时该路径长度与从顶点vi到顶点到顶点vj的路径上所经过的的路径上所经过的顶点编号不大于顶点编号不大于k的最短路径长度相同；的最短路径长度相同； 另一种情况是从顶点另一种情况是从顶点vi到顶点到顶点vj的最短路径上的最短路径上经过

56、经过编编号为号为k+1的顶点。的顶点。64 i j k+1 Aki,k+1 Akk+1,j Aki,j Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j65 该路径可分为两段该路径可分为两段: (1) 从顶点从顶点vi到顶点到顶点vk+1的最短路径的最短路径; (2) 从顶点从顶点vk+1到顶点到顶点vj的最短路径。的最短路径。 此时最短路径长度等于这两段路径长度之和。这此时最短路径长度等于这两段路径长度之和。这两种情况中的两种情况中的较小值较小值，就是所要求的从顶点，就是所要求的从顶点vi到顶点到顶点vj的路径上所经过的顶点编号不大于的路径上所经过的顶点编号不大于k+1的最

57、短路径。的最短路径。 弗洛伊德思想可用如下的表达式来描述：弗洛伊德思想可用如下的表达式来描述： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-1)66 设设G=(V,E)是一个具有是一个具有n个顶点的有向图，个顶点的有向图，V中顶中顶点序列点序列v1,v2,vn称为一个称为一个拓扑序列拓扑序列，当且仅当该顶，当且仅当该顶点序列满足下列条件：点序列满足下列条件：若若是图中的边是图中的边(即从顶点即从顶点vi到到vj有一条路径有一条路径)，则在序列中顶点则在序列中顶点vi必须排在顶点必须排在顶点vj之前。之前。 在一个有向图中找一个拓扑序列的过程

58、称为拓扑在一个有向图中找一个拓扑序列的过程称为拓扑排序。排序。 对有向图进行对有向图进行拓扑排序，拓扑排序，可检查有向图中是否存可检查有向图中是否存在回路在回路。 8.6 拓扑排序拓扑排序67课程代号课程名称先修课程C1高等数学无C2程序设计无C3离散数学C1C4数据结构C2,C3C5编译原理C2,C4C6操作系统C4,C7C7计算机组成原理C2 例如，计算机专业的学生必须完成一系列规定的基础例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。课和专业课才能毕业。 C1 C3 C4 C2 C5 C7 C6 课程之间的先后关系课程之间的先后关系可用有向图表示：可用有向图表示：拓扑序

59、列拓扑序列1：C1-C3-C2-C4-C7-C6-C5拓扑序列拓扑序列2：C2-C7-C1-C3-C4-C5-C6按照任何一个拓扑序列都可以顺序地进行课程学习。按照任何一个拓扑序列都可以顺序地进行课程学习。68 拓扑排序方法如下：拓扑排序方法如下： (1) 从有向图中选择一个从有向图中选择一个没有前驱没有前驱(即即入度为入度为0)的的顶点并且输出它。顶点并且输出它。 (2) 从网中删去该顶点，并且删去从该顶点从网中删去该顶点，并且删去从该顶点发出发出的全部有向边。的全部有向边。 (3) 重复上述两步，直到剩余的网中不再存在没重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。若此时网不空，

60、表明网中有环。有前驱的顶点为止。若此时网不空，表明网中有环。 69abcghdfeabhcdgfe一个一个AOV-网的拓扑排序网的拓扑排序70为了实现拓扑排序的算法，对于给定的有向图，为了实现拓扑排序的算法，对于给定的有向图，采用邻接表作为存储结构，为每个顶点设立一个链采用邻接表作为存储结构，为每个顶点设立一个链表，每个链表有一个表头结点，表头结点中增加一表，每个链表有一个表头结点，表头结点中增加一个个存放顶点入度的域存放顶点入度的域count。即将邻接表定义中的即将邻接表定义中的VNode类型修改如下：类型修改如下： typedef struct /*表头结点类型表头结点类型*/ Vertex data;