数据结构第7章课件

数据结构第7章课件第7章图学习目标与要求：了解图的定义和相关术语。熟练掌握图的邻接矩阵和邻接链表表示。熟练掌握图的两种遍历方式：深度优先搜索和广度优先搜索。熟练掌握求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。熟练掌握求单源最短路径的迪杰斯特拉算法，了解求每对顶点间最短路径的弗洛伊德算法。熟练掌握求拓扑序列的方法。2第7章图学习目标与要求：2图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。7.1图的定义和术语3图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，图是由非空的顶点集合和一个描述顶点之间关系—边的有限集合组成的一种数据结构。可以用二元组定义为：

G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。7.1图的定义和术语4图是由非空的顶点集合和一个描述顶点之间关系—边的有限集合组成V1V3V2V4V5

G1=（V1，E1）V1＝{v1,v2,v3,v4,v5}；E1＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称为边。7.1图的定义和术语5V1V3V2V4V5G1=（V1，E1）7.1图的定义V1V3V2V4G2=(V2,E2)V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}<vi,vj>表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。7.1图的定义和术语6V1V3V2V4G2=(V2,E2)7.1图的定义和术语假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶点到自身的边或者弧，即如果<vi,vj>,则vi≠vj。对于无向图，边数e的取值范围为0~n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图或无向完全图。对于有向图，弧度e的取值范围是0~n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。具有e<nlogn条弧或者边的图称为稀疏图。具有e>nlogn条弧或者边的图称为稠密图。7.1图的定义和术语7假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶7.1.2图的基本术语1．邻接点在无向图G=(V,E)中，如果存在边（vi,vj）∈E，则称vi和vj互为邻接点，即vi和vj相互邻接。边（vi,vj）依附于顶点vi和vj，或者称边（vi,vj）与顶点相互关联在有向图G=(V,E)中，如果存在弧<vi,vj>∈E，则称vi邻接到vj。弧<vi,vj>与顶点vi和vj相互关联。

87.1.2图的基本术语1．邻接点7.1.2图的基本术语2．顶点的度在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD(v)。在有向图中：(a)一个顶点拥有的弧头的数目，称为该顶点的入度，

记为ID(v)；(b)一个顶点拥有的弧尾的数目，称为该顶点的出度，

记为OD(v)；(c)一个顶点度等于顶点的入度+出度，

即：TD(v)=ID(v)＋OD(v)。

97.1.2图的基本术语2．顶点的度在图7-1的G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图7-2的G2中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2图7-1无向图G1图7-2有向图G2V1V3V2V4V5V1V3V2V47.1.2图的基本术语10在图7-1的G1中有：图7-1无向图G1图7-2有向图G7.1.2图的基本术语2．顶点的度假设顶点的个数为n，边数或弧数为e，顶点vi的度记作TD(vi),则顶点的度与弧度或者边数满足关系：

117.1.2图的基本术语2．顶点的度7.1.2图的基本术语3．路径在图中，从顶点vi出发经过一系列的顶点序列到达顶点vj称为从顶点vi到vj的路径。路径的长度是路径上弧或者边的数目。在路径中，如果第一个顶点与最后一个顶点相同，则这样的路径称为回路或者环。

127.1.2图的基本术语3．路径7.1.2图的基本术语3．路径在路径所经过的顶点序列中，如果顶点不重复出现，则称这样的路径为简单路径。在回路中，除了第一个顶点和最后一个顶点外，如果其他顶点不重复出现，则称这样的回路为简单回路或者简单环。

137.1.2图的基本术语3．路径4．子图对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。V1V3V2V1V3V2V4V5图7-3图G1和G2的两个子图示意V1V3V2V4V5V1V3V2V47.1.2图的基本术语144．子图V1V3V2V1V3V2V4V5图7-7.1.2图的基本术语5．连通图和强连通图在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图。否则，将其中的极大连通子图称为连通分量。

(a)无向图G3(b)G3的两个连通分量图7-4无向图及连通分量示意BCEFADIHGBCEADIFHG157.1.2图的基本术语5．连通图和强连通图5．连通图和强连通图在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图。否则，将其中的极大连通子图称为强连通分量。V1V3V2V4图7-5有向图G2的两个强连通分量示意有向图G2V1V3V2V4有向图G2的两个连通分量7.1.2图的基本术语165．连通图和强连通图V1V3V2V4图7-5有向图G2的6．生成树在含有n个顶点的图G中，如果G是包含n个顶点的极小连通子图，该子图只有n-1条边，这样的图称为连通图的生成树。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵包含n个顶点的生成树仅有n-1条边，如果少于n-1条边，则改图是非连通的。7.1.2图的基本术语176．生成树7.1.2图的基本术语176．生成树图7-6为图7-4中无向图G3的生成树。图7-6无向图G3生成树示意图BCEADI7.1.2图的基本术语BCEADI186．生成树图7-6无向图G3生成树示意图BCEADI7.7．网如果在图的边或者弧上增加具有一定意义的数，这些数称为权，权通常表示一个顶点到另一个顶点的距离或者花费，带有权的图称为网。一个网如图所示。图7-7网的示意图BCADE496141277.1.2图的基本术语197．网图7-7网的示意图BCADE496141277.17.2图的存储结构由于图的结构比较复杂，具体采用什么存储方式，要依据具体的操作。从图的定义可知，无论采用什么存储方式，都要能够描述图的顶点信息和边或弧的信息。下面介绍两种常用的图的存储结构。207.2图的存储结构由于图的结构比较复杂，具体采用什么存储7.2.1邻接矩阵图的邻接矩阵表示也称为数组表示，图的邻接矩阵就是利用C语言中的两个数组实现。其中一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。217.2.1邻接矩阵图的邻接矩阵表示也称为数组表示，图的邻7.2.1邻接矩阵设G=(V,E)是一个具有n个顶点的图(n≥1)，则G的邻接矩阵是表示顶点之间邻接关系的n阶方阵。该n阶方阵具有如下性质：227.2.1邻接矩阵设G=(V,E)是一个具有n个顶点的7.2.1邻接矩阵若G是网，则对应的n阶方阵具有如下性质：其中，wij表示边(vi,vj)或<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。237.2.1邻接矩阵若G是网，则对应的n阶方阵具有如下性质无向图用邻接矩阵表示法如图7-8所示；网用邻接矩阵表示法如图7-9所示。图7-9网的邻接矩阵表示图7-8一个无向图的邻接矩阵表示24无向图用邻接矩阵表示法如图7-8所示；网用邻接矩阵表示法如图

图的邻接矩阵具有以下性质：（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。（3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。7.2.1邻接矩阵25图的邻接矩阵具有以下性质：7.2.1邻接矩阵257.2.2邻接链表邻接表是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，该方法将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。267.2.2邻接链表邻接表是图的一种顺序存储与链式存储结合在邻接表表示中有两种结点结构，如图7-10所示。顶点域边表头指针邻接点域指针域vertexlinkadjvexnext顶点表边表图7-10邻接表表示的结点结构adjvexdatanext邻接点域指针域边上信息网的边表结构7.2.2邻接链表27在邻接表表示中有两种结点结构，如图7-10所示。vertex7.2.2邻接链表图7-11给出无向图对应的邻接表表示。

图7-11a图的邻接表表示287.2.2邻接链表图7-11给出无向图对应的邻接表表示。7.2.2邻接链表图7-11给出无向图对应的邻接表表示。

图7-11b图的邻接表表示297.2.2邻接链表图7-11给出无向图对应的邻接表表示。7.2.2邻接链表邻接链表存储图具有如下特点：(1)无向图中，第i个链表中的表结点数是顶点vi的度；有向图中，第i个链表中的表结点数是顶点vi的出度。(2)若无向图有n个顶点、e条边，则邻接链表需n个存储单元和2e个表结点。有向图存储n个顶点e条边，需要n个存储单元和e个表结点。对于边很少的图，用邻接链表比用邻接矩阵要节省存储单元。(3)在邻接链表中，要确定两个顶点vi和vj之间是否有边或弧相连，需要遍历第i个或第j个单链表，不像邻接矩阵那样能方便地对顶点进行随机访问。307.2.2邻接链表邻接链表存储图具有如下特点：307.3图的遍历图的遍历是对具有图状结构的数据线性化的过程。从图中任一顶点出发，访问输出图中各个顶点，并且使每个顶点仅被访问一次，这样得到顶点的一个线性序列，这一过程叫做图的遍历。图的遍历是个很重要的算法，图的连通性和拓扑排序等算法都是以图的遍历算法为基础的。下面分别介绍图的两种遍历方法：深度优先搜索和广度优先搜索，这两种方法既适用于无向图也适用于有向图。317.3图的遍历图的遍历是对具有图状结构的数据线性化7.3.1深度优先搜索深度优先搜索(DepthFirstSearch，DFS)遍历类似于二叉树的先序遍历，其基本思想是：初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将其标记为已访问，然后任选一个与v邻接且未被访问的顶点w访问输出并标记，再从与w邻接且未被访问的顶点z出发，进行深度优先搜索，重复这一过程，若到达某顶点不存在未被访问过的邻接顶点时，则一直退回到最近被访问过的且存在未被访问过邻接顶点的那个顶点再进行深度优先搜索，直至所有与v有路径相通的顶点都被访问到，若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做深度优先搜索327.3.1深度优先搜索深度优先搜索(DepthFirs7.3.1深度优先搜索对于图7-12所示的有向图其对应的邻接链表如图7-13所示得到的线性序列为1,2,4,3,5,7,6337.3.1深度优先搜索对于图7-12所示的有向图其对应的7.3.1深度优先搜索深度优先生成树或森林：由图中的全部顶点和深度优先搜索所经过的边即构成了深度优先生成树或森林。对图7.12所示有向图进行深度优先搜索得到的生成森林如图7.14所示。347.3.1深度优先搜索深度优先生成树或森林：由图中的全部7.3.2广度优先搜索广度优先搜索(BreadthFirstSearch，BFS)类似于二叉树的层次遍历。其基本思想是：初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将该顶点标记为已访问，然后依次访问输出与v邻接的未被访问的所有顶点，并标记为已访问，再分别从这些邻接点出发进行广度优先搜索，直至图中所有已被访问的顶点的邻接顶点都被访问到。若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做广度优先搜索。357.3.2广度优先搜索广度优先搜索(BreadthFi7.3.2广度优先搜索下面仍以图7.12所示有向图为例，说明广度优先搜索的过程，其存储结构为图7.13所示的邻接链表。得到的线性序列为1,2,4,3,5,7,6367.3.2广度优先搜索下面仍以图7.12所示有向图为例，7.3.2广度优先搜索对图7.12所示有向图进行广度优先搜索得到的生成森林如图7.15所示。377.3.2广度优先搜索对图7.12所示有向图进行广度优先V1V5V2V4V8V3V6V7v1→v2→v4→v8→v5→v3→v6→v7v1→v2→v3→v4→v5→v6→v7→v838V1V5V2V4V8V3V6V7v1→v2→v4→7.4最小生成树最小生成树就是指在一个连通网的所有生成树中，所有边的代价之和最小的那棵生成树。代价在网中用权值表示，一个生成树的代价就是生成树各边的代价之和。最小生成树有重要的研究意义，例如，要在n各城市建立一个交通图，就是要在n(n-1)/2条线路中选择n-1条代价最小的线路，在这里可以将各个城市看成图的顶点，城市的线路看成边。397.4最小生成树最小生成树就是指在一个连通网的所有生成树7.4最小生成树1．普里姆算法2．克鲁斯卡尔算法407.4最小生成树1．普里姆算法407.4.1普里姆(Prim)算法基本思想：假设G＝(V,E)是连通网，T＝(U,TE)为欲构造的最小生成树。(1)初始时令U={1}(即构造最小生成树时，从顶点1出发)，TE=Ф。(2)从所有u∈U，v∈V-U的边中，选取具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合TE中。(3)重复(2)，直到U＝V为止。417.4.1普里姆(Prim)算法基本思想：假设G＝(V,图7-16Prim算法构造最小生成树的过程示意图

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)681214161751566666888881212121414542图7-16Prim算法构造最小生成树的过程示意图AE7.4.2克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法构造最小生成树的基本思想是：假设G＝(V,E)是连通网，T＝(U,TE)为欲构造的最小生成树。(1)初始时令U＝V，TE＝Φ，即最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。(2)把G的边按权值升序排列。(3)从中选取权值最小边(u,v)，若(u,v)连接T中两个不同的连通分量，则将(u,v)并入T中。(4)重复(3)直到T中只有一个连通分量为止。437.4.2克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法图7-17Kruskal算法构造最小生成树的过程示意图

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)681214161751556666888512125514544图7-17Kruskal算法构造最小生成树的过程示意图7.5最短路径7.5.1单源最短路径单源最短路径是指在有向网中，以某个顶点v0作为源点，从v0出发，到其余各个顶点的最短路径。图7-18是个有向网，图7.19是其所对应的邻接矩阵cost，表7.1给出了对图7.18所示有向网，以1为源点，应用迪杰斯特拉算法求1到其余各顶点的最短路径的全过程及各数据结构的变化情况。457.5最短路径7.5.1单源最短路径45表7-1图7-19有向网的邻接矩阵循环SWdist[2]dist[3]dist[4]dist[5]pre[2]pre[3]pre[4]pre[5]初始化{1}--10∞3010011111{1,2}210603010012112{1,2,4}41050309014143{1,2,4,3}31050306014134{1,2,3,4,5}5105030601413图7-18有向网示意图46表7-1图7-19有向网的邻接矩阵循环SWdist[27.5.2每一对顶点之间的最短路径求每一对顶点之间的最短路径，可以通过两种方法：一是每次以图中的一个顶点作为源点，调用n次Dijkstra算法，便可求得图中每一对顶点间的最短路径。另一种方法是采用弗洛伊德(Floyd)算法，此算法比较简单，易于理解和编程。477.5.2每一对顶点之间的最短路径求每一对顶点之间的最短7.5.2每一对顶点之间的最短路径图7.20是一个有向网和它的邻接矩阵存储，按照弗洛伊德算法求每对顶点间的最短路径，矩阵D和path的变化情况如图7.21所示。487.5.2每一对顶点之间的最短路径图7.20是一个有向网7.6AOV网拓扑排序7.6.1AOV网一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其他有关子工程完成之后才能开始，为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、弧表示活动间先后关系的有向图称作AOV网(ActivityOnVertexNetwork)。497.6AOV网拓扑排序7.6.1AOV网7.6.1AOV网课程代码课程名先修课程代码C1程序设计导论无C2离散数学C6，C1C3数据结构C1，C2C4微机原理C1C5操作系统C3，C4C6高等数学无C7线性代数C6图7-22表示课程间先后关系的AOV网表7-2计算机专业学生必修课程名称与代号507.6.1AOV网课程代码课程名先修课程代码C1程序设计7.6.2AOV网拓扑排序一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行，活动会进入死循环，如图7.23所示是由三个顶点构成的一个回路，活动1结束才能进行2，2结束才能进行3，由此推出1结束才能进行3，而从图中存在的弧可知3结束才能进行1，因此出现矛盾。517.6.2AOV网拓扑排序一个AOV网应该是一个有向无环7.6.2AOV网拓扑排序对AOV网进行拓扑排序的方法如下：(1) 从AOV网中选择一个入度为0的顶点，并且输出它。(2) 从AOV网中删去该顶点和该顶点发出的全部有向边。(3) 重复(1)和(2)，直到找不到入度为0的顶点。此时，若网中仍有顶点没有输出，则说明AOV网中有环路。527.6.2AOV网拓扑排序对AOV网进行拓扑排序的方法如7.6.2AOV网拓扑排序对于图7.22所示AOV网，其拓扑排序的过程如图7.24所示，得到的一个拓扑序列为(1,6,7,2,3,4,5)。537.6.2AOV网拓扑排序对于图7.22所示AOV网，其7.6.2AOV网拓扑排序拓扑排序算法的步骤为：(1) 将id为0的顶点入栈。(2) 从栈中弹出栈顶元素并输出，并把该顶点发出的所有有向边删去，即把它的各个邻接顶点的入度减1。(3) 将新的id为0的顶点入栈。(4) 重复(2)和(3)，直到栈空为止。此时若输出的顶点数小于n，则输出“有回路”；否则拓扑排序正常结束。547.6.2AOV网拓扑排序拓扑排序算法的步骤为：547.6.2AOV网拓扑排序图7.25(a)～图7.25(h)给出了对图7.22所示AOV网使用上述算法进行拓扑排序邻接链表及栈的变化过程。557.6.2AOV网拓扑排序图7.25(a)～图7.25(7.6.2AOV网拓扑排序567.6.2AOV网拓扑排序567.7图的应用【例7.1】编程实现Prim算法。参见教材P162【例7.2】编程实现Dijkstra算法。参见教材P164577.7图的应用【例7.1】编程实现Prim算法。5本章小结(1) 图是一种非线性数据结构，图中元素存在多对多的关系，因此它的应用更加广泛，可以使用邻接矩阵和邻接链表两种存储方式来表示图中数据元素间的关系。(2) 图的遍历算法是图的基本算法，使用该算法，可以判断图的连通性及求图的连通分量。另外注意体会图的遍历与二叉树的遍历的联系：图的深度优先搜索类似于二叉树的先序遍历，图的广度优先搜索类似于二叉树的层次遍历。(3) 图有很多方面的具体应用，包括求最小生成树、求最短路径以及拓扑排序。求最小生成树可以使用Prim和Kruskal算法；求单源最短路径可以使用Dijsktra算法；求每对顶点间的最短路径可以使用Floyed算法；拓扑排序是在无环路有向图中进行的，通过拓扑排序可以判断有向图中是否存在环路，另外在求拓扑序列时注意拓扑序列可以不唯一。58本章小结(1) 图是一种非线性数据结构，图中元素存在多习题一、填空题参见教材P166二、选择题三、判断题四、应用题五、算法设计题59习题一、填空题59数据结构第7章课件第7章图学习目标与要求：了解图的定义和相关术语。熟练掌握图的邻接矩阵和邻接链表表示。熟练掌握图的两种遍历方式：深度优先搜索和广度优先搜索。熟练掌握求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。熟练掌握求单源最短路径的迪杰斯特拉算法，了解求每对顶点间最短路径的弗洛伊德算法。熟练掌握求拓扑序列的方法。61第7章图学习目标与要求：2图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。7.1图的定义和术语62图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，图是由非空的顶点集合和一个描述顶点之间关系—边的有限集合组成的一种数据结构。可以用二元组定义为：

G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。7.1图的定义和术语63图是由非空的顶点集合和一个描述顶点之间关系—边的有限集合组成V1V3V2V4V5

G1=（V1，E1）V1＝{v1,v2,v3,v4,v5}；E1＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称为边。7.1图的定义和术语64V1V3V2V4V5G1=（V1，E1）7.1图的定义V1V3V2V4G2=(V2,E2)V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}<vi,vj>表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。7.1图的定义和术语65V1V3V2V4G2=(V2,E2)7.1图的定义和术语假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶点到自身的边或者弧，即如果<vi,vj>,则vi≠vj。对于无向图，边数e的取值范围为0~n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图或无向完全图。对于有向图，弧度e的取值范围是0~n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。具有e<nlogn条弧或者边的图称为稀疏图。具有e>nlogn条弧或者边的图称为稠密图。7.1图的定义和术语66假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶7.1.2图的基本术语1．邻接点在无向图G=(V,E)中，如果存在边（vi,vj）∈E，则称vi和vj互为邻接点，即vi和vj相互邻接。边（vi,vj）依附于顶点vi和vj，或者称边（vi,vj）与顶点相互关联在有向图G=(V,E)中，如果存在弧<vi,vj>∈E，则称vi邻接到vj。弧<vi,vj>与顶点vi和vj相互关联。

677.1.2图的基本术语1．邻接点7.1.2图的基本术语2．顶点的度在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD(v)。在有向图中：(a)一个顶点拥有的弧头的数目，称为该顶点的入度，

记为ID(v)；(b)一个顶点拥有的弧尾的数目，称为该顶点的出度，

记为OD(v)；(c)一个顶点度等于顶点的入度+出度，

即：TD(v)=ID(v)＋OD(v)。

687.1.2图的基本术语2．顶点的度在图7-1的G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图7-2的G2中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2图7-1无向图G1图7-2有向图G2V1V3V2V4V5V1V3V2V47.1.2图的基本术语69在图7-1的G1中有：图7-1无向图G1图7-2有向图G7.1.2图的基本术语2．顶点的度假设顶点的个数为n，边数或弧数为e，顶点vi的度记作TD(vi),则顶点的度与弧度或者边数满足关系：

707.1.2图的基本术语2．顶点的度7.1.2图的基本术语3．路径在图中，从顶点vi出发经过一系列的顶点序列到达顶点vj称为从顶点vi到vj的路径。路径的长度是路径上弧或者边的数目。在路径中，如果第一个顶点与最后一个顶点相同，则这样的路径称为回路或者环。

717.1.2图的基本术语3．路径7.1.2图的基本术语3．路径在路径所经过的顶点序列中，如果顶点不重复出现，则称这样的路径为简单路径。在回路中，除了第一个顶点和最后一个顶点外，如果其他顶点不重复出现，则称这样的回路为简单回路或者简单环。

727.1.2图的基本术语3．路径4．子图对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。V1V3V2V1V3V2V4V5图7-3图G1和G2的两个子图示意V1V3V2V4V5V1V3V2V47.1.2图的基本术语734．子图V1V3V2V1V3V2V4V5图7-7.1.2图的基本术语5．连通图和强连通图在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图。否则，将其中的极大连通子图称为连通分量。

(a)无向图G3(b)G3的两个连通分量图7-4无向图及连通分量示意BCEFADIHGBCEADIFHG747.1.2图的基本术语5．连通图和强连通图5．连通图和强连通图在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图。否则，将其中的极大连通子图称为强连通分量。V1V3V2V4图7-5有向图G2的两个强连通分量示意有向图G2V1V3V2V4有向图G2的两个连通分量7.1.2图的基本术语755．连通图和强连通图V1V3V2V4图7-5有向图G2的6．生成树在含有n个顶点的图G中，如果G是包含n个顶点的极小连通子图，该子图只有n-1条边，这样的图称为连通图的生成树。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵包含n个顶点的生成树仅有n-1条边，如果少于n-1条边，则改图是非连通的。7.1.2图的基本术语766．生成树7.1.2图的基本术语176．生成树图7-6为图7-4中无向图G3的生成树。图7-6无向图G3生成树示意图BCEADI7.1.2图的基本术语BCEADI776．生成树图7-6无向图G3生成树示意图BCEADI7.7．网如果在图的边或者弧上增加具有一定意义的数，这些数称为权，权通常表示一个顶点到另一个顶点的距离或者花费，带有权的图称为网。一个网如图所示。图7-7网的示意图BCADE496141277.1.2图的基本术语787．网图7-7网的示意图BCADE496141277.17.2图的存储结构由于图的结构比较复杂，具体采用什么存储方式，要依据具体的操作。从图的定义可知，无论采用什么存储方式，都要能够描述图的顶点信息和边或弧的信息。下面介绍两种常用的图的存储结构。797.2图的存储结构由于图的结构比较复杂，具体采用什么存储7.2.1邻接矩阵图的邻接矩阵表示也称为数组表示，图的邻接矩阵就是利用C语言中的两个数组实现。其中一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。807.2.1邻接矩阵图的邻接矩阵表示也称为数组表示，图的邻7.2.1邻接矩阵设G=(V,E)是一个具有n个顶点的图(n≥1)，则G的邻接矩阵是表示顶点之间邻接关系的n阶方阵。该n阶方阵具有如下性质：817.2.1邻接矩阵设G=(V,E)是一个具有n个顶点的7.2.1邻接矩阵若G是网，则对应的n阶方阵具有如下性质：其中，wij表示边(vi,vj)或<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。827.2.1邻接矩阵若G是网，则对应的n阶方阵具有如下性质无向图用邻接矩阵表示法如图7-8所示；网用邻接矩阵表示法如图7-9所示。图7-9网的邻接矩阵表示图7-8一个无向图的邻接矩阵表示83无向图用邻接矩阵表示法如图7-8所示；网用邻接矩阵表示法如图

图的邻接矩阵具有以下性质：（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。（3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。7.2.1邻接矩阵84图的邻接矩阵具有以下性质：7.2.1邻接矩阵257.2.2邻接链表邻接表是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，该方法将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。857.2.2邻接链表邻接表是图的一种顺序存储与链式存储结合在邻接表表示中有两种结点结构，如图7-10所示。顶点域边表头指针邻接点域指针域vertexlinkadjvexnext顶点表边表图7-10邻接表表示的结点结构adjvexdatanext邻接点域指针域边上信息网的边表结构7.2.2邻接链表86在邻接表表示中有两种结点结构，如图7-10所示。vertex7.2.2邻接链表图7-11给出无向图对应的邻接表表示。

图7-11a图的邻接表表示877.2.2邻接链表图7-11给出无向图对应的邻接表表示。7.2.2邻接链表图7-11给出无向图对应的邻接表表示。

图7-11b图的邻接表表示887.2.2邻接链表图7-11给出无向图对应的邻接表表示。7.2.2邻接链表邻接链表存储图具有如下特点：(1)无向图中，第i个链表中的表结点数是顶点vi的度；有向图中，第i个链表中的表结点数是顶点vi的出度。(2)若无向图有n个顶点、e条边，则邻接链表需n个存储单元和2e个表结点。有向图存储n个顶点e条边，需要n个存储单元和e个表结点。对于边很少的图，用邻接链表比用邻接矩阵要节省存储单元。(3)在邻接链表中，要确定两个顶点vi和vj之间是否有边或弧相连，需要遍历第i个或第j个单链表，不像邻接矩阵那样能方便地对顶点进行随机访问。897.2.2邻接链表邻接链表存储图具有如下特点：307.3图的遍历图的遍历是对具有图状结构的数据线性化的过程。从图中任一顶点出发，访问输出图中各个顶点，并且使每个顶点仅被访问一次，这样得到顶点的一个线性序列，这一过程叫做图的遍历。图的遍历是个很重要的算法，图的连通性和拓扑排序等算法都是以图的遍历算法为基础的。下面分别介绍图的两种遍历方法：深度优先搜索和广度优先搜索，这两种方法既适用于无向图也适用于有向图。907.3图的遍历图的遍历是对具有图状结构的数据线性化7.3.1深度优先搜索深度优先搜索(DepthFirstSearch，DFS)遍历类似于二叉树的先序遍历，其基本思想是：初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将其标记为已访问，然后任选一个与v邻接且未被访问的顶点w访问输出并标记，再从与w邻接且未被访问的顶点z出发，进行深度优先搜索，重复这一过程，若到达某顶点不存在未被访问过的邻接顶点时，则一直退回到最近被访问过的且存在未被访问过邻接顶点的那个顶点再进行深度优先搜索，直至所有与v有路径相通的顶点都被访问到，若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做深度优先搜索917.3.1深度优先搜索深度优先搜索(DepthFirs7.3.1深度优先搜索对于图7-12所示的有向图其对应的邻接链表如图7-13所示得到的线性序列为1,2,4,3,5,7,6927.3.1深度优先搜索对于图7-12所示的有向图其对应的7.3.1深度优先搜索深度优先生成树或森林：由图中的全部顶点和深度优先搜索所经过的边即构成了深度优先生成树或森林。对图7.12所示有向图进行深度优先搜索得到的生成森林如图7.14所示。937.3.1深度优先搜索深度优先生成树或森林：由图中的全部7.3.2广度优先搜索广度优先搜索(BreadthFirstSearch，BFS)类似于二叉树的层次遍历。其基本思想是：初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将该顶点标记为已访问，然后依次访问输出与v邻接的未被访问的所有顶点，并标记为已访问，再分别从这些邻接点出发进行广度优先搜索，直至图中所有已被访问的顶点的邻接顶点都被访问到。若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做广度优先搜索。947.3.2广度优先搜索广度优先搜索(BreadthFi7.3.2广度优先搜索下面仍以图7.12所示有向图为例，说明广度优先搜索的过程，其存储结构为图7.13所示的邻接链表。得到的线性序列为1,2,4,3,5,7,6957.3.2广度优先搜索下面仍以图7.12所示有向图为例，7.3.2广度优先搜索对图7.12所示有向图进行广度优先搜索得到的生成森林如图7.15所示。967.3.2广度优先搜索对图7.12所示有向图进行广度优先V1V5V2V4V8V3V6V7v1→v2→v4→v8→v5→v3→v6→v7v1→v2→v3→v4→v5→v6→v7→v897V1V5V2V4V8V3V6V7v1→v2→v4→7.4最小生成树最小生成树就是指在一个连通网的所有生成树中，所有边的代价之和最小的那棵生成树。代价在网中用权值表示，一个生成树的代价就是生成树各边的代价之和。最小生成树有重要的研究意义，例如，要在n各城市建立一个交通图，就是要在n(n-1)/2条线路中选择n-1条代价最小的线路，在这里可以将各个城市看成图的顶点，城市的线路看成边。987.4最小生成树最小生成树就是指在一个连通网的所有生成树7.4最小生成树1．普里姆算法2．克鲁斯卡尔算法997.4最小生成树1．普里姆算法407.4.1普里姆(Prim)算法基本思想：假设G＝(V,E)是连通网，T＝(U,TE)为欲构造的最小生成树。(1)初始时令U={1}(即构造最小生成树时，从顶点1出发)，TE=Ф。(2)从所有u∈U，v∈V-U的边中，选取具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合TE中。(3)重复(2)，直到U＝V为止。1007.4.1普里姆(Prim)算法基本思想：假设G＝(V,图7-16Prim算法构造最小生成树的过程示意图

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515666668888812121214145101图7-16Prim算法构造最小生成树的过程示意图AE7.4.2克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法构造最小生成树的基本思想是：假设G＝(V,E)是连通网，T＝(U,TE)为欲构造的最小生成树。(1)初始时令U＝V，TE＝Φ，即最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。(2)把G的边按权值升序排列。(3)从中选取权值最小边(u,v)，若(u,v)连接T中两个不同的连通分量，则将(u,v)并入T中。(4)重复(3)直到T中只有一个连通分量为止。1027.4.2克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法图7-17Kruskal算法构造最小生成树的过程示意图

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515566668885121255145103图7-17Kruskal算法构造最小生成树的过程示意图7.5最短路径7.5.1单源最短路径单源最短路径是指在有向网中，以某个顶点v0作为源点，从v0出发，到其余各个顶点的最短路径。图7-18是个有向网，图7.19是其所对应的邻接矩阵cost，表7.1给出了对图7.18所示有向网，以1为源点，应用迪杰斯特拉算法求1到其余各顶点的最短路径的全过程及各数据结构的变化情况。1047.5最短路径7.5.1单源最短路径45表7-1图7-19有向网的邻接矩阵循环SWdist[2]dist[3]dist[4]dist[5]pre[2]pre[3]pre[4]pre[5]初始化{1}--10∞3010011111{1,2}210603010012112{1,2,4}41050309014143{1,2,4,3}31050306014134{1,2,3,4,5}5105030601413图7-18有向网示意图105表7-1图7-19有向网的邻接矩阵循环SWdist[27.5.2