超强数据结构教学课件-第七章(图).pptx

1例例245136G1l图图G1中：中：V(G1)=1,2,3,4,5,6lE(G1)=,例例157324G26l图图G2中：中：V(G2)=1,2,3,4,5,6,7l无向图无向图 若图中的边是顶点的无序对，则称此图为若图中的边是顶点的无序对，则称此图为无向图无向图。通。通常用园括号表示常用园括号表示无向边无向边。（v,w）或（或（w,v)，并且（并且（v,w)=(w,v)7.1 图的定义和术语图的定义和术语lE(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)2l3、有向完全图、无向完全图、有向完全图、无向完全图l4、相邻顶点、相关联弧或边、相邻顶点、相关联弧或边l无向完全图无向完全图：n个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2，具有，具有n(n-1)/2条边的无向图称为无向完全图。条边的无向图称为无向完全图。213有向完全图有向完全图213无向完全图无向完全图7.1 图的定义和术语图的定义和术语l若若 E或或(V1,V2)E，则，则V1，V2是是相邻顶点相邻顶点，弧，弧或边或边(V1,V2)是与顶点是与顶点V1和和V2相关联弧或边相关联弧或边。l有向完有向完全全图图：具有：具有n(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。3l5、度、度 例例1245136G1l顶点顶点2入度：入度：1 出度：出度：3l顶点顶点4入度：入度：1 出度：出度：0例例2157324G26l顶点顶点5的度：的度：3l顶点顶点2的度：的度：47.1 图的定义和术语图的定义和术语l一个顶点一个顶点V的度是与该顶点相关联的边的数目，记为的度是与该顶点相关联的边的数目，记为TD（V）。）。l对于有向图，则把以顶点对于有向图，则把以顶点V为弧尾的数目称为点为弧尾的数目称为点V的出度，的出度，记为记为OD（V），把以顶点），把以顶点V为头的弧的数目称为顶点为头的弧的数目称为顶点V的入的入度，记为度，记为ID（V）。）。顶点顶点V的度为：的度为：lTD（V）=ID（V）+OD（V）4l6、子图、子图l设有两个图设有两个图 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。7.1 图的定义和术语图的定义和术语5l7、路径、路径l若一条路径上除了若一条路径上除了vi 和和vj 可以相同外，可以相同外，其余顶点均不相同，则其余顶点均不相同，则称此路径为一条称此路径为一条简单路径简单路径。7.1 图的定义和术语图的定义和术语l在无向图在无向图 G(V,E)中中,若存在一个顶点序列若存在一个顶点序列 vp1,vp2,vpm，使得使得(vi,vp1)、(vp1,vp2)、.、(vpm,vj)均属于均属于E，则称顶点，则称顶点vi到到vj存在一存在一 条路径。条路径。路径长度定义为路径上边或弧的数目。路径长度定义为路径上边或弧的数目。l起点和终点相同的路径称为起点和终点相同的路径称为简单回路或简单环简单回路或简单环。6例例2157324G26例例1245136G1l路径：路径：1，2，3，5，6，3l路径：路径：1，2，5，7，6，5，2，37.1 图的定义和术语图的定义和术语l路径长度：路径长度：5l简单路径：简单路径：1，2，3，5l回路：回路：1，2，3，5，6，3，1l简单回路：简单回路：3，5，6，3l路径长度：路径长度：7l简单路径：简单路径：1，2，5，7，6l回路：回路：1，2，5，7，6，5，2，1l简单回路：简单回路：1，2，3，17l8、图的连通、图的连通 在无向图在无向图G中，若两个顶点中，若两个顶点vi和和vj之间有路径存在，之间有路径存在，则称则称vi 和和vj 是连通的。是连通的。若若G中任意两个顶点都是连通的，则称中任意两个顶点都是连通的，则称G为连通图。为连通图。连通图连通图例例245136强连通图强连通图356例例例例245136非连通图，连通分量非连通图，连通分量l9、强连通图与强连通分量、强连通图与强连通分量 在有向图中在有向图中,若对于每一对顶点若对于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是则称此图是强连通图强连通图。非强连通图的极大强连通子图叫做强连通分量。非强连通图的极大强连通子图叫做强连通分量。7.1 图的定义和术语图的定义和术语l非连通图的极大连通子图叫做非连通图的极大连通子图叫做连通分量连通分量。8l10、带权图或网、带权图或网1235687410796671231516ABDCE60304535804075l若给图中每一条边附加一个实数作为权，则该图称若给图中每一条边附加一个实数作为权，则该图称为为带权图或网。带权图或网。7.1 图的定义和术语图的定义和术语l这些权可以表示从一个顶点到另一个顶点的距离或这些权可以表示从一个顶点到另一个顶点的距离或花费的代价。花费的代价。9l一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示7.2 图的存储结构图的存储结构l二、图的邻接表存储表示二、图的邻接表存储表示l三、有向图的十字链表存储表示三、有向图的十字链表存储表示l四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示10l用两个数组分别存储数据元素（顶点）的信息和数据元素用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。之间的关系（边或弧）的信息。一、数组表示法（邻接矩阵一、数组表示法（邻接矩阵）l在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。表，还有一个表示各个顶点之间关系的邻接矩阵。l设图设图 A=(V,E)是一个有是一个有 n 个顶点的图，则图的邻接矩阵个顶点的图，则图的邻接矩阵定义：定义：l无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。对称的。11例例G12413例例15324G2一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）12l借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。连，并容易求得各个顶点的度。l对于无向量，顶点对于无向量，顶点Vi的度是邻接矩阵中第的度是邻接矩阵中第i行（或第行（或第i列）列）的元素的元素之和，即之和，即 l对于有向图，对于有向图，第第i行的元素之和为顶点行的元素之和为顶点Vi的出度的出度OG（Vi），），第第j列的元素之和为顶点列的元素之和为顶点Vj的入度的入度ID(Vj)。一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）例例G1241313l网的邻接矩阵可定义为：网的邻接矩阵可定义为：例例1452375318642一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）14二、图的邻接表存储表示二、图的邻接表存储表示q邻接表邻接表是图的一种链式存储结构。是图的一种链式存储结构。在邻接表中，对在邻接表中，对图中每个顶点建立一个单链表，图中每个顶点建立一个单链表，第第i个单链表中的个单链表中的结点表示依附于顶点结点表示依附于顶点Vi的边（对有向图中指以顶点的边（对有向图中指以顶点Vi为尾的弧）。为尾的弧）。adjvex nextarc infoq每个结点有三个域组成：每个结点有三个域组成：q邻接结点域邻接结点域(adjvex)：指示与顶点：指示与顶点Vi邻接的点在图邻接的点在图中的位置。中的位置。q链域链域(nextarc)：指示下一条边或弧的结点。：指示下一条边或弧的结点。q数据域数据域(info)：存储和边相关的信息，如权值等：存储和边相关的信息，如权值等15l每个链表上附设一个表头结点。在表头结点中，除了设有链域每个链表上附设一个表头结点。在表头结点中，除了设有链域(firstarc)指向链表中第一个结点之外，还设有存储顶点指向链表中第一个结点之外，还设有存储顶点Vi的名的名或其它有关信息的数据域或其它有关信息的数据域(data)。头结点头结点 data firstarc二、图的邻接表存储表示二、图的邻接表存储表示例例V1V5V3V2V4G20123V1V3V4V2vexdatafirstarc 1 4 23adjvexnext4V5 2 20 4 1 0 2116l若无向图中有若无向图中有n个顶点、个顶点、e条边，则它的邻接表需条边，则它的邻接表需n个头结点个头结点和和2e个表结点。个表结点。显然，在边稀疏显然，在边稀疏(en(n-1)/2)的情况下，用的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。较多时更是如此。二、图的邻接表存储表示二、图的邻接表存储表示例例V1V5V3V2V4G20123V1V3V4V2vexdatafirstarc 1 4 23adjvexnext4V5 2 20 4 1 0 2117例例G1V2V4V1V30123V1V3V4V2vexdatafirstarc 2 1 3 0adjvexnext二、图的邻接表存储表示二、图的邻接表存储表示l在无向图的邻接表中，顶点在无向图的邻接表中，顶点vi的度恰为第的度恰为第i个链表中的结点数；个链表中的结点数；l而在有向图中，第而在有向图中，第i个链表中的结点个数只是顶点个链表中的结点个数只是顶点vi的出度，为的出度，为求入度，必须遍历整个邻接表。求入度，必须遍历整个邻接表。l在所有链表中其邻接点域的值为在所有链表中其邻接点域的值为i的结点的个数是顶点的结点的个数是顶点vi的入度。的入度。18ABECD二、图的邻接表存储表示二、图的邻接表存储表示l有时，为了便于确定顶点的入度或以顶点有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接以建立一个链接以vi为头的弧的链表。为头的弧的链表。l在邻接表上容易找到任一顶点的第在邻接表上容易找到任一顶点的第1个邻接点和下一个邻接点，个邻接点和下一个邻接点，3 30 4 2 0 EDCBA43210l但是要判定任意两个顶点（但是要判定任意两个顶点（vi和和vj）之间是否有边或狐相连，则）之间是否有边或狐相连，则需搜索第需搜索第i个或第个或第j个链表，因此，不及邻接矩阵方便。个链表，因此，不及邻接矩阵方便。19三、有向图的十字链表表示法三、有向图的十字链表表示法l十字链表十字链表是有向图的另一种链式存储结构。可以看成是将是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。有向图的邻接表和逆邻接表结合起来得到的一种链表。l在十字链表中，对应于有向图中每一条弧有一个结点，对在十字链表中，对应于有向图中每一条弧有一个结点，对应于每一个顶点也有一个结点。这些结点的结构如下：应于每一个顶点也有一个结点。这些结点的结构如下：弧的结点结构弧的结点结构弧尾顶点位置弧尾顶点位置 弧头顶点位置弧头顶点位置 弧的相关信弧的相关信息息指向下一个指向下一个有相同弧尾有相同弧尾的结点的结点指向下一个有指向下一个有相同弧头的结相同弧头的结点点tailvexheadvexhlink tlinkinfo20顶点信息数据 指向该顶点的指向该顶点的第一条入弧第一条入弧指向该顶点的指向该顶点的第一条出弧第一条出弧datafirstinfirstout顶点结点三、有向图的十字链表表示法三、有向图的十字链表表示法l在十字链表中，既容易找到以在十字链表中，既容易找到以vi为尾的狐，也容易找到以为尾的狐，也容易找到以vi尾尾头的狐，因而容易求得顶点的出度和入度。头的狐，因而容易求得顶点的出度和入度。l建立十字链表的时间复杂度和建立邻接表是相同的。在某些建立十字链表的时间复杂度和建立邻接表是相同的。在某些有向图中，十字链表是很有用的工具。有向图中，十字链表是很有用的工具。21例例V2V4V1V3V1V2 V3V40123 0 2 0 1 2 3 2 0 3 2 3 1 3 0三、有向图的十字链表表示法三、有向图的十字链表表示法22四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示l邻接多重表是无向图的另一种链式存储结构。邻接多重表的结邻接多重表是无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中，每一条边用一个结点表构和十字链表类似。在邻接多重表中，每一条边用一个结点表示，它由如下所示的六个域组成：示，它由如下所示的六个域组成：mark ivex ilink jvex jlink infolmark为标志域，可以用以标记该条边是否被搜索过。为标志域，可以用以标记该条边是否被搜索过。livex和和jvex为该边依附的两个顶点在图中的位置。为该边依附的两个顶点在图中的位置。lilink指向下一条依附于顶点指向下一条依附于顶点ivex的边。的边。ljlink指向下一条依附于顶点指向下一条依附于顶点jvex的边。的边。linfo为指向和边相关的各种信息的指针域。为指向和边相关的各种信息的指针域。23例例v1v5v3v2v40123v1v3v4v24v5 0 1 0 3 2 3 2 1 2 4 4 1l每一个顶点也用一个结点表示，它由如下所示的两个域组成：每一个顶点也用一个结点表示，它由如下所示的两个域组成：data firstedgeldata域存储和该顶点相关的信息域存储和该顶点相关的信息四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示lfirstedge域指示第一条依附于该顶点的边域指示第一条依附于该顶点的边247.3 图的遍历图的遍历l从图中某一顶点出发访遍图中其余顶点，且使每一个顶点从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做仅被访问一次。这一过程就叫做图的遍历图的遍历。l通常有两条遍历图的路径：通常有两条遍历图的路径：l深度优先搜索遍历深度优先搜索遍历l广度优先搜索遍历广度优先搜索遍历251、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法l深度优先搜索遍历深度优先搜索遍历类似于树的先根遍历，是树的先根类似于树的先根遍历，是树的先根遍历的推广。遍历的推广。l深度优先可以从图中某个顶点深度优先可以从图中某个顶点V出发，访问此顶点，出发，访问此顶点，l若此时图中尚有顶点未被访问，则另选图中一个未曾若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。顶点都被访问为止。l然后依次从然后依次从V的未被访问的邻接点出发，深度优先遍的未被访问的邻接点出发，深度优先遍历图，直至图中所有和历图，直至图中所有和V有路径有路径的顶点都被访问到；的顶点都被访问到；26l（1）假定从图中的某一顶点）假定从图中的某一顶点V出发进行遍历，首先访问出发进行遍历，首先访问顶点顶点V，再访问一个与，再访问一个与V相邻的顶点相邻的顶点W，接着访问一个与，接着访问一个与W相邻且未被访问的顶点。依次类推，直至某个被访问相邻且未被访问的顶点。依次类推，直至某个被访问的顶点的所有相邻顶点均被访问过为止。的顶点的所有相邻顶点均被访问过为止。l（2）然后退回到尚有相邻顶点未被访问的顶点）然后退回到尚有相邻顶点未被访问的顶点R，再从，再从顶点顶点R的一个未被访问的相邻顶点出发，重复上述过程，的一个未被访问的相邻顶点出发，重复上述过程，直到图中所有和直到图中所有和V有路径相通的顶点都被访问过。有路径相通的顶点都被访问过。l（3）若此时）若此时图中尚有顶点未被访问，则另选图中一个未图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。点都被访问为止。1、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法27深度遍历：深度遍历：V1V2 V4 V8 V5 V3 V6 V71、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 428V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：深度遍历：V1V2 V4 V8 V5 V3 V6 V71、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法292、广度优先搜索遍历、广度优先搜索遍历(BFS)l方法：方法：广度优先遍历类似于树的按层次遍历的过程广度优先遍历类似于树的按层次遍历的过程。假设。假设从图中某顶点从图中某顶点V出发，访问此顶点出发，访问此顶点V后，依次访问后，依次访问V的各个的各个未曾访问过的邻接点；未曾访问过的邻接点；l若此时图中尚有顶点未被访问，则另选图中一个未被访若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。被访问为止。l然后分别从这些邻接点出发依次访问它们的邻接点，并使然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访问的顶点的邻后被访问的顶点的邻接点接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问，直至图中所有已被访问的顶点的邻接点都被访问到；被访问到；30V1V2V4V5V3V7V6V8例例l广度遍历广度遍历V1V2V4V5V3V7V6V8例例V1V2 V1V3 V4 V5 V6 V7 V8l广度遍历广度遍历V2 V3 V4 V6 V7 V8 V52、广度优先搜索遍历、广度优先搜索遍历(BFS)317.4 最小生成树最小生成树l假设要在假设要在n个城市间建立通信联络网，则连通个城市间建立通信联络网，则连通n个城市只需个城市只需n-1条条线路。这时，自然会考虑这样一个问题，如何在最节省经费的线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通讯网？前提下建立这个通讯网？l在每个城市之间都可以设置一条线路，相应地都要付出一定的在每个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。经济代价。n个城市之间，最多可能设置个城市之间，最多可能设置n(n-1)/2条线路，那么，条线路，那么，如何在这些可能的线路中选择如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？条，以使总的耗费最少呢？l可以用连通网来表示可以用连通网来表示n个城市以及个城市以及n个城市间可能设置的通讯线个城市间可能设置的通讯线路，其中路，其中网的网的顶点表示城市，边表示两个城市之间的线路，赋顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价于边的权值表示相应的代价。对于。对于n个顶点的连通网可以建立许个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通讯网。多不同的生成树，每一棵生成树都可以是一个通讯网。32l现在，我们要选择这样一棵生成树，也就是使总的耗费最少，现在，我们要选择这样一棵生成树，也就是使总的耗费最少，这个问题就是构造连通网的这个问题就是构造连通网的最小代价生成树最小代价生成树（简称为最小生（简称为最小生成树）的问题。成树）的问题。l一棵生成树的代价就是树上各边的代价之和。一棵生成树的代价就是树上各边的代价之和。l构造最小生成树可以有多种方法。其中多数算法利用了最小生构造最小生成树可以有多种方法。其中多数算法利用了最小生成树的下列一种简称为成树的下列一种简称为MST的性质：的性质：假设假设N=（V，E）是一个）是一个连通网，连通网，U是顶点集是顶点集V的一个非空子集。若（的一个非空子集。若（u,v）是一条具有）是一条具有最小权值（代价）的边，其中最小权值（代价）的边，其中u U，v V-U，则必存在一棵包，则必存在一棵包含边（含边（u,v）的最小生成树。）的最小生成树。l普里姆普里姆算法算法和克鲁斯卡尔和克鲁斯卡尔算法算法是两个利用是两个利用MST性质构造最小生性质构造最小生成树的算法。成树的算法。7.4 最小生成树最小生成树331、普里姆、普里姆算法算法l假设假设N=（V,E)是连通图是连通图,TE是是N上最小生成树中边的集合上最小生成树中边的集合.算算法从法从U=u0(u0 V),TE=开始，重复执行下述操作开始，重复执行下述操作:l在所有在所有u U,v VU的边的边(u,v)E中中,找一条代价最小的边找一条代价最小的边（u0,v0）并入集合）并入集合TE，同时，同时v0并入并入U中，中，l如此不断重复如此不断重复,直到直到UV为止。此时为止。此时TE必有必有n-1条边条边,则则T（V,TE）为）为N的最小生成树。的最小生成树。34l如此进行下去，每次往生成树如此进行下去，每次往生成树里加一个顶点和一条权值最小里加一个顶点和一条权值最小的边的边，直到把所有的顶点都包括进生成树。，直到把所有的顶点都包括进生成树。1、普里姆、普里姆算法算法l从任意一个顶点开始从任意一个顶点开始，首先把这个顶点包括在生成树里，首先把这个顶点包括在生成树里，l然后在那些其一个端点已在生成树里另一个端点还未在生成然后在那些其一个端点已在生成树里另一个端点还未在生成数里的边中，数里的边中，找权值最小的一条边找权值最小的一条边，l当有两条具有同样的最小权值的边可供选择时，选哪一条都当有两条具有同样的最小权值的边可供选择时，选哪一条都行。行。l并把这条并把这条边和其不在生成树里的那个端点包括进生成树里边和其不在生成树里的那个端点包括进生成树里。35例例16543265135664251311631416431421164321425165432142531、普里姆、普里姆算法算法36l为了实现这个算法需附设一个辅助数组为了实现这个算法需附设一个辅助数组closedge,以记录从以记录从U到到V-U具有最小代价的边具有最小代价的边.对每个顶点对每个顶点vi V-U，在辅助数组中存在一，在辅助数组中存在一个相应分量个相应分量closedgei-1，它包含两个域，其中，它包含两个域，其中lowcost存储该存储该边上的权。显然，边上的权。显然，Closedgei-1.lowcost=Mincost(u,vi)|u U,vex域存储该边依附的在域存储该边依附的在U中的顶点。中的顶点。l初始状态时初始状态时,由于由于U=v1,则到则到V-U中各顶点的最小边中各顶点的最小边,即为从依附即为从依附于顶点于顶点1的各条边中的各条边中,找到一条代价最小的边（找到一条代价最小的边（u0,v0）=（1,3）为生成树上的第一条边为生成树上的第一条边,同时将同时将v0（=v3）并入集合）并入集合U.l然后修改辅助数组中的值。首先将然后修改辅助数组中的值。首先将closedge 2.Lowcost 改为改为“0”,以示顶点以示顶点v3以并入以并入U。然后。然后,由于边（由于边（v3，v2）上的权值小）上的权值小于于closedge1.lowcost,则需修改则需修改closedge1.lowcost为边为边（v3，v2）及其权值。同理修改）及其权值。同理修改closedge4和和closedge5。依次类推，直至依次类推，直至U=V。1、普里姆、普里姆算法算法37closedge i12345UV-UkAdjvexlowcostv16v11v15v1v2,v3,v4,v5,v62l构造最小生成树过程中辅助数组中各分量的值构造最小生成树过程中辅助数组中各分量的值Adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v65Adjvexlowcostv350v62v360v1,v3,v6v2,v4,v53Adjvexlowcostv3500v360v1,v3,v6,v4v2,v51Adjvexlowcost000v220v1,v3,v6,v4,v2v54Adjvexlowcost00000v1,v3,v6,v4,v2,v5165432651356642538l设含设含n个顶点的网中，边的权值全是正数。图用邻接矩阵表个顶点的网中，边的权值全是正数。图用邻接矩阵表示，若（示，若（Vi，Vj）是边，则）是边，则Ai，j的值等于此边上的权；若的值等于此边上的权；若（Vi，Vj）不是边，则）不是边，则Ai，j的值是一个比任何边的权值都的值是一个比任何边的权值都大的正数大的正数Max，矩阵的对角线元素全为，矩阵的对角线元素全为0。l构造最小生成树的过程构造最小生成树的过程：若顶点：若顶点Vi已包括进生成树里，就把已包括进生成树里，就把邻接矩阵对角线元素邻接矩阵对角线元素Ai，j 置为置为1；无向图的邻接矩阵是对；无向图的邻接矩阵是对称的，边（称的，边（Vi，Vj）对应两个矩阵元素）对应两个矩阵元素Ai，j和和Aj，i，若，若边（边（Vi，Vj）已包括进生成树，就把矩阵元素）已包括进生成树，就把矩阵元素Ai，j和和Aj，i两者中位于矩阵下三角中的一个置为负值。两者中位于矩阵下三角中的一个置为负值。1、普里姆、普里姆算法算法l算法结束时，邻接矩阵下三角部分为负的元素表示最小生成算法结束时，邻接矩阵下三角部分为负的元素表示最小生成树的边。在算法中用数组存放邻接矩阵树的边。在算法中用数组存放邻接矩阵A，数组元素的下标，数组元素的下标等于相关联的顶点序号减等于相关联的顶点序号减1。3910 1 2 3 4 501 2 3 4 51-21-41-1例例16543265135664251-51-316543265135664251654321425311、普里姆、普里姆算法算法40l普里姆算法普里姆算法的时间复杂度为的时间复杂度为O（n2），与网中的边数无），与网中的边数无关，因此关，因此适用于求边稠密的网的最小生成树适用于求边稠密的网的最小生成树。2、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算法算法l而而克鲁斯尔算法克鲁斯尔算法恰恰相反，它的时间复杂度为恰恰相反，它的时间复杂度为O(eloge)（e为网中边的数目），因此，它相当于普里姆算法而为网中边的数目），因此，它相当于普里姆算法而言，言，适合于求边稀疏的网的最小生成树适合于求边稀疏的网的最小生成树。41例例165432651356642516543212345l克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法:假设连通网假设连通网N=（V，E），则令），则令最小生成树的初始状态为只有最小生成树的初始状态为只有n个顶点而无边的非连通图个顶点而无边的非连通图T=（V，），图中每个顶点自成一个连同分量。在），图中每个顶点自成一个连同分量。在E中选择代中选择代价最小的边，若该边依附的顶点落在价最小的边，若该边依附的顶点落在T中不同的连通分量上，中不同的连通分量上，则将此边加入到则将此边加入到T中，否则舍去此边而选择下一条代价最小的中，否则舍去此边而选择下一条代价最小的边。依次类推，直至边。依次类推，直至T中所有顶点都在同一连通量上为止。中所有顶点都在同一连通量上为止。2、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算法算法42l（1）用顶点数组和边数组存放顶点和边信息）用顶点数组和边数组存放顶点和边信息l顶点结点：顶点结点：ltypedef structl int data;/顶点信息顶点信息l int jihe;VEX;l边结点：边结点：ltypedef struct l int vexh,vext;/边依附的两顶点边依附的两顶点l int weight;/边的权值边的权值l int flag;/标志域标志域 EDGE;l（2）初始时，令每个顶点的）初始时，令每个顶点的jihe互不相同；每个边的互不相同；每个边的flag为为0l（3）选出权值最小且）选出权值最小且flag为为0的边的边l（4）若该边依附的两个顶点的）若该边依附的两个顶点的jihe 值不同，即非连通，则令该值不同，即非连通，则令该边的边的flag=1,选中该边；选中该边；l（5）重复上述步骤，直到选出）重复上述步骤，直到选出n-1条边为止条边为止 l再令该边依附的两顶点的再令该边依附的两顶点的jihe以及两集合中所有顶点的以及两集合中所有顶点的jihe相同。相同。l若该边依附的两个顶点的若该边依附的两个顶点的jihe 值相同，即连通，则令该边的值相同，即连通，则令该边的flag=2,即舍去该边即舍去该边43例例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222165432123452、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算法算法44l例如，一个软件专业的学生必须学习一系列基本课程，其例如，一个软件专业的学生必须学习一系列基本课程，其中有些课是基础课，它独立于其它课程，如中有些课是基础课，它独立于其它课程，如高等数学高等数学；而另一些课程必须在学完作为它的基础的先修课程才能开而另一些课程必须在学完作为它的基础的先修课程才能开始。如在始。如在程序设计基础程序设计基础和和离散数学离散数学学完之前就不学完之前就不能开始学习能开始学习数据结构数据结构。7.5 拓扑排序拓扑排序l这些先决条件定义了课程之间的优先关系。这个关系可以这些先决条件定义了课程之间的优先关系。这个关系可以用有向图更加清楚地表示，图中顶点表示课程，有向弧表用有向图更加清楚地表示，图中顶点表示课程，有向弧表示先决条件。若课程示先决条件。若课程i是课程是课程j的先决条件，则图中有弧的先决条件，则图中有弧。l学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业完成学业拓扑排序拓扑排序45C1C2C3C4C5C6C7C8C9C10C11C127.5 拓扑排序拓扑排序课程编号课程编号课程名称课程名称先决条件先决条件C1程序设计程序设计无无C2离散数学离散数学C1C3数据结构数据结构C1，C2C4汇编语言汇编语言C1C5语言的设计和分析语言的设计和分析C3，C4C6计算机原理计算机原理C11C7编译原理编译原理C5，C3C8操作系统操作系统C3，C6C9高等数学高等数学无无C10线性代数线性代数C9C11普通物理普通物理C9C12数值分析数值分析C9，C10，C146lAOV网网这种用顶点表示活动，用弧表示活动间优先关这种用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称简称AOV网网。l在网中，若从顶点在网中，若从顶点i到顶点到顶点j有一条有向路径，则有一条有向路径，则i是是j的前驱，的前驱，j是是i的后继。的后继。若若是图中有向边，则是图中有向边，则vi是是vj的直接前驱；的直接前驱；vj是是vi的直接后继。的直接后继。lAOV网中不允许有回路，这意味着某项活动以自己为先决网中不允许有回路，这意味着某项活动以自己为先决条件。条件。l对于给定的对于给定的AOV网应首先判定网中是否存在环。检测的办网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该点都在它的拓扑有序序列中，则该AOV网必定不存在环。网必定不存在环。7.5 拓扑排序拓扑排序47l在有向图中选一个没有前驱的顶点且输出之。在有向图中选一个没有前驱的顶点且输出之。1、如何、如何拓扑排序？拓扑排序？l拓扑排序拓扑排序把把AOV网络中各顶点按照它们相互之间的网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。优先关系排列成一个线性序列的过程叫拓扑排序。如何如何拓扑排序？拓扑排序？l从图中删除该顶点和所有以它为尾的弧。从图中删除该顶点和所有以它为尾的弧。l重复上述两步，直至全部顶点均已输出，或者当前图中重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。不存在无前驱的顶点为止。48C1C2C3C4C5C6C7C8C9C10C11C12q拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8q或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的1、如何、如何拓扑排序？拓扑排序？49C1C2C3C4C5C6C7C8C9C10C11C121、如何、如何拓扑排序？拓扑排序？50C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2（2）1、如何、如何拓扑排序？拓扑排序？51C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4（4）1、如何、如何拓扑排序？拓扑排序？52C6C8C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9C6C8C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5（5）C6C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7（6）1、如何、如何拓扑排序？拓扑排序？53C6C8C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）1、如何、如何拓扑排序？拓扑排序？54l如何在计算机中实现？如何在计算机中实现？2、排序算法的实现、排序算法的实现l针对上述两步操作，我们可采用邻接表作有向图的存储结构，针对上述两步操作，我们可采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（且在头结点中增加一个存放顶点入度的数组（indegree）。入）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减的操作，则可换以弧头顶点的入度减1来实现。来实现。l为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。为零的顶点。l为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同时设置一个栈来存储所有入度为时设置一个栈来存储所有入度为0 的顶点。的顶点。l在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为0 的顶点都推入栈中，一旦排序过程中出现新的入度为的顶点都推入栈中，一旦排序过程中出现新的入度为0 的顶点，的顶点，也同样将其推入栈中。也同样将其推入栈中。55l邻接表结点：邻接表结点：ltypedef struct nodel int vex;/顶点域顶点域l struct node *next;/链