数据结构(四).ppt

数据结构（四）数据结构（四）图型结构图型结构 图的概念图的概念图（图（graph）是图型结构的简称。它是一种）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都复杂的非线性数据结构。图在各个领域都着广泛的应用。图的二元组定义为：着广泛的应用。图的二元组定义为：G=（V,E）其中其中V是非空的顶点集合，即是非空的顶点集合，即 V=vi|1=i=1,vi elemtype，n 为顶点数为顶点数图的基本术语图的基本术语 1、端点和邻接点、端点和邻接点 在一个无向图中，若存在在一个无向图中，若存在条边（条边（vi，vj），则称），则称vi,vj为此边的两个端点，并称它们互为邻接点为此边的两个端点，并称它们互为邻接点（adjacent），即），即vi是是vj的一个邻接点，的一个邻接点，vj也是也是vi的一个邻接点。的一个邻接点。在一个有向图中，若存在一条边在一个有向图中，若存在一条边，则称此，则称此边是顶点边是顶点vi的一条出边（的一条出边（outedge），顶点），顶点vj的一的一条入边（条入边（inedge）；）；称称Vi为此边的起始端点，简为此边的起始端点，简称起点或始点，称起点或始点，vj为此边的终止端点，简称终点；为此边的终止端点，简称终点；称称vi和和vj互为邻接点，并称互为邻接点，并称vj是是vi的出边邻接点，的出边邻接点，vi是是vj的入边邻接点。的入边邻接点。2、顶点的度、入度、出度顶点的度、入度、出度 无向图顶点无向图顶点v的度（的度（degree）定义为以）定义为以该顶点为一个端点的边的数目，简单地说，该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为就是该顶点的边的数目，记为D（v）。如）。如图图71的的G1中中v1顶点的度为顶点的度为4，v2顶点的度顶点的度为为2。有向图中顶点。有向图中顶点v的度有入度和出度之分，的度有入度和出度之分，入度（入度（indegree）是该顶点的入边的数目，）是该顶点的入边的数目，记为记为ID（v）；出度（）；出度（outdegree）是该顶）是该顶点的出边的数目，记为点的出边的数目，记为OD（v）顶点）顶点v的度的度等于它的入度和出度之和，即等于它的入度和出度之和，即D（v）=ID（v）+OD（v）。）。3、完全图、稠密图、稀疏图、完全图、稠密图、稀疏图 若无向图中的每两个顶点之间都存在着若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。着方向相反的两条边，则称此图为完全图。显然，若完全图是无向的，则图中包含有显然，若完全图是无向的，则图中包含有n（n1）/2条边条边,若完全图是有向的，则图若完全图是有向的，则图中包含有中包含有n（n1）条边。当一个图接近完全）条边。当一个图接近完全图时，则可称为稠密图，相反地，当一个图图时，则可称为稠密图，相反地，当一个图有较少的边数（即有较少的边数（即e n（n 1）时，则）时，则可称为稀疏图。可称为稀疏图。4、子图子图 设有两个图设有两个图G=（V,E）和）和G （V,E）,若若V是是V的子集，且的子集，且E是是E的子集，则的子集，则成成G是是G的子图。的子图。5、路径和回路、路径和回路 在一个图在一个图G中，从顶点中，从顶点v到顶点到顶点v的一条路径的一条路径（path）是一个顶点序列）是一个顶点序列vi0,vi1,vi2,vim,其中其中v=vi0,v=vim,若此图是无向图，则（若此图是无向图，则（vij1,vij）E（G），（），（1jm）；若此图是有向图，）；若此图是有向图，则则E（G），（），（1jm）。路径长度）。路径长度是指该路径上经过的边的数目。若一条路径上除是指该路径上经过的边的数目。若一条路径上除了前后端点可以相同外，所有顶点均不同，则称了前后端点可以相同外，所有顶点均不同，则称此路径为简单路径。若一条路径上的前后两端点此路径为简单路径。若一条路径上的前后两端点相同，则被称为回路或环（相同，则被称为回路或环（cycle），前后两端点），前后两端点相同的简单路径被称为简单回路或简单环相同的简单路径被称为简单回路或简单环。6、连通和连通分量、连通和连通分量 在无向图在无向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径，则称有路径，则称vi和和vj是连通的。若图是连通的。若图G中任意两个顶点都连通，则称中任意两个顶点都连通，则称G为连为连通图，否则称为非连通图。无向图通图，否则称为非连通图。无向图G的的极大连通子图称为极大连通子图称为G的连通分量。显然，的连通分量。显然，任何连通图的连通分量只有一个，即本任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。身，而非连通图有多个连通分量。7、强连通图和强连通分量、强连通图和强连通分量 在有向图在有向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径，则称从有路径，则称从vi到到vj是连通的。若图是连通的。若图G中的任意两个顶点中的任意两个顶点vi和和vj都连通，即都连通，即从从vi到到vj和从和从vj到到vi都存在路径，则称都存在路径，则称G是强连通图。有向图是强连通图。有向图G的极大强连通子的极大强连通子图称为图称为G的强连通分量。显然，强连通的强连通分量。显然，强连通图只有一个强连通分量，即本身，非强图只有一个强连通分量，即本身，非强连通图有多个强连通分量。连通图有多个强连通分量。8、权和网、权和网 在一个图中每条边可以标上具有某种在一个图中每条边可以标上具有某种含义的数值，此数值称为该边的权含义的数值，此数值称为该边的权（weight）。例如，对于一个反映城市交）。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长通线路的图，边上的权可表示该条线路的长度或等级；对于一个反映电子线路的图，边度或等级；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；上的权可表示两端点间的电阻、电流或电压；对于一个反映零件装配的图，边上的权可表对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数示一个端点需要装配另一个端点的零件的数量；对于一个反映工程进度的图，边上的权量；对于一个反映工程进度的图，边上的权可表示从前一子工程到后一子工程所需要的可表示从前一子工程到后一子工程所需要的天数。边上带有权的图称作带权图，也常称天数。边上带有权的图称作带权图，也常称作网（作网（network）。）。图的存储结构图的存储结构 1、邻接矩阵邻接矩阵 邻接矩阵（邻接矩阵（adjacency matrix）是表示顶点）是表示顶点之间相邻关系的矩阵。设之间相邻关系的矩阵。设G（V，E）是具）是具有有n个顶点的图，顶点序号依次为个顶点的图，顶点序号依次为1、2、n，则，则G的邻接矩阵是具有如下定义的邻接矩阵是具有如下定义的的n阶方阵。阶方阵。2、邻接表邻接表 邻接表（邻接表（adjacency list）是对图中的）是对图中的每个顶点建立一个邻接关系的单链表，并把每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示它们的表头指针用向量存储的一种图的表示方法。为顶点方法。为顶点vi建立的邻接关系的单链表又建立的邻接关系的单链表又称作称作vi的邻接表。的邻接表。vi邻接表中的每个结点用邻接表中的每个结点用来存储以该顶点为端点或起点的一条边的信来存储以该顶点为端点或起点的一条边的信息，因而被称为边结点。息，因而被称为边结点。vi邻接表中的结点邻接表中的结点数，对于无向图来说，等于数，对于无向图来说，等于vi的边数，邻接的边数，邻接点数或度数；对于有向图来说，等于点数或度数；对于有向图来说，等于vi的出的出边数、出边邻接点数或出度数。边数、出边邻接点数或出度数。3、边集数组边集数组 边集数组（边集数组（edgeset array）是利用一维）是利用一维数组存储图中所有边的一种图的表示方法。数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中边该数组中所含元素的个数要大于等于图中边的条数，每个元素用来存储一条边的起点、的条数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），下各边在起点或终点）和权（若有的话），下各边在数组中的次序可任意安排，也可根据具体要数组中的次序可任意安排，也可根据具体要求而定。求而定。图的遍历图的遍历 1、深度优先遍历深度优先遍历 深度优先搜索（深度优先搜索（depth first search）遍历类）遍历类似树的先根遍历，它是一个递归过程，可叙述为：似树的先根遍历，它是一个递归过程，可叙述为：首先访问一个顶点首先访问一个顶点vi（开始为初始点），并将其（开始为初始点），并将其标记为已访问过，然后从标记为已访问过，然后从vi的一个未被访问的邻的一个未被访问的邻接点（无向图）或出边邻接点（有向图）出发进接点（无向图）或出边邻接点（有向图）出发进行深度优先搜索遍历，当行深度优先搜索遍历，当vi的所有邻接点均被访的所有邻接点均被访问过时，则退回到上一个顶点问过时，则退回到上一个顶点vk，从，从vk的另一个的另一个未被访问过的邻接点出发进行深度优先搜索遍历。未被访问过的邻接点出发进行深度优先搜索遍历。2、广度优先搜索遍历、广度优先搜索遍历 广度优先搜索（广度优先搜索（breadthfirst search）遍历类似树的按层遍历，其过程）遍历类似树的按层遍历，其过程为：首先访问初始点为：首先访问初始点vi,并将其标记为已访并将其标记为已访问过，接着访问问过，接着访问vi的所有未被访问过的邻接的所有未被访问过的邻接点点vi1,vi2,vit并均标记为已访问过，然并均标记为已访问过，然后再按照后再按照vi1,vi2,vit的次序，访问每一的次序，访问每一个顶点的所有未被访问过的邻接点，并均标个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和记为已访问过，依次类推，直到图中所有和初始点初始点vi有路径相通的顶点都被访问过为止。有路径相通的顶点都被访问过为止。非连通图的遍历非连通图的遍历 前面提到的深度优先遍历和广度优先遍前面提到的深度优先遍历和广度优先遍历都只从图的一个顶点开始进行一次遍历，历都只从图的一个顶点开始进行一次遍历，对于连通图可以遍历到图的所有结点，但对于连通图可以遍历到图的所有结点，但如果图不连通，则有一部分结点无法访问如果图不连通，则有一部分结点无法访问到。修改很简单，每次选取任意一个没有到。修改很简单，每次选取任意一个没有被遍历过的结点开始一次遍历，重复此操被遍历过的结点开始一次遍历，重复此操作直到遍历完图的所有结点即可。作直到遍历完图的所有结点即可。图的生成树与最小生成树图的生成树与最小生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G，即：若边集E（G）中的边既将图中的所有顶点连通又不形成回路，则称子图G是原图G的一棵生成树。普里姆算法普里姆算法 假设假设G=（V，E）是一个具有）是一个具有n个顶点的连通网，个顶点的连通网，T=（U，TE）是）是G的最小生成树，其中的最小生成树，其中U是是T的顶点集，的顶点集，TE是是T的边集，的边集，U和和TE的初值均为空集。算法开始的初值均为空集。算法开始时，首先从时，首先从V中任取一个顶点（假定取中任取一个顶点（假定取v1），将它），将它并入并入U中，此时中，此时U=v1，然后只要，然后只要U是是V的真子集的真子集（即），就从那些其一个端点已在（即），就从那些其一个端点已在T中，另一个端中，另一个端点仍在点仍在T外的所有边中，找一条最短（即权值最小）外的所有边中，找一条最短（即权值最小）边，假定为（边，假定为（vi，vj），其中，并把该边（），其中，并把该边（vi，vj）和顶点）和顶点vj分别并入分别并入T的边集的边集TE和顶点集和顶点集U，如，如此进行下去，每次往生成树里并入一个顶点和一条此进行下去，每次往生成树里并入一个顶点和一条边，直到（边，直到（n一一1）次后就把所有）次后就把所有n个顶点都并入到个顶点都并入到生成树生成树T的顶点集中，此时的顶点集中，此时UV，TE中含有（中含有（n一一1）条边，）条边，T就是最后得到的最小生成树就是最后得到的最小生成树。普里姆算法的关键之处是：每次如何从生成普里姆算法的关键之处是：每次如何从生成树树T中到中到T外的所有边中，找出一条最短边。外的所有边中，找出一条最短边。例如，在第例如，在第k次前，生成树次前，生成树T中已有中已有k个顶点个顶点和（和（k1）条边，此时）条边，此时T中到中到T外的所有边数外的所有边数为为k（nk），当然它包括两顶点间没有直接），当然它包括两顶点间没有直接边相连，其权值被看作为边相连，其权值被看作为“无穷大无穷大”的边在的边在内，从如此多的边中查找最短边，其时间复内，从如此多的边中查找最短边，其时间复杂性为杂性为O（k（nk），显然是很费时的。），显然是很费时的。是否有一种好的方法能够降低查找最短边的是否有一种好的方法能够降低查找最短边的时间复杂性呢？时间复杂性呢？方法是：假定在进行第方法是：假定在进行第k次前已经保留着从次前已经保留着从T中到中到T外每一外每一顶点（共（顶点（共（nk）个顶点）的各一条最短边，进行第）个顶点）的各一条最短边，进行第k次时，次时，首先从这（首先从这（nk）条最短边中，找出一条最最短的边（它）条最短边中，找出一条最最短的边（它就是从就是从T中到中到T外的所有边中的最短边），假设为（外的所有边中的最短边），假设为（vi,vj），），此步需进行（此步需进行（nk）次比较；然后把边（）次比较；然后把边（vi,vj）和顶点）和顶点vj分别并入分别并入T中的边集中的边集TE和顶点集和顶点集U中，此时中，此时T外只有外只有n（k+1）个顶点，对于其中的每个顶点）个顶点，对于其中的每个顶点vt，若（，若（vj,vt）边）边上的权值小于已保留的从原上的权值小于已保留的从原T中到中到vt的最短边的权值，则的最短边的权值，则用（用（v，vt）修改之，使从）修改之，使从T中到中到T外顶点外顶点vt的最短边为（的最短边为（vj，vt），否则原有最短边保持不变，这样，就把第），否则原有最短边保持不变，这样，就把第k次后从次后从T中到中到T外每一顶点外每一顶点vt的各一条最短边都保留下来了。为进的各一条最短边都保留下来了。为进行第（行第（k+1）次运算做好了准备，此步需进行（）次运算做好了准备，此步需进行（nk1）次）次比较。所以，利用此方法求第比较。所以，利用此方法求第k次的最短边共需比较次的最短边共需比较2（nk）1次，即时间复杂性为次，即时间复杂性为O（nk）。）。克鲁斯卡尔算法克鲁斯卡尔算法假设假设G（V，E）是一个具有）是一个具有n个顶点的连个顶点的连通网，通网，T（U，TE）是）是G的最小生成树，的最小生成树，U的初值等于的初值等于V，即包含有，即包含有G中的全部顶点，中的全部顶点，TE的初值为空。此算法的基本思想是，将图的初值为空。此算法的基本思想是，将图G中的边按权值从小到大的顺序依次选取，中的边按权值从小到大的顺序依次选取，若选取的边使生成树若选取的边使生成树T不形成回路，则把它不形成回路，则把它并入并入TE中，保留作为中，保留作为T的一条边，若选取的的一条边，若选取的边使生成树边使生成树T形成回路，则将其舍弃，如此形成回路，则将其舍弃，如此进行下去，直到进行下去，直到TE中包含有中包含有n 1条边为止。条边为止。此时的此时的T即为最小生成树。即为最小生成树。克鲁斯卡尔算法的关键之处是：如何判断欲克鲁斯卡尔算法的关键之处是：如何判断欲加入的一条边是否与生成树中已选取的边形加入的一条边是否与生成树中已选取的边形成回路。这可将各顶点划分为所属集合的方成回路。这可将各顶点划分为所属集合的方法来解决，每个集合中的顶点表示一个无回法来解决，每个集合中的顶点表示一个无回路的连通分量。算法开始时，由于生成树的路的连通分量。算法开始时，由于生成树的顶点集等于图顶点集等于图G的顶点集，边集为空，所以的顶点集，边集为空，所以n个顶点分属于个顶点分属于n个集合。每个集合中只有一个个集合。每个集合中只有一个顶点，表明顶点之问互不连通。顶点，表明顶点之问互不连通。最短路径最短路径由于从一顶点到另一顶点可能存在着多条路由于从一顶点到另一顶点可能存在着多条路径。每条路径上所经过的边数可能不同，即径。每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。其路径长度叫做最短路径长度或最短距离。求图中一顶点求图中一顶点vi到其余各顶点的最短路径和到其余各顶点的最短路径和最短距离比较容易，只要从该顶点最短距离比较容易，只要从该顶点vi，出发，出发对图进行一次广度优先搜索遍历，在遍历时对图进行一次广度优先搜索遍历，在遍历时记下每个结点的层次即可。记下每个结点的层次即可。若图是带权图（假定权值非负）从源点若图是带权图（假定权值非负）从源点vi到到终点终点vj的每条路径上的权（它等于该路径上的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条径长度）可能不同，我们把权值最小的那条路径也称做最短路径，其权值也称作最短路路径也称做最短路径，其权值也称作最短路径长度或最短距离。径长度或最短距离。际上，这两类最短路径问题可合并为一类，际上，这两类最短路径问题可合并为一类，这只要把第一类的每条边的权都设为这只要把第一类的每条边的权都设为1就归就归属于第二类了，所以在以后的讨论中，若不属于第二类了，所以在以后的讨论中，若不特别指明，均是指第二类的最短路径问题。特别指明，均是指第二类的最短路径问题。求图的最短路径问题包括两个子子问题：一求图的最短路径问题包括两个子子问题：一是求图中一顶点到其余各顶点的最短路径，是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面二是求图中每对顶点之间的最短路径。下面分别进行讨论。分别进行讨论。从一顶点到其余各顶点的最短路径迪杰斯特拉（迪杰斯特拉（Dijkstra）于）于1959年提出了解决此年提出了解决此问题的一般算法，具体做法是按照从源点到其余问题的一般算法，具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度，每次求出从源点到各顶点的最短路径及长度，每次求出从源点vi到一个终点到一个终点vj的最短路径及长度后，都要以的最短路径及长度后，都要以vj作为作为新考虑的中间点，用新考虑的中间点，用vi到到vj的最短路径和最短路径的最短路径和最短路径长度对长度对vi到其它尚未求出最短路径的那些终点的到其它尚未求出最短路径的那些终点的当前路径及长度作必要的修改，使之成为当前新当前路径及长度作必要的修改，使之成为当前新的最短路径和最短路径长度，当进行的最短路径和最短路径长度，当进行n2次后算法次后算法结束。结束。每对顶点之间的最短路径 求图中每对顶点之间的最短路径是指把图求图中每对顶点之间的最短路径是指把图中任意两个顶点中任意两个顶点vi和和vj（ij）之间的最短）之间的最短 路径都计算出来。解决此问题有两种方法：路径都计算出来。解决此问题有两种方法：一是分别以图中的每个顶点为源点共调用一是分别以图中的每个顶点为源点共调用n次迪杰斯特拉算法，此方法的时间复杂性次迪杰斯特拉算法，此方法的时间复杂性为为O（n3）；二是采用下面介绍的弗洛伊德）；二是采用下面介绍的弗洛伊德（Floyed）算法，此算法的时间复杂性仍）算法，此算法的时间复杂性仍为为O（n3），但比较简单。），但比较简单。弗洛伊德算法实际上是一个动态规划的算法。从图的邻接矩阵开始，按照顶点v1，v2，vn的次序，分别以每个顶点vk（1kn）作为新考虑的中间点，在第k-1次运算Ak-1 （A（0）为原图的邻接矩阵G）的基础上，求出每对顶点vi到vj的最短路径长度计算公式为：拓扑排序拓扑排序 在实际工作中，经常用一个有向图来表示在实际工作中，经常用一个有向图来表示施工的流程图，或产品生产的流程图。一施工的流程图，或产品生产的流程图。一个工作往往可以分为若干个子工程，把子个工作往往可以分为若干个子工程，把子工程称为工程称为“活动活动”。在有向图种若以顶点。在有向图种若以顶点表示表示“活动活动”的网的网(Activity On Vertex network),简称为简称为AOV网。网。对于一个对于一个AOV网，构造其所有顶点的线性网，构造其所有顶点的线性序列，使此序列不仅保持网中各顶点间原序列，使此序列不仅保持网中各顶点间原有的先后关系，而且使原来没有先后关系有的先后关系，而且使原来没有先后关系的顶点之间也建立起人为的先后关系。这的顶点之间也建立起人为的先后关系。这样的线性序列称为拓扑有序序列。构造样的线性序列称为拓扑有序序列。构造AOV网的拓扑有序序列的运算称为拓扑排网的拓扑有序序列的运算称为拓扑排序。序。某个某个AOV网，如果它的拓扑有序序列被网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其构造成功，则该网中不存在有向回路，其各个子工程可按拓扑有序序列的次序进行各个子工程可按拓扑有序序列的次序进行安排。显然，一个安排。显然，一个AOV网的网的拓扑有序序列并不是唯一的。对对AOV网进行拓扑排序的方法和步骤网进行拓扑排序的方法和步骤是：是：在网中选择一个没有前趋的顶点且输在网中选择一个没有前趋的顶点且输出之；出之；从网中删去该顶点，并且删去从该顶从网中删去该顶点，并且删去从该顶点发出的全部有向边；点发出的全部有向边；重复上述两步，直至网中不存在没有重复上述两步，直至网中不存在没有前趋的顶点为止。前趋的顶点为止。