7第七章-图120张课件

7.1 7.1 图的定义和基本术语图的定义和基本术语图的定义和基本术语图的定义和基本术语 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历图的遍历图的遍历 7.4 7.4 图的生成树图的生成树图的生成树图的生成树 7.5 7.5 拓扑排序拓扑排序拓扑排序拓扑排序 7.6 7.6 关键路径关键路径关键路径关键路径 7.7 7.7 最短路径最短路径最短路径最短路径第七章第七章 图图 7.1 图的定义和基本术语第七章 图1图图图图(Graph)图图图图G G G G是由两个集合是由两个集合是由两个集合是由两个集合V(G)V(G)V(G)V(G)和和和和E(G)E(G)E(G)E(G)组成的组成的组成的组成的,记为记为记为记为G=(V,E)G=(V,E)G=(V,E)G=(V,E)其中：其中：其中：其中：V(G)V(G)V(G)V(G)是顶点的非空有限集是顶点的非空有限集是顶点的非空有限集是顶点的非空有限集 E(G)E(G)E(G)E(G)是边的有限集合，边是顶点的无序对或有序对是边的有限集合，边是顶点的无序对或有序对是边的有限集合，边是顶点的无序对或有序对是边的有限集合，边是顶点的无序对或有序对n 图的定义和术语图的定义和术语图的定义和术语图的定义和术语【例例例例】1 15 57 73 32 24 4G1G16 6V(G1)=1,2,3,4,5,6,7V(G1)=1,2,3,4,5,6,7V(G1)=1,2,3,4,5,6,7V(G1)=1,2,3,4,5,6,7E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)图(Graph)图G是由两个集合V(G)和E(G)组成的2无向图无向图无向图无向图 无向图无向图无向图无向图G G G G是由两个集合是由两个集合是由两个集合是由两个集合V(G)V(G)V(G)V(G)和和和和E(G)E(G)E(G)E(G)组成的组成的组成的组成的其中：其中：其中：其中：V(G)V(G)V(G)V(G)是顶点的非空有限集是顶点的非空有限集是顶点的非空有限集是顶点的非空有限集 E(G)E(G)E(G)E(G)是边的有限集合，边是顶点的无序对，记为是边的有限集合，边是顶点的无序对，记为是边的有限集合，边是顶点的无序对，记为是边的有限集合，边是顶点的无序对，记为 （v,wv,wv,wv,w）或（或（或（或（w,v)w,v)w,v)w,v)，并且（并且（并且（并且（v,w)=(w,v)v,w)=(w,v)v,w)=(w,v)v,w)=(w,v)简单的图简单的图简单的图简单的图：图中不包含顶点到其自身的弧或边，同一条弧或边图中不包含顶点到其自身的弧或边，同一条弧或边图中不包含顶点到其自身的弧或边，同一条弧或边图中不包含顶点到其自身的弧或边，同一条弧或边不在图中重复出现不在图中重复出现不在图中重复出现不在图中重复出现 有向图有向图有向图有向图&无向图无向图无向图无向图 有向图有向图有向图有向图有向图有向图有向图有向图G G G G是由两个集合是由两个集合是由两个集合是由两个集合V(G)V(G)V(G)V(G)和和和和E(G)E(G)E(G)E(G)组成的组成的组成的组成的其中：其中：其中：其中：V(G)V(G)V(G)V(G)是顶点的非空有限集是顶点的非空有限集是顶点的非空有限集是顶点的非空有限集 E(G)E(G)E(G)E(G)是有向边（也称是有向边（也称是有向边（也称是有向边（也称弧弧弧弧）的有限集合，弧是顶点的）的有限集合，弧是顶点的）的有限集合，弧是顶点的）的有限集合，弧是顶点的有序对，记为有序对，记为有序对，记为有序对，记为 v,wv,wv,w，v,wv,wv,wv,w是顶点，是顶点，是顶点，是顶点，v v v v为为为为弧尾弧尾弧尾弧尾，w w w w为为为为弧头弧头弧头弧头无向图 无向图G是由两个集合V(G)和E(G)组成的简3【有向图有向图有向图有向图G2G2】2 24 45 51 13 36 6G2G2V(G2)=1,2,3,4,5,6V(G2)=1,2,3,4,5,6V(G2)=1,2,3,4,5,6V(G2)=1,2,3,4,5,6E(G2)=,E(G2)=,E(G2)=,E(G2)=,【有向图G2】245136G2V(G2)=1,2,3,4权权权权 与图的边或弧相关的数与图的边或弧相关的数与图的边或弧相关的数与图的边或弧相关的数网网网网 带权的图叫带权的图叫带权的图叫带权的图叫 1 14 45 52 23 37 75 53 31 18 86 64 42 2G3G3子图子图子图子图 如果图如果图如果图如果图G(V,E)G(V,E)G(V,E)G(V,E)和图和图和图和图G(V,E),G(V,E),G(V,E),G(V,E),满满满满足：足：足：足：V V V V V EV EV EV E E E E E 则称则称则称则称GGGG为为为为G G G G的的的的子图子图子图子图3 35 56 62 24 45 51 13 36 6图与子图图与子图图与子图图与子图无向图无向图无向图无向图&有向图有向图有向图有向图&无向网无向网无向网无向网&有向网有向网有向网有向网 UDG DG UDN DN UDG DG UDN DN权 与图的边或弧相关的数网 带权的图叫145235有向完全图有向完全图有向完全图有向完全图 n n n n个顶点的有向图最大边数是个顶点的有向图最大边数是个顶点的有向图最大边数是个顶点的有向图最大边数是n(n-1)n(n-1)n(n-1)n(n-1)入度：入度：入度：入度：以该顶点为头的弧的数目以该顶点为头的弧的数目以该顶点为头的弧的数目以该顶点为头的弧的数目顶点的度顶点的度顶点的度顶点的度 无向图中，顶点的度为与每个顶点相关联的边数无向图中，顶点的度为与每个顶点相关联的边数无向图中，顶点的度为与每个顶点相关联的边数无向图中，顶点的度为与每个顶点相关联的边数 有向图中，顶点的度分成有向图中，顶点的度分成有向图中，顶点的度分成有向图中，顶点的度分成 入度入度入度入度 与与与与 出度出度出度出度出度出度出度出度：以该顶点为尾的弧的数目以该顶点为尾的弧的数目以该顶点为尾的弧的数目以该顶点为尾的弧的数目b ba ac c有向完全图有向完全图有向完全图有向完全图b ba ac c无向完全图无向完全图无向完全图无向完全图无向完全图无向完全图无向完全图无向完全图 n n n n个顶点的无向图最大边数是个顶点的无向图最大边数是个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2邻接点邻接点邻接点邻接点无向图无向图无向图无向图G(V,E)G(V,E)G(V,E)G(V,E)中，如果边中，如果边中，如果边中，如果边(u(u(u(u，v)Ev)Ev)Ev)E，则称顶点，则称顶点，则称顶点，则称顶点u u u u，v v v v互为邻接点，或者称顶点互为邻接点，或者称顶点互为邻接点，或者称顶点互为邻接点，或者称顶点u u u u，v v v v相关联相关联相关联相关联有向完全图 n个顶点的有向图最大边数是n(n-1)入度6【例例】245136G2顶点顶点顶点顶点2 2入度：入度：入度：入度：1 1 出度：出度：出度：出度：3 3顶点顶点顶点顶点4 4入度：入度：入度：入度：1 1 出度：出度：出度：出度：0 0【例例例例】1 15 57 73 32 24 4G1G16 6顶点顶点顶点顶点5 5的度：的度：的度：的度：3 3顶点顶点顶点顶点2 2的度：的度：的度：的度：4 4G2G2G2G2中中中中 1 1 1 1，2 2 2 2，3 3 3 3，5 5 5 5，6 6 6 6 是一条路径是一条路径是一条路径是一条路径 G1G1G1G1中中中中 1 1 1 1，2 2 2 2，5 5 5 5，7 7 7 7 是一条路径是一条路径是一条路径是一条路径例如例如例如例如路径路径路径路径 路径是顶点的序列路径是顶点的序列路径是顶点的序列路径是顶点的序列V=VV=VV=VV=Vi0i0i0i0,V,V,V,Vi1i1i1i1,V,V,V,Vinininin ，满足满足满足满足 (V V V Vij-1ij-1ij-1ij-1,V,V,V,Vijijijij)E E E E（1j1j1j1j n)n)n)n)【例】245136G2顶点2入度：1 出度：3【例】17路径长度路径长度路径长度路径长度路径上边或弧的数目或沿路径各边权值之和路径上边或弧的数目或沿路径各边权值之和路径上边或弧的数目或沿路径各边权值之和路径上边或弧的数目或沿路径各边权值之和回路回路回路回路第一个顶点和最后一个顶点相同的路径第一个顶点和最后一个顶点相同的路径第一个顶点和最后一个顶点相同的路径第一个顶点和最后一个顶点相同的路径简单路径简单路径简单路径简单路径序列中顶点不重复出现的路径序列中顶点不重复出现的路径序列中顶点不重复出现的路径序列中顶点不重复出现的路径简单回路简单回路简单回路简单回路除了第一个顶点和最后一个顶点外，其余顶点不除了第一个顶点和最后一个顶点外，其余顶点不除了第一个顶点和最后一个顶点外，其余顶点不除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路重复出现的回路叫简单回路重复出现的回路叫简单回路重复出现的回路叫简单回路a ae eg gc cb bf fG1G1d d a a a a，b b b b，e e e e，d d d d 路径长度是路径长度是路径长度是路径长度是3 3 3 3bdeacfG2 a a a a，b b b b，c c c c，e e e e 是一条路径是一条路径是一条路径是一条路径路径长度路径上边或弧的数目或沿路径各边权值之和回路第8连通连通连通连通无向图从顶点无向图从顶点无向图从顶点无向图从顶点v v到顶点到顶点到顶点到顶点ww有一条路径，则说有一条路径，则说有一条路径，则说有一条路径，则说v v和和和和ww是连是连是连是连通的通的通的通的连通图连通图连通图连通图无向图中任意两个顶点都是连通的叫连通图无向图中任意两个顶点都是连通的叫连通图无向图中任意两个顶点都是连通的叫连通图无向图中任意两个顶点都是连通的叫连通图连通分量连通分量连通分量连通分量无向图的极大连通子图叫连通分量无向图的极大连通子图叫连通分量无向图的极大连通子图叫连通分量无向图的极大连通子图叫连通分量【连通图连通图连通图连通图】b bd de ea ac cf fb bd de ea ac cf f【有有有有2 2个连通分量的无向图个连通分量的无向图个连通分量的无向图个连通分量的无向图】连通无向图从顶点v到顶点w有一条路径，则说v和w是连通的9强连通分量强连通分量强连通分量强连通分量有向图的极大强连通子图叫强连通分量有向图的极大强连通子图叫强连通分量有向图的极大强连通子图叫强连通分量有向图的极大强连通子图叫强连通分量强连通图强连通图强连通图强连通图有向图中，如果对每一对有向图中，如果对每一对有向图中，如果对每一对有向图中，如果对每一对顶点间顶点间顶点间顶点间都存在路径，则称都存在路径，则称都存在路径，则称都存在路径，则称 G G 强连通图强连通图强连通图强连通图【强连通图强连通图强连通图强连通图】A AB BC C【有有有有2 2个强连通分量的有向图个强连通分量的有向图个强连通分量的有向图个强连通分量的有向图】A AB BC CD DE E强连通分量有向图的极大强连通子图叫强连通分量强连通图10【例例例例】1 15 57 73 32 24 4G2G26 6【例例例例】2 24 45 51 13 36 6G1G1路径：路径：路径：路径：1 1，2 2，3 3，5 5，6 6，3 3路径：路径：路径：路径：1 1，2 2，5 5，7 7，6 6，5 5，2 2，3 3简单回路：简单回路：简单回路：简单回路：3 3，5 5，6 6，3 3路径长度：路径长度：路径长度：路径长度：5 5简单路径：简单路径：简单路径：简单路径：1 1，2 2，3 3，5 5回路：回路：回路：回路：1 1，2 2，3 3，5 5，6 6，3 3，1 1简单回路：简单回路：简单回路：简单回路：1 1，2 2，3 3，1 1路径长度：路径长度：路径长度：路径长度：7 7简单路径：简单路径：简单路径：简单路径：1 1，2 2，5 5，7 7，6 6回路：回路：回路：回路：1 1，2 2，5 5，7 7，6 6，5 5，2 2，1 1【例】157324G26【例】245136G1路径：1，2，11 7.1 7.1 图的定义和基本术语图的定义和基本术语图的定义和基本术语图的定义和基本术语 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历图的遍历图的遍历 7.4 7.4 图的生成树图的生成树图的生成树图的生成树 7.5 7.5 拓扑排序拓扑排序拓扑排序拓扑排序 7.6 7.6 关键路径关键路径关键路径关键路径 7.7 7.7 最短路径最短路径最短路径最短路径第七章第七章 图图 7.1 图的定义和基本术语第七章 图12 7.2.1 7.2.1 邻接矩阵邻接矩阵邻接矩阵邻接矩阵 7.2.2 7.2.2 邻接表邻接表邻接表邻接表 7.2.3 7.2.3 十字链表十字链表十字链表十字链表 7.2 4 7.2 4 邻接多重表邻接多重表邻接多重表邻接多重表7.2 图的存储结构图的存储结构 7.2.1 邻接矩阵7.2 图的存储结构13n邻接矩阵邻接矩阵邻接矩阵邻接矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵例例例例G2G22 24 41 13 3例例例例15324G1G1 定义：定义：定义：定义：设设设设G=(V,E)G=(V,E)G=(V,E)G=(V,E)是有是有是有是有n n n n 1 1 1 1个顶点的图，个顶点的图，个顶点的图，个顶点的图，G G G G的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵A A A A是具有以是具有以是具有以是具有以下性质的下性质的下性质的下性质的n n n n阶方阵阶方阵阶方阵阶方阵 0 00 00 01 11 10 00 00 00 00 00 00 00 01 11 10 0 0 00 01 11 10 00 00 01 10 01 11 11 10 01 10 01 10 01 10 01 10 01 10 01 10 01 1Ai,j=Ai,j=0 0若若若若(v(v(v(vi i i i,v,v,v,vj j j j)或或或或vvv E E E E其它其它其它其它邻接矩阵表示顶点间相联关系的矩阵例G22413例1532141 14 45 52 23 37 75 53 31 18 86 64 42 2 6 61 18 83 36 6 2 24 4 1 12 2 7 78 84 4 5 53 3 7 75 5 创建一个以邻接矩阵存储的图创建一个以邻接矩阵存储的图创建一个以邻接矩阵存储的图创建一个以邻接矩阵存储的图 网的邻接矩阵可定义为：网的邻接矩阵可定义为：网的邻接矩阵可定义为：网的邻接矩阵可定义为：=，其它，其它，其它，其它E(G)E(G)v v,v v或或或或)v v,(v(v若若若若,j ji ij ji iij ijj ji iA Aw w w w145237531864215typedef struct typedef struct ArcCellArcCell VRType adj;VRType adj;InfoType *info;InfoType *info;ArcCell,AdjMatrixMAXMAX;ArcCell,AdjMatrixMAXMAX;typedef struct typedef struct MGraphMGraph VertexType vexsMAX_VERTEX_NUM;VertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;AdjMatrix arcs;int vexnum,arcnum;int vexnum,arcnum;GraphKind kind;GraphKind kind;MGraph;MGraph;Mgraph G;Mgraph G;typedef struct ArcCellMgraph G16例例aecbdG1 0 00 01 11 10 00 00 01 10 01 11 11 10 01 10 01 10 01 10 01 10 01 10 01 10 0G Gvexsvexsarcsarcsvexnumvexnumarcnumarcnumkindkind6 65 5UDGUDGa b c d ea b c d e例aecbdG1001117n n特点：特点：特点：特点：pp 有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有n n n n个顶点的有向图需存个顶点的有向图需存个顶点的有向图需存个顶点的有向图需存储空间为储空间为储空间为储空间为nnnnpp 无向图中顶点无向图中顶点无向图中顶点无向图中顶点ViViViVi的度是邻接矩阵的度是邻接矩阵的度是邻接矩阵的度是邻接矩阵A A A A中第中第中第中第i i i i行元素之和行元素之和行元素之和行元素之和pp 有向图中，有向图中，有向图中，有向图中，顶点顶点顶点顶点ViViViVi的出度是的出度是的出度是的出度是A A A A中第中第中第中第i i i i行元素之和行元素之和行元素之和行元素之和 顶点顶点顶点顶点ViViViVi的入度是的入度是的入度是的入度是A A A A中第中第中第中第i i i i列元素之和列元素之和列元素之和列元素之和p 无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有n n n n个顶点的无个顶点的无个顶点的无个顶点的无向图需存储空间为向图需存储空间为向图需存储空间为向图需存储空间为n(n+1)/2n(n+1)/2n(n+1)/2n(n+1)/2特点：有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空18n邻接表邻接表邻接表邻接表 实现实现实现实现：为图中每个顶点建立一个单链表，第为图中每个顶点建立一个单链表，第为图中每个顶点建立一个单链表，第为图中每个顶点建立一个单链表，第i i i i个单链表中的个单链表中的个单链表中的个单链表中的结点表示依附于顶点结点表示依附于顶点结点表示依附于顶点结点表示依附于顶点ViViViVi的边（有向图中指以的边（有向图中指以的边（有向图中指以的边（有向图中指以ViViViVi为尾的弧）为尾的弧）为尾的弧）为尾的弧）例例例例G1G1b bd da ac c1 12 23 34 4a ac cd db bvexdatavexdatafirstarcfirstarc 3 3 2 2 4 4 1 1 adjvexadjvexnextarcnextarc邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的19a ae ec cb bd dG2G21 12 23 34 4a ac cd db bdatadatafirtarcfirtarc 4 4 2 2 1 1 2 2 adjvexadjvex nextarcnextarc5 5e e 4 4 3 3 5 5 1 1 5 5 3 3 2 2 3 3 创建一个以邻接表存储的图创建一个以邻接表存储的图创建一个以邻接表存储的图创建一个以邻接表存储的图aecbdG21234acdbdatafirtarc 4 220n n特点特点特点特点G1G1b bd da ac c1 12 23 34 4a ac cd db bdatadata firstarcfirstarc 4 4 1 1 1 1 3 3 adjvexadjvex nextarcnextarcpp 有向图中有向图中有向图中有向图中n n 顶点顶点顶点顶点ViViViVi的出度为第的出度为第的出度为第的出度为第i i i i个单链表中的结点个数个单链表中的结点个数个单链表中的结点个数个单链表中的结点个数n n 顶点顶点顶点顶点ViViViVi的入度为整个的入度为整个的入度为整个的入度为整个单链表中邻接点域值是单链表中邻接点域值是单链表中邻接点域值是单链表中邻接点域值是i i i i的结点的结点的结点的结点个数个数个数个数pp 无向图中顶点无向图中顶点无向图中顶点无向图中顶点ViViViVi的度为第的度为第的度为第的度为第i i i i个单链表中的结点数个单链表中的结点数个单链表中的结点数个单链表中的结点数pp 逆邻接表：有向图中对每个结点建立以逆邻接表：有向图中对每个结点建立以逆邻接表：有向图中对每个结点建立以逆邻接表：有向图中对每个结点建立以ViViViVi为头的弧的单链表为头的弧的单链表为头的弧的单链表为头的弧的单链表特点G1bdac1234acdbdatafirstarc 421n 有向图的十字链表表示法有向图的十字链表表示法有向图的十字链表表示法有向图的十字链表表示法b bd da ac c 创建一个以十字链表存储的图创建一个以十字链表存储的图创建一个以十字链表存储的图创建一个以十字链表存储的图 0 20 2 0 10 1 2 32 3 2 02 0 3 23 2 3 13 1 3 03 0tailvex headvex hlink tlink a ab b c cd d0 01 12 23 3data firstin firstout 有向图的十字链表表示法bdac创建一个以十22n无向图的邻接多重表表示法无向图的邻接多重表表示法无向图的邻接多重表表示法无向图的邻接多重表表示法a ae ec cb bd d 创建一个以邻接多重表存储的图创建一个以邻接多重表存储的图创建一个以邻接多重表存储的图创建一个以邻接多重表存储的图0 01 12 23 3a ac cd db b4 4e e 0 10 1 0 30 3 2 32 3 2 12 1 2 4 2 4 4 14 1ivex jvex ilink jlink data firstedge 无向图的邻接多重表表示法aecbd创建一个以邻接多23 7.1 7.1 图的定义和基本术语图的定义和基本术语图的定义和基本术语图的定义和基本术语 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历图的遍历图的遍历 7.4 7.4 图的生成树图的生成树图的生成树图的生成树 7.5 7.5 拓扑排序拓扑排序拓扑排序拓扑排序 7.6 7.6 关键路径关键路径关键路径关键路径 7.7 7.7 最短路径最短路径最短路径最短路径第七章第七章 图图 7.1 图的定义和基本术语第七章 图247.3.1 7.3.1 深度优先遍历深度优先遍历深度优先遍历深度优先遍历DFSDFS7.3.2 7.3.2 广度优先遍历广度优先遍历广度优先遍历广度优先遍历BFSBFS 7.3 图的遍历图的遍历7.3.1 深度优先遍历DFS7.3 图的遍历25 遍历图：遍历图：遍历图：遍历图：从图中某个顶点出发游历图，访遍图中其余顶点，从图中某个顶点出发游历图，访遍图中其余顶点，从图中某个顶点出发游历图，访遍图中其余顶点，从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。并且使图中的每个顶点仅被访问一次的过程。并且使图中的每个顶点仅被访问一次的过程。并且使图中的每个顶点仅被访问一次的过程。n n 深度优先遍历深度优先遍历深度优先遍历深度优先遍历 DFSDFSDFSDFSn n 广度优先遍历广度优先遍历广度优先遍历广度优先遍历 BFSBFSBFSBFS两种遍历方法：两种遍历方法：两种遍历方法：两种遍历方法：遍历图：从图中某个顶点出发游历图，访遍图中其余顶点，并且26n n深度优先遍历深度优先遍历深度优先遍历深度优先遍历(DFS)(DFS)V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8深度遍历：深度遍历：深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V5 V5 V3 V3 V6 V6 V7V7方法：方法：方法：方法：从图的某一顶点从图的某一顶点从图的某一顶点从图的某一顶点V0V0V0V0出发，访问此顶点；然后依次从出发，访问此顶点；然后依次从出发，访问此顶点；然后依次从出发，访问此顶点；然后依次从V0V0V0V0的的的的未被访问的邻接点出发，深度优先遍历图，直至图中所有和未被访问的邻接点出发，深度优先遍历图，直至图中所有和未被访问的邻接点出发，深度优先遍历图，直至图中所有和未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0V0V0V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中选图中一个未被访问的顶点作起点，重复上述过程，直至图中选图中一个未被访问的顶点作起点，重复上述过程，直至图中选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止所有顶点都被访问为止所有顶点都被访问为止所有顶点都被访问为止深度优先遍历(DFS)V1V2V4V5V3V7V6V8深度遍27V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8深度遍历：深度遍历：深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V5 V5 V6 V6 V3 V3 V7V7深度遍历：深度遍历：深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V5 V5 V6 V6 V3 V3 V7V7V1V2V4V5V3V7V6V8V1V2V4V5V3V7V628V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8深度遍历：深度遍历：深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V3 V3 V6 V6 V7 V7 V5V5V1V2V4V5V3V7V6V8深度遍历：V1 V2 V298 81 16 62 27 73 35 55 51 14 42 28 87 76 64 43 34 42 25 58 87 73 36 61 1V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8例例例例深度遍历：深度遍历：深度遍历：深度遍历：816273551428764342587361V1V2V430V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8深度遍历：深度遍历：深度遍历：深度遍历：V1V11 12 23 34 41 13 34 42 2vexdatavexdatafirstarcfirstarc 2 2 7 7 8 8 3 3 adjvexadjvexnextnext5 55 5 6 6 4 4 1 1 5 5 1 1 2 2 8 8 2 2 6 67 78 86 67 78 8 7 7 3 3 6 6 3 3 5 5 4 4 V3 V3 V7 V7 V6 V6 V2 V2 V5 V5 V8 V8 V4V4V1V2V4V5V3V7V6V8深度遍历：V112341331V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 81 12 23 34 41 13 34 42 2vexdatavexdatafirstarcfirstarc 2 2 7 7 8 8 3 3 adjvexadjvexnextnext5 55 5 6 6 4 4 8 8 2 2 6 67 78 86 67 78 8 7 7 深度遍历：深度遍历：V1V3 V7 V6 V2 V2 V4 V4 V8 V8 V5V5V1V2V4V5V3V7V6V812341342vexdat32n n深度优先遍历算法深度优先遍历算法深度优先遍历算法深度优先遍历算法 递归算法递归算法递归算法递归算法方法：方法：方法：方法：1 1 1 1）选定任意一点作起始点）选定任意一点作起始点）选定任意一点作起始点）选定任意一点作起始点2 2 2 2）访问起始点，并标注）访问起始点，并标注）访问起始点，并标注）访问起始点，并标注“已访问已访问已访问已访问”3 3 3 3）对起始点的每一个邻接点进行如下操作：若该邻接点）对起始点的每一个邻接点进行如下操作：若该邻接点）对起始点的每一个邻接点进行如下操作：若该邻接点）对起始点的每一个邻接点进行如下操作：若该邻接点未访问过，以它作为新的起始点进行未访问过，以它作为新的起始点进行未访问过，以它作为新的起始点进行未访问过，以它作为新的起始点进行2 2 2 2）3 3 3 3）的操作。）的操作。）的操作。）的操作。（算法特点：递归）（算法特点：递归）（算法特点：递归）（算法特点：递归）深度优先遍历算法 递归算法方法：33DFSTraverse DFSTraverse()()for()DFS(G,v)for()DFS(G,v)/对非连通图需要多次出发对非连通图需要多次出发对非连通图需要多次出发对非连通图需要多次出发DFSDFSDFSDFS DFSDFS()()/以以以以v v v v为起点深度遍历为起点深度遍历为起点深度遍历为起点深度遍历 visit(v);visit(v);/访问顶点访问顶点访问顶点访问顶点v v v v for(w=for(w=v v的第一个邻接点的第一个邻接点的第一个邻接点的第一个邻接点;w;w=;w;w=v v的下一个邻接点的下一个邻接点的下一个邻接点的下一个邻接点)DFS(G,w);DFS(G,w);DFSTraverse()34n n广度优先遍历广度优先遍历广度优先遍历广度优先遍历(BFS)(BFS)(BFS)(BFS)V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8广度遍历：广度遍历：广度遍历：广度遍历：V1V1 V2 V2 V3 V3 V4 V4 V5 V5 V6 V6 V7 V7 V8V8方法：方法：方法：方法：从图的某一顶点从图的某一顶点从图的某一顶点从图的某一顶点V0V0V0V0出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问V0V0V0V0的各个未曾访问过的邻接点；然后分别从这些邻接点出的各个未曾访问过的邻接点；然后分别从这些邻接点出的各个未曾访问过的邻接点；然后分别从这些邻接点出的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻发，广度优先遍历图，直至图中所有已被访问的顶点的邻发，广度优先遍历图，直至图中所有已被访问的顶点的邻发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选接点都被访问到；若此时图中尚有顶点未被访问，则另选接点都被访问到；若此时图中尚有顶点未被访问，则另选接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图图中一个未被访问的顶点作起点，重复上述过程，直至图图中一个未被访问的顶点作起点，重复上述过程，直至图图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止中所有顶点都被访问为止中所有顶点都被访问为止中所有顶点都被访问为止。广度优先遍历(BFS)V1V2V4V5V3V7V6V8广度遍35V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8广度遍历：广度遍历：广度遍历：广度遍历：V1V1 V2 V2 V3 V3 V4 V4 V5 V5 V6 V6 V7 V7 V8V8广度遍历：广度遍历：广度遍历：广度遍历：V1V1 V2 V2 V3 V3 V4 V4 V5 V5 V6 V6 V7 V7 V8V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V636V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8广度遍历：广度遍历：广度遍历：广度遍历：V1V1 V2 V2 V3 V3 V4 V4 V6 V6 V7 V7 V8 V8 V5V5V1V2V4V5V3V7V6V8广度遍历：V1 V2 V378 81 16 62 27 73 35 55 51 14 42 28 87 76 64 43 33 32 25 54 48 86 67 71 1V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8例例例例广度遍历：广度遍历：广度遍历：广度遍历：816273551428764332548671V1V2V438V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8广度遍历：广度遍历：广度遍历：广度遍历：V1V11 12 23 34 41 13 34 42 2vexdatavexdatafirstarcfirstarc 2 2 7 7 8 8 3 3 adjvexadjvexnextnext5 55 5 6 6 4 4 1 1 5 5 1 1 2 2 8 8 2 2 6 67 78 86 67 78 8 7 7 3 3 6 6 3 3 5 5 4 4 V3 V3 V2 V2 V5 V5 V3 V3 V7 V7 V5 V5 V8V8V1V2V4V5V3V7V6V8广度遍历：V1123413391 14 42 23 35 51 12 23 34 41 13 34 42 2vexdatavexdatafirstarcfirstarc 5 5 5 5 4 4 3 3 adjvexadjvexnextnext5 55 5 1 1 5 5 1 1 1 1 4 4 3 3 2 2 2 20 1 2 3 4 50 1 2 3 4 51 1f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 10 1 2 3 4 50 1 2 3 4 54 4f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 41 40 1 2 3 4 50 1 2 3 4 54 34 3f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 31 4 31423512341342vexdatafirstarc 5401 12 23 34 41 13 34 42 2vexdatavexdatafirstarcfirstarc 5 5 5 5 4 4 3 3 adjvexadjvexnextnext5 55 5 1 1 5 5 1 1 1 1 4 4 3 3 2 2 2 20 1 2 3 4 50 1 2 3 4 54 3 24 3 2f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 3 21 4 3 20 1 2 3 4 50 1 2 3 4 5 3 23 2f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 3 21 4 3 20 1 2 3 4 50 1 2 3 4 5 3 2 53 2 5f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 3 2 51 4 3 2 51 14 42 23 35 512341342vexdatafirstarc 5 5 4 410 1 2 3 4 50 1 2 3 4 5 2 52 5f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 3 2 51 4 3 2 50 1 2 3 4 50 1 2 3 4 5 5 5f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 3 2 51 4 3 2 50 1 2 3 4 50 1 2 3 4 5 f fr r遍历序列：遍历序列：遍历序列：遍历序列：1 4 3 2 51 4 3 2 51 12 23 34 41 13 34 42 2vexdatavexdatafirstarcfirstarc 5 5 5 5 4 4 3 3 adjvexadjvexnextnext5 55 5 1 1 5 5 1 1 1 1 4 4 3 3 2 2 2 21 14 42 23 35 50 1 2 3 4 5 42BFSTraverse BFSTraverse()()for()for()/对于非连通图需要有多个起始点对于非连通图需要有多个起始点对于非连通图需要有多个起始点对于非连通图需要有多个起始点 EnQueue(v)EnQueue(v)/v/v/v/v是起点是起点是起点是起点 Visit(v)Visit(v)while()while()/队列不空队列不空队列不空队列不空 DeQueue()DeQueue()while()while()/所有邻接点入队一个访问一个所有邻接点入队一个访问一个所有邻接点入队一个访问一个所有邻接点入队一个访问一个 EnQueue EnQueue（ww）Visit(w)Visit(w)广度优先遍历算法广度优先遍历算法广度优先遍历算法广度优先遍历算法BFSTraverse()广度优先遍历算法43 7.1 7.1 图的定义和基本术语图的定义和基本术语图的定义和基本术语图的定义和基本术语 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历图的遍历图的遍历 7.4 7.4 图的生成树图的生成树图的生成树图的生成树 7.5 7.5 拓扑排序拓扑排序拓扑排序拓扑排序 7.6 7.6 关键路径关键路径关键路径关键路径 7.7 7.7 最短路径最短路径最短路径最短路径第七章第七章 图图 7.1 图的定义和基本术语第七章 图44什么是生成树？什么是生成树？什么是生成树？什么是生成树？n n 一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树n n 一个有一个有一个有一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边条边条边条边定义：定义：定义：定义：所有顶点均由边连接在一起，但不存在回路的子图叫所有顶点均由边连接在一起，但不存在回路的子图叫所有顶点均由边连接在一起，但不存在回路的子图叫所有顶点均由边连接在一起，但不存在回路的子图叫V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8n n 有两种特殊的生成树：深度优先生成树有两种特殊的生成树：深度优先生成树有两种特殊的生成树：深度优先生成树有两种特殊的生成树：深度优先生成树&广度优先生成树广度优先生成树广度优先生成树广度优先生成树n n 一个连通图的一个连通图的一个连通图的一个连通图的生成树生成树生成树生成树其实就是该连通图的其实就是该连通图的其实就是该连通图的其实就是该连通图的极小连通分量极小连通分量极小连通分量极小连通分量什么是生成树？一个图可以有许多棵不同的生成树 一个有n45V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8例例例例深度遍历：深度遍历：深度遍历：深度遍历：V1V1V2V2V4V4V8V8V5V5V3V3V6V6V7V7V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8深度优先生成树深度优先生成树深度优先生成树深度优先生成树V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8广度优先生成树广度优先生成树广度优先生成树广度优先生成树V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V V7 7V V1 1V V2 2V V4 4V V5 5V V3 3V V6 6V V8 8广度遍历：广度遍历：广度遍历：广度遍历：V1V1V2V2V3V3V4V4V5V5V6V6V7V7V8V8V1V2V4V5V3V7V6V8例深度遍历：V1V2V446非连通图非连通图非连通图非连通图A AB BL LMMC CF FD DE EGGHHKKI IJ JA AB BL LMMC CF FJ JD DE EGGHHKKI I深度优先生成森林深度优先生成森林深度优先生成森林深度优先生成森林生成森林生成森林生成森林生成森林：非连通图每个连通分量非连通图每个连通分量非连通图每个连通分量非连通图每个连通分量的生成树一起组成非连通图的的生成树一起组成非连通图的的生成树一起组成非连通图的的生成树一起组成非连通图的 需要从多个顶点出发，需要从多个顶点出发，需要从多个顶点出发，需要从多个顶点出发，经过多次搜索经过多次搜索经过多次搜索经过多次搜索非连通图ABLMCFDEGHKIJABLMCFJDEGHKI47对于连通网络，其生成树的各边也是带权值的，其各边的权对于连通网络，其生成树的各边也是带权值的，其各边的权对于连通网络，其生成树的各边也是带权值的，其各边的权对于连通网络，其生成树的各边也是带权值的，其各边的权值之和称作生成树的权，权值最小的生成树称为值之和称作生成树的权，权值最小的生成树称为值之和称作生成树的权，权值最小的生成树称为值之和称作生成树的权，权值最小的生成树称为最小生成树最小生成树最小生成树最小生成树1 14 45 52 23 37 75 53 31 18 86 64 42 21 14 45 52 23 37 75 53 31 18 86 64 42 2对于连通网络，其生成树的各边也是带权值的，其各边的权值之和称48n n问题分析问题分析问题分析问题分析1 16 65 54 43 32 27 7131317179 9181812127 75 524241010 假设要在假设要在假设要在假设要在n n n n个城市之间建立通讯联络网，则连通个城市之间建立通讯联络网，则连通个城市之间建立通讯联络网，则连通个城市之间建立通讯联络网，则连通n n n n个城个城个城个城市只需要修建市只需要修建市只需要修建市只需要修建n-1n-1n-1n-1条线路条线路条线路条线路该问题等价于：在该问题等价于：在该问题等价于：在该问题等价于：在e e e e条带权的边中选取条带权的边中选取条带权的边中选取条带权的边中选取n-1n-1n-1n-1条（不构成回路），条（不构成回路），条（不构成回路），条（不构成回路），使使使使“权值之和权值之和权值之和权值之和”为最小。即：构造网的一棵最为最小。即：构造网的一棵最为最小。即：构造网的一棵最为最小。即：构造网的一棵最小生成树小生成树小生成树小生成树如何在最节省经费的前提下建立这个通讯网如何在最节省经费的前提下建立这个通讯网如何在最节省经费的前提下建立这个通讯网如何在最节省经费的前提下建立这个通讯网？n n问题提出问题提出问题提出问题提出问题分析1654327131791812752410 49n n构造最小生成树方法构造最小生成树方法构造最小生成树方法构造最小生成树方法方法一：普里姆方法一：普里姆方法一：普里姆方法一：普里姆(Prim)(Prim)算法算法算法算法 MSTMSTMSTMST性质性质性质性质 假设假设假设假设N=(V,E)N=(V,E)N=(V,E)N=(V,E)是一个连通网，是一个连通网，是一个连通网，是一个连通网，U U U U是顶点集是顶点集是顶点集是顶点集V V V V中的非空子集，中的非空子集，中的非空子集，中的非空子集，若若若若(u,v)(u,v)(u,v)(u,v)是所有一端在是所有一端在是所有一端在是所有一端在U U U U中而另一端在中而另一端在中而另一端在中而另一端在V-UV-UV-UV-U中的所有边中具有最中的所有边中具有最中的所有边中具有最中的所有边中具有最小权值的边，则必存在一棵最小生成树包含边小权值的边，则必存在一棵最小生成树包含边小权值的边，则必存在一棵最小生成树包含边小权值的边，则必存在一棵最小生成树包含边(u,v)(u,v)(u,v)(u,v)。构造最小生成树方法方法一：普里姆(Prim)算法 MST50若图中所有顶点均加入中，则在若图中所有顶点均加入中，则在若图中所有顶点均加入中，则在若图中所有顶点均加入中，则在3 3 3 3操作中记录的边和相关的操作中记录的边和相关的操作中记录的边和相关的操作中记录的边和相关的顶点构成该网络的最小生成树顶点构成该网络的最小生成树顶点构成该网络的最小生成树顶点构成该网络的最小生成树以下的表述中，以下的表述中，以下的表述中，以下的表述中，u u u u 表示表示表示表示 U U U U 中的顶点中的顶点中的顶点中的顶点,v,v,v,v 表示表示表示表示 V-U V-U V-U V-U 中的顶点中的顶点中的顶点中的顶点 1 1 1 1 选任一个顶点加入选任一个顶点加入选任一个顶点加入选任一个顶点加入U U U U2 2 2 2 标出一端在标出一端在标出一端在标出一端在U U U U中，而另一端在中，而另一端在中，而另一端在中，而另一端在V-UV-UV-UV-U中的边和其权值，如果有中的边和其权值，如果有中的边和其权值，如果有中的边和其权值，如果有多条边同时从多条边同时从多条边同时从多条边同时从U U U U中的不同的顶点出发到达中的不同的顶点出发到达中的不同的顶点出发到达中的不同的顶点出发到达v v v v，则只选其中权值，则只选其中权值，则只选其中权值，则只选其中权值小的那条小的那条小的那条小的那条 3 3 3 3 在在在在2 2 2 2中标出的所有中标出的所有中标出的所有中标出的所有(u,v)(u,v)(u,v)(u,v)中，选出权值最小的一条边，记录中，选出权值最小的一条边，记录中，选出权值最小的一条边，记录中，选出权值最小的一条边，记录这条边，并将顶点这条边，并将顶点这条边，并将顶点这条边，并将顶点v v v v加入加入加入加入U U U U中中中中4 4 4 4 若若若若UV,UV,UV,UV,根据新加入根据新加入根据新加入根据新加入U U U U中的顶点，调整连接中的顶点，调整连接中的顶点，调整连接中的顶点，调整连接U U U U和和和和V V V V中的边（中的边（中的边（中的边（u u u u，v v v v），返回），返回），返回），返回3 3 3 3若图中所有顶点均加入中，则在3操作中记录的边和相关的顶点构成51例例例例1 16 65 54 43 32 26 65 51 13 35 56 66 64 42 25 51 13 31 11 16 63 31 14 41 16 64 43 31 14 42 21 11 16 64 43 32 21 14 42 25 51 16 65 54 43 32 21 14 42 25 53 3*Prim 算法算法*例1654326513566425131163141643152n n方法二：