数据结构导论第五章课件

第五章第五章 图图5.1 5.1 图的基本概念图的基本概念 5.2 5.2 图的存储结构图的存储结构 5.3 5.3 图的遍历图的遍历 5.4 5.4 最小生成树最小生成树 5.5 5.5 拓扑排序拓扑排序1 15.1 5.1 图的基本概念图的基本概念 图图图图G G G G由两个集合构成，记作由两个集合构成，记作由两个集合构成，记作由两个集合构成，记作G=G=G=G=其中其中其中其中:V V V V（vertexvertexvertexvertex）是顶点的非空有限集合）是顶点的非空有限集合）是顶点的非空有限集合）是顶点的非空有限集合 E E E E（edgeedgeedgeedge）是边的有限集合）是边的有限集合）是边的有限集合）是边的有限集合v1v2v5v4v32 2如果每条边都没有方向，则为无向图如果每条边都没有方向，则为无向图 (vi,vj)(vi,vj)和和(vj,vi)(vj,vi)表示同一条边表示同一条边如果每条边都有方向，则称有向图如果每条边都有方向，则称有向图有向图中用箭头表示弧的方向，箭头从弧尾指向弧头有向图中用箭头表示弧的方向，箭头从弧尾指向弧头v1v2v5v4v3v2v1v4v33 3G1=V,EG1=V,EG1=V,EG1=V,EV=v1,v2,v3,v4,v5 V=v1,v2,v3,v4,v5 V=v1,v2,v3,v4,v5 V=v1,v2,v3,v4,v5 E=(v1,v2),(v2,v3),(v2,v4),(v3,v5),(v2,v5)E=(v1,v2),(v2,v3),(v2,v4),(v3,v5),(v2,v5)E=(v1,v2),(v2,v3),(v2,v4),(v3,v5),(v2,v5)E=(v1,v2),(v2,v3),(v2,v4),(v3,v5),(v2,v5)G2=V,EG2=V,EV=v1,v2,v3,v4,v5 V=v1,v2,v3,v4,v5，E=,E=,4 4n n完全图：完全图：无向完全图：无向完全图：无向完全图：无向完全图：任意两顶点间都有边的图。任意两顶点间都有边的图。任意两顶点间都有边的图。任意两顶点间都有边的图。n n在一个含有在一个含有在一个含有在一个含有n n n n个顶点的无向完全图中，有个顶点的无向完全图中，有个顶点的无向完全图中，有个顶点的无向完全图中，有n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2条边。条边。条边。条边。有向完全图有向完全图有向完全图有向完全图:任意两顶点之间都有方向互为相反的两任意两顶点之间都有方向互为相反的两任意两顶点之间都有方向互为相反的两任意两顶点之间都有方向互为相反的两条弧相连接的有向图。条弧相连接的有向图。条弧相连接的有向图。条弧相连接的有向图。n n在一个含有在一个含有在一个含有在一个含有n n n n个顶点的有向完全图中，有个顶点的有向完全图中，有个顶点的有向完全图中，有个顶点的有向完全图中，有n(n-1)n(n-1)n(n-1)n(n-1)条弧。条弧。条弧。条弧。5 5邻接点、相关边邻接点、相关边无向图中存在边无向图中存在边(vi,vj)(vi,vj)，则称，则称vivi和和vjvj互为邻接点互为邻接点 同时称同时称边边(vi,vj)(vi,vj)依附于顶点依附于顶点vi,vjvi,vj (vi,vj)(vi,vj)是与是与vivi和和vjvj相关联的边相关联的边在有向图中，在有向图中，若存在弧若存在弧，也称相邻接，也称相邻接，但要区分弧的头和尾但要区分弧的头和尾6 6n n顶点的度顶点的度顶点的度顶点的度在无向图中在无向图中在无向图中在无向图中,顶点顶点顶点顶点V V V V的度的度的度的度=与与与与V V V V相关联的边的数目，相关联的边的数目，相关联的边的数目，相关联的边的数目，记作记作记作记作D(V)D(V)D(V)D(V)在有向图中在有向图中在有向图中在有向图中,顶点顶点顶点顶点V V V V的度的度的度的度=V=V=V=V的出度的出度的出度的出度OD(V)+VOD(V)+VOD(V)+VOD(V)+V的入度的入度的入度的入度ID(V)ID(V)ID(V)ID(V)OD(V)=OD(V)=OD(V)=OD(V)=以以以以V V V V为起点有向边数为起点有向边数为起点有向边数为起点有向边数ID(V)=ID(V)=ID(V)=ID(V)=以以以以V V V V为终点有向边数为终点有向边数为终点有向边数为终点有向边数7 7n n路径路径路径路径G G G G中的顶点序列中的顶点序列中的顶点序列中的顶点序列v1,v2,vk,v1,v2,vk,v1,v2,vk,v1,v2,vk,若各边若各边若各边若各边(vi,vi+1)(vi,vi+1)(vi,vi+1)(vi,vi+1)E,E,E,E,则称该序列是从顶点则称该序列是从顶点则称该序列是从顶点则称该序列是从顶点v1v1v1v1到顶点到顶点到顶点到顶点vkvkvkvk的路径；的路径；的路径；的路径；8 8n n回路回路回路回路:若路径的起点和终点相同，则称回路。若路径的起点和终点相同，则称回路。若路径的起点和终点相同，则称回路。若路径的起点和终点相同，则称回路。n n简单路径简单路径简单路径简单路径在一条路径中在一条路径中在一条路径中在一条路径中,若除起点和终点外若除起点和终点外若除起点和终点外若除起点和终点外,所有顶点各不相所有顶点各不相所有顶点各不相所有顶点各不相同同同同,则该路径为简单路径；则该路径为简单路径；则该路径为简单路径；则该路径为简单路径；n n简单回路：简单回路：简单回路：简单回路：由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路；9 9n n子图子图子图子图设有两个图设有两个图设有两个图设有两个图G=G=G=G=（V V V V，E E E E）G1=G1=G1=G1=（V1V1V1V1，E1E1E1E1），），），），若若若若V1V1V1V1 V V V V，E1 E1 E1 E1 E E E E，E1E1E1E1关联的顶点都在关联的顶点都在关联的顶点都在关联的顶点都在V1V1V1V1中，则称中，则称中，则称中，则称 G1 G1 G1 G1是是是是G G G G的子图；的子图；的子图；的子图；G1=(V1，E1);V1=v1,v2,v3,v4,v5 E1=(v1,v2),(v2,v3),(v3,v5),(v2,v4),(v2,v5)G2=(V2，E2)V2=v2,v3,v5E2=(v2,v3),(v2,v5),(v3,v5)1010 n n连通图连通图连通图连通图 在无向图在无向图在无向图在无向图G=G=G=G=中，中，中，中，若对任何两个顶点若对任何两个顶点若对任何两个顶点若对任何两个顶点 v v v v、u u u u 都存在从都存在从都存在从都存在从v v v v 到到到到 u u u u 的路径，的路径，的路径，的路径，则称则称则称则称G G G G是连通图是连通图是连通图是连通图1111n n连通分量连通分量连通分量连通分量无向图无向图无向图无向图G G G G 的极大连通子图称为的极大连通子图称为的极大连通子图称为的极大连通子图称为G G G G的连通分量的连通分量的连通分量的连通分量1212生成树生成树包含无向图包含无向图G G 所有顶点的的极小连通子图所有顶点的的极小连通子图若若T T是是G G 的生成树当且仅当的生成树当且仅当T T 满足如下条件满足如下条件 T T是是G G 的连通子图的连通子图 T T包含包含G G 的所有顶点的所有顶点 T T中无回路中无回路13131.1.若连通图若连通图G G的顶点个数为的顶点个数为n n，则，则G G的生成树边数为的生成树边数为n-1n-1。2.2.如果如果G G的一个子图的一个子图GG的边数大于的边数大于n-1n-1，则，则GG中一定中一定有环。有环。3.3.相反，如果相反，如果GG的边数小于的边数小于n-1n-1，则，则GG一定不连通。一定不连通。结论结论1414边的权：边的权：边的权：边的权：在图的边或弧上表示数字，表示与该边相关的在图的边或弧上表示数字，表示与该边相关的在图的边或弧上表示数字，表示与该边相关的在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据信息就称该边的权（数据信息，这个数据信息就称该边的权（数据信息，这个数据信息就称该边的权（数据信息，这个数据信息就称该边的权（weightweightweightweight）。）。）。）。网（网（网（网（networknetworknetworknetwork）：边（或弧）上带权的图称为网。）：边（或弧）上带权的图称为网。）：边（或弧）上带权的图称为网。）：边（或弧）上带权的图称为网。V0V0 V4V4 V3V3 V1V1 V2V28246531515习题习题1.1.（1 1）设有无向图）设有无向图G=(V,E)G=(V,E)和和G=(V,E)G=(V,E)，若，若GG是是G G的生成树，则下面不正确的说法是（的生成树，则下面不正确的说法是（）A.A.GG为为G G的子图的子图 B.B.GG为为G G的连通分量的连通分量 C.GC.G为为G G的极小连通子图且的极小连通子图且V=V V=V D.GD.G是是G G的无环子图的无环子图答案：答案：B B16165.25.2图的存储表示图的存储表示邻接矩阵表示法邻接矩阵表示法邻接表表示法邻接表表示法17171.1.邻接矩阵表示邻接矩阵表示n n图图图图G G G G的邻接矩阵是满足如下条件：的邻接矩阵是满足如下条件：的邻接矩阵是满足如下条件：的邻接矩阵是满足如下条件：若若G G是网是网若若G G是图是图1818V1V2V3V4V1V2V3V4359619191 1，无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的2 2，存储无向图的邻接矩阵需要，存储无向图的邻接矩阵需要n(n+1)/2n(n+1)/2个单元，个单元，与边数无关，只与顶点数有关。与边数无关，只与顶点数有关。3 3，无向图，无向图vivi的度是第的度是第i i行行(列列)中中1 1的个数，的个数，边数是矩阵中边数是矩阵中1 1个数的一半个数的一半4 4，有向图第，有向图第i i行行1 1的个数是的个数是vivi的出度的出度 第第i i列列1 1的个数是的个数是vivi的入度的入度 2020习题习题习题习题1 1 1 1）求顶点）求顶点）求顶点）求顶点v v v v的度：的度：的度：的度：2 2 2 2）判断两顶点是否邻接：）判断两顶点是否邻接：）判断两顶点是否邻接：）判断两顶点是否邻接：3 3 3 3）检测图中的总边数：）检测图中的总边数：）检测图中的总边数：）检测图中的总边数：2121邻接矩阵的定义结构邻接矩阵的定义结构邻接矩阵的定义结构邻接矩阵的定义结构typedef struct graphtypedef struct graphtypedef struct graphtypedef struct graph vertex vexs vnum vertex vexs vnum vertex vexs vnum vertex vexs vnum；int arcs vnum vnum int arcs vnum vnum int arcs vnum vnum int arcs vnum vnum；int vexnum int vexnum int vexnum int vexnum，arcnumarcnumarcnumarcnum；/顶点信息顶点信息顶点信息顶点信息/边信息边信息边信息边信息/顶点数，边数顶点数，边数顶点数，边数顶点数，边数22222.2.2.2.邻接表邻接表邻接表邻接表1.1.无向图的邻接表无向图的邻接表一种顺序和链式相结合的存储结构一种顺序和链式相结合的存储结构一种顺序和链式相结合的存储结构一种顺序和链式相结合的存储结构顶点数组顶点数组与顶点邻接的顶点链表与顶点邻接的顶点链表表头结点表头结点表结点表结点23232.2.有向图的邻接表（有向图的邻接表（出出边表）和逆邻接表（边表）和逆邻接表（入入边表）边表）逆邻接表逆邻接表邻接表邻接表24243.3.3.3.邻接表存储下图的有关操作邻接表存储下图的有关操作邻接表存储下图的有关操作邻接表存储下图的有关操作1 1 1 1）求顶点）求顶点）求顶点）求顶点v v v v的度：的度：的度：的度：2 2 2 2）判断两顶点是否邻接：）判断两顶点是否邻接：）判断两顶点是否邻接：）判断两顶点是否邻接：3 3 3 3）检测图中的总边数：）检测图中的总边数：）检测图中的总边数：）检测图中的总边数：逆邻接表逆邻接表邻接表邻接表邻接表邻接表2525邻接表的定义结构邻接表的定义结构邻接表的定义结构邻接表的定义结构typedef struct arcnodetypedef struct arcnodetypedef struct arcnodetypedef struct arcnode int adjvex int adjvex int adjvex int adjvex；struct arcnode*nextarc struct arcnode*nextarc struct arcnode*nextarc struct arcnode*nextarc；arcnode arcnode arcnode arcnode；typedef struct vexnodetypedef struct vexnodetypedef struct vexnodetypedef struct vexnode int vertex int vertex int vertex int vertex；arcnode*firstarc arcnode*firstarc arcnode*firstarc arcnode*firstarc；vexnode vexnode vexnode vexnode；typedef struct graphtypedef struct graphtypedef struct graphtypedef struct graph vexnode adjlist vnum vexnode adjlist vnum vexnode adjlist vnum vexnode adjlist vnum ；int vexnum int vexnum int vexnum int vexnum，arcnum arcnum arcnum arcnum；graph graph graph graph；2626习题习题2.2.（2 2）已知无向图）已知无向图G G的结点数为的结点数为n n，边数为，边数为e e，其邻，其邻接表表示中的表结点数与表头结点数之和为接表表示中的表结点数与表头结点数之和为 答案：答案：n+2en+2e表表结结点点数数表表头头结结点点数数27271.1.邻接表表示法是借助邻接表表示法是借助_来反映顶点间的来反映顶点间的邻接关系，其中的结点称为表结点。邻接关系，其中的结点称为表结点。习题习题答案：单链表答案：单链表28283.3.对于无向图的邻接矩阵，顶点对于无向图的邻接矩阵，顶点vivi的度是的度是_。对于有向图的邻接矩阵，顶点对于有向图的邻接矩阵，顶点vivi的出度的出度ODOD（vivi）为）为_，顶点，顶点vivi的入度的入度ID(vi)ID(vi)是是_。习题习题答案：答案：矩阵第矩阵第i i行（列）非零元素的个数；行（列）非零元素的个数；矩阵第矩阵第i i行非零元素的个数；行非零元素的个数；矩阵第矩阵第i i列非零元素的个数；列非零元素的个数；29295.3 5.3 图的遍历图的遍历 图的遍历：从图的图的遍历：从图的图的遍历：从图的图的遍历：从图的某顶点某顶点某顶点某顶点出发，访问图中所有出发，访问图中所有出发，访问图中所有出发，访问图中所有顶点，并且每个顶点仅访问一次。顶点，并且每个顶点仅访问一次。顶点，并且每个顶点仅访问一次。顶点，并且每个顶点仅访问一次。有两种遍历方法有两种遍历方法：深度优先遍历（深度优先遍历（DFSDFS：Depth First SearchDepth First Search）广度优先遍历（广度优先遍历（BFSBFS：Breadth First SearchBreadth First Search）3030一一 、深度优先遍历（、深度优先遍历（DFSDFS）从图中某顶点从图中某顶点v v出发：出发：1 1）访问顶点）访问顶点v v；2 2）依次从）依次从v v的的未被访问的邻接点未被访问的邻接点出发，继续对图进行深出发，继续对图进行深度优先遍历；度优先遍历；由于没有规定访问邻接点的顺序，由于没有规定访问邻接点的顺序，DFSDFS序列不唯一序列不唯一abchdekfgachkfedbg3131void dfs(int v)void dfs(int v)访问访问v;v;visitv=1;visitv=1;找到找到g g中中v v的第一个邻接点的第一个邻接点w;w;while(w while(w存在存在)if(visit w=0)if(visit w=0)dfs(w);dfs(w);令令 w=g w=g图中图中v v的下一个邻接点的下一个邻接点 深度优先遍历算法深度优先遍历算法3232图中某未访问过的顶点图中某未访问过的顶点vivi出发：出发：1 1）访问顶点）访问顶点vi vi；2 2）访问）访问 vi vi 的所有的所有未被访问未被访问的邻接点的邻接点w w1 1,w,w2 2,w,wk k ；3 3）依次从这些邻接点出发依次从这些邻接点出发，访问它们的所有未被访问，访问它们的所有未被访问的邻接点的邻接点;依此类推，直到图中所有访问过的顶点的邻依此类推，直到图中所有访问过的顶点的邻接点都被访问；接点都被访问；二、广度优先遍历（二、广度优先遍历（BFSBFS）Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w43333n n问题：如何保证邻接点的出发顺序？问题：如何保证邻接点的出发顺序？n n解决：利用队列。解决：利用队列。1 1 1 1）从图中某未访问过的顶点）从图中某未访问过的顶点）从图中某未访问过的顶点）从图中某未访问过的顶点vivivivi出发：出发：出发：出发：2 2 2 2）访问顶点）访问顶点）访问顶点）访问顶点vi vi vi vi；3 3 3 3）访问）访问）访问）访问vivivivi的所有未被访问的邻接点的所有未被访问的邻接点的所有未被访问的邻接点的所有未被访问的邻接点w1,w2,wk w1,w2,wk w1,w2,wk w1,w2,wk；4 4 4 4）将）将）将）将w1,w2,wkw1,w2,wkw1,w2,wkw1,w2,wk入队；入队；入队；入队；5 5 5 5）取队头顶点，从该顶点出发，访问它的所有未被访）取队头顶点，从该顶点出发，访问它的所有未被访）取队头顶点，从该顶点出发，访问它的所有未被访）取队头顶点，从该顶点出发，访问它的所有未被访问的邻接点；即重复问的邻接点；即重复问的邻接点；即重复问的邻接点；即重复2 2 2 25 5 5 5，直到图中所有访问过的顶，直到图中所有访问过的顶，直到图中所有访问过的顶，直到图中所有访问过的顶点的邻接点都被访问点的邻接点都被访问点的邻接点都被访问点的邻接点都被访问3434void bfs(int v)void bfs(int v)void bfs(int v)void bfs(int v)初始化队列初始化队列初始化队列初始化队列Q Q Q Q；访问访问访问访问v v v v；visitedv=1 visitedv=1 visitedv=1 visitedv=1；v v v v入队；入队；入队；入队；当队非空时，当队非空时，当队非空时，当队非空时，出队出队出队出队v v v v 找到找到找到找到v v v v的第一个邻接点的第一个邻接点的第一个邻接点的第一个邻接点w w w w 当当当当w w w w存在存在存在存在 若若若若w w w w未被访问，未被访问，未被访问，未被访问，访问访问访问访问w w w w，visitedw=1 visitedw=1 visitedw=1 visitedw=1；w w w w入队；入队；入队；入队；w=g w=g w=g w=g中中中中v v v v的下一个邻接点；的下一个邻接点；的下一个邻接点；的下一个邻接点；35351 1一有向图一有向图G G的邻接表存储结构如图所示。现按深的邻接表存储结构如图所示。现按深度优先遍历算法，从顶点度优先遍历算法，从顶点V1V1出发，所得到的顶点序出发，所得到的顶点序列可能是列可能是 （）V1,V3,V2,V4,V5 V1,V3,V4,V2,V5 V1,V3,V2,V4,V5 V1,V3,V4,V2,V5 V1,V2,V3,V4,V5 V1,V3,V4,V5,V2 V1,V2,V3,V4,V5 V1,V3,V4,V5,V2 习题习题答案：答案：3636图的连通分量图的连通分量abcdegfaedcbgfabcdegfaedcbgf3737连通分量连通分量深度优先生成树深度优先生成树广度优先生成树广度优先生成树a ae ed dc cb bg gf fabcdegfaedcbgf3838连通分量连通分量深度优先生成树深度优先生成树广度优先生成树广度优先生成树abcdegfabcdegfaedcbgf3939图的连通分量图的连通分量对图进行对图进行dfs和和bfs，每次调用得到一个连通分量，每次调用得到一个连通分量思考题目：如何运用思考题目：如何运用dfs和和bfs判断图是否为连通图？判断图是否为连通图？abcdegfaedcbgf40401.1.对有向图对有向图G,G,如果从任意顶点出发进行一次深度优如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是先或广度优先搜索能访问到每个顶点，则该图一定是完全图。完全图。判断题判断题4141生成树生成树包含无向图包含无向图G G所有顶点的极小连通子图称为所有顶点的极小连通子图称为G G的生成树的生成树若若T T是是G G 的生成树当且仅当的生成树当且仅当T T 满足如下条件满足如下条件 T T是是G G 的连通子图的连通子图 T T包含包含G G 的所有顶点的所有顶点 T T中无回路中无回路abcdegfaedcbgfabcdegfaedcbgf42421.1.若连通图若连通图G G顶点个数为顶点个数为n n，则，则G G的生成树的边数为的生成树的边数为n-1n-1。2.2.如果如果G G的一个子图的一个子图GG的边数大于的边数大于n-1n-1，则，则GG中一定中一定有环。有环。3.3.相反，如果相反，如果GG的边数小于的边数小于n-1n-1，则，则GG一定不连通。一定不连通。结论结论abcdegfaedcbgfabcdegfaedcbgf43435.4 5.4 最小生成树最小生成树 假设要在假设要在 n 个城市之间建立通讯联络网，个城市之间建立通讯联络网，则连通则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，如何条线路，如何在最节省经费的前提下建立这个通讯网？在最节省经费的前提下建立这个通讯网？问题：问题：4444 假设要在假设要在 n 个城市之间建立通讯联络网，个城市之间建立通讯联络网，则连通则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，如何条线路，如何在最节省经费的前提下建立这个通讯网？在最节省经费的前提下建立这个通讯网？abcdegf195141827168213ae12dcbgf7148531621假设用顶点表示城市，假设用顶点表示城市，边表示城市间的通信边表示城市间的通信线路，边上的权表示线路，边上的权表示费用费用4545abcdegf195141827168213ae12dcbgf7148531621abcdegf51827821ae12dcbgf85214646abcdegf195141827168213ae12dcbgf7148531621abcdegf514168213aedcbgf1485316214747最小生成树最小生成树 若有一个连通的无向图若有一个连通的无向图G G，有，有n n个顶点，并且它的边是个顶点，并且它的边是有权值的。在有权值的。在G G上构造生成树上构造生成树 G G ,最小生成树最小生成树n-1n-1条边条边的权值之和最小的的权值之和最小的 G G 。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）算法一：（普里姆算法）算法一：（普里姆算法）4848用普里姆算法构造最小生成树用普里姆算法构造最小生成树 取图中任意一个顶点取图中任意一个顶点 v 作为生成树的根，之后往生作为生成树的根，之后往生成树上添加新的顶点成树上添加新的顶点 w。在添加的顶点在添加的顶点 w 和已经在生和已经在生成树上的顶点成树上的顶点v 之间必定存在一条边，并且该边的权值之间必定存在一条边，并且该边的权值在所有连通顶点在所有连通顶点 v 和和 w 之间的边中取值最小。之间的边中取值最小。之后继之后继续往生成树上添加顶点，直至生成树上含有续往生成树上添加顶点，直至生成树上含有 n-1 个顶点个顶点为止。为止。4949abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=675050v2v1v3v7v6v5v46454735151具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然后从，然后从权值最小的边开始，若它的添加不使权值最小的边开始，若它的添加不使SG 中产生回路，中产生回路，则在则在 SG 上加上这条边，如此重复，直至加上上加上这条边，如此重复，直至加上 n-1 条边条边为止。为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：5252abcdegf195141827168213ae12dcbgf71485316217121819535354545.5 5.5 拓扑排序拓扑排序5555 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 56565757 拓扑排序是有向图的一个重要操作。在给定的拓扑排序是有向图的一个重要操作。在给定的拓扑排序是有向图的一个重要操作。在给定的拓扑排序是有向图的一个重要操作。在给定的有向图有向图有向图有向图G G G G中，若顶点序列中，若顶点序列中，若顶点序列中，若顶点序列v v v vi1i1i1i1,v,v,v,vi2i2i2i2,.,v,.,v,.,v,.,vinininin满足下列条满足下列条满足下列条满足下列条件：若在有向图件：若在有向图件：若在有向图件：若在有向图G G G G中从顶点中从顶点中从顶点中从顶点v v v vi i i i到顶点到顶点到顶点到顶点v v v vj j j j有一条路径，有一条路径，有一条路径，有一条路径，则在序列中顶点则在序列中顶点则在序列中顶点则在序列中顶点v v v vi i i i必在顶点必在顶点必在顶点必在顶点v v v vj j j j之前，便称这个序列为之前，便称这个序列为之前，便称这个序列为之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为一个拓扑序列。求一个有向图拓扑序列的过程称为一个拓扑序列。求一个有向图拓扑序列的过程称为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。拓扑排序。拓扑排序。拓扑排序。BDAC可求得拓扑有序序列：可求得拓扑有序序列：A B C D A B C D 或或 A C B D A C B D5858BDAC对于下列有向图对于下列有向图不能求得它的拓扑有序序列。不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B,C,D B,C,D5959如何进行拓扑排序？如何进行拓扑排序？1.从有向图中选取一个从有向图中选取一个没有前驱没有前驱的顶点，并输出之；的顶点，并输出之；2.从有向图中从有向图中删去删去此顶点以及此顶点以及所有以它为尾的弧所有以它为尾的弧；3.重复上述两步，直至图空，或者图不空但找不到无重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。前驱的顶点为止。abcghdfeabhcdgfe60601._1._的有向图，其全部顶点有可能排成一个的有向图，其全部顶点有可能排成一个拓扑序列。拓扑序列。练习练习答案：无环答案：无环61612.2.一个有向图一个有向图G G中若有弧中若有弧,、和和,则在图则在图G G的拓扑序列中，顶点的拓扑序列中，顶点ViVi、VjVj和和VkVk的的相对位置为相对位置为_。练习练习答案：答案：Vi,Vj,VkVi,Vj,Vk62623.3.在一个有向图的拓扑序列中，若顶点在一个有向图的拓扑序列中，若顶点a a在顶点在顶点b b之前，之前，则图中必有一条弧则图中必有一条弧。练习练习答案：答案：6363写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits64 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日