数据结构与算法设计（第二版）课件 第7章 图

第七章图西安科技大学计算机学院张小艳数据结构与算法设计

七桥问题7.1图--基本概念图论。欧拉把每一块陆地看成一个点，连接两块陆地的桥用联线表示。把它转化成一个几何问题。七桥问题就转化成了是否能用一笔不重复地画出过此七条线的图形？142351234图--基本概念顶点边弧

图是一种网状数据结构，是由一个顶点的有穷非空集V(G)和一个弧或边的集合E(G)组成。通常记作二元组G

=

(V，E)其中G表示一个图，V是图G中顶点的集合，E是图G中的弧的集合。线性表可以没有元素，称之为空表；树中可以没有结点，称之为空树；图中不能没有顶点。图--图的定义图分为无向图和有向图。(a)无向图对于无向图G

=

(V，E)，如果(vi，vj)是一条边，则称顶点vi，vj互为邻接点。边(vi，vj)依附于顶点(vi，vj)。注意：(vi，vj)和(vj，vi)是一条边。无向边用于表示“对称关系”，城市中的双行道可以用无向边表示。

图(a)图可以表示为二元组

(V1，E)

V1={1,2,3,4,5}

E=

{（1,2）,(1,4),(2,3),(2,5),(3,5),(3,4)}图—图的分类14235(b)有向图

对于有向图G

=

(V，E)，如果

<vi，vj>

是一条弧，

vi称为弧尾或起始点，vj称为弧头(head)或终端点。

弧<vi，vj>

和

弧<vj，vi>

是两条不同的弧。有向边用于表示“非对称关系”。城市中的单行道用有向边表示。图(b)可以表示为G2

=(V2，A)

V2={1,2,3,4}

A={<1,2>,<1,3>,<3,4>,<4,1>,<4,2>}表示边的序偶用圆括号，表示弧的序偶用尖括号。图—图的分类1234

在一个无向图中，如果任意两个顶点都有一条直接边相邻接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

在一个有向图中，如果任意两个顶点之间都有方向互为相反的两条弧相邻接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。

若一个图接近完全图，称为稠密图；反之称为稀疏图。(a)无向完全图(b)有向完全图图—完全图加权边或加权弧。带权的图称为网或网络(network)。(a)无向网(b)有向网图—权值和网图--顶点的度顶点的度(degree)是指依附于某顶点v的边数，通常记为TD(v)。在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(v)；

顶点v的出度是指以顶点v为始点的弧的数目，记为OD(v)。TD(v) = ID(v) + OD(v)。顶点1的度是2，顶点2的度为3，顶点3的度为3，顶点4的度是2，顶点5的度为2，所有顶点的度加起来等12，图中有6条边。15432（a）无向图G1对于具有n个顶点、e条边的无向图：

顶点1的入度为 1，出度为 2；顶点2的入度为2，出度为0；顶点3的入度为1，出度为1；顶点4的入度为1，出度为2；所有顶点的入度之和与出度之和相等，就是边数。1432（b）有向图G2图--顶点的度图--路径和回路无向图G = (V，E)中：从顶点v到顶点v' 之间的路径(path)是一个顶点序列(v = vi1，vi2，…，vim = v')，其中，(vij，vij+1)是E中的一条边，1≤j＜m。路径上边或弧的数目称为路径长度。序列中顶点不重复出现的路径称为简单路径。V1V6V5V4V3V2132161189235712（a）无向网v1→v2→v3→v4v1→v6→v4路径长度分别为3和2，这两条路径都是简单路径。v1→v2→v6→v5→v4是从顶点v1到顶点v4的一条路径，路径长度为4。v5→v1是从顶点v5到顶点v1的一条路径，路径长度为1。这两条路径都是简单路径。V3V1V6V5V4V289613215712（b）有向网图--路径和回路无向网(a)中，v1→v2→v6→v5→v1是一条简单回路。有向网(b)中，v1→v2→v6→v5→v1也是一条简单回路。无向网(a)中的v1→v2→v6→v4→v2→v1路径中v2是重复的，就不是简单环了。V1V6V5V4V3V2132161189235712V3V1V6V5V4V289613215712（a）无向网（b）有向网路径中第一个顶点和最后一个顶点相同时称该路径为回路或者环(cycle)。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。图--路径和回路图--子图对于图G = (V，E)，存在G' = (V'，E')，若存在V' 是V的子集，E' 是E的子集，则称图G' 是G的一个子图。153214154321542无向图G1G1的子图图--无向图的连通性在无向图中，如果从顶点vi到顶点vj(i ≠ j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。15432无向图G1来看这里的无向图连通吗？MLADKJIHGFECB(a)无向图G3显然是不连通的，但是他包含三个部分，这三部分各自是联通的。这三部分可以称之为原图的连通分量。MLAJFCBDEKIHG(b)无向图G3的三个连通分量图--无向图的连通性无向图的连通分量要满足三个条件：

第一：是子图；

第二：要联通；

第三：含有极大顶点数及依附于这些顶点的所有的边。所以无向图的连通分量也称之为无向图的极大连通子图图--无向图的连通性图--有向图的连通性在有向图中，若图中任意一对顶点vi,vj，从vi到vj有路径，从vj到vi也有路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。图(a)的有向图有两个强连通分量，分别是{v1,v3,v4}和{v2}。14322143(a)有向图(b)连通分量图--生成树和生成森林一个连通图的生成树是一个极小的连通子图，它包含图中全部的顶点n，但只有足以让n个顶点连通的n-1条边，就是让N个顶点连通而无回路。MLAJFCBMLAJFCB所以，一个连通图的生成树不止一棵。图a不连通，有三个连通分量，就有三棵生成树。MLADKJIHGFECBMLAJFCBDEKIHG(a)无向图G3(c)无向图G3的三个生成树在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。图--生成树和生成森林如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。图中v0的入度为0，v1,v2,v3,v4,v5的入度均为1，所以是一棵有向树。V3V0V1V5V4V2入度为0的顶点其实就相当于树的根结点，其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树的弧。图--生成树和生成森林图--基本操作在图中任何一个顶点都可以被看成是第一个顶点；任意一个顶点的邻接点之间也不存在次序关系，所以无法将图中的顶点排列成一个唯一的线性序列。为了操作方便，需要将图中顶点按任意的顺序排列起来(这个序列是人为规定的)。所以需明确一个“顶点在图中位置”的概念。15432所谓顶点在图中位置，指的是该顶点在人为规定的排列中的位置(或序号)。同理，可对某个顶点的所有邻接点进行排序，在这个序列中，自然形成了第一个邻接点和第k个邻接点。若某个顶点的邻接点的个数大于k，则称第k+1个邻接点是第k个邻接点的下一个邻接点，最后一个邻接点的下一个邻接点为“空”。图--基本操作假设顶点的序号就是存储位置，按照序号从小到大排列某个顶点的邻接点。顶点1有两个邻接点，4是顶点1相对于2的下一个邻接点；顶点1相对于4的下一个邻接点为空。15432无向图G1可以称2是1的第一个邻接点；图--基本操作的基本操作：(1)顶点定位操作LocateVex(G，v)：在图G中找到顶点v，返回该顶点在图中的位置。(2)取顶点操作GetVextex(G，v)：在图G中找到顶点v，并返回顶点v的相关信息。(3)求第一个邻接点操作FirstAdjVex(G，v)：在图G中，返回v的第一个邻接点。若顶点v在G中没有邻接顶点，则返回“空”。15432无向图G1图--基本操作的基本操作：(1)顶点定位操作LocateVex(G，v)：在图G中找到顶点v，返回该顶点在图中的位置。(2)取顶点操作GetVextex(G，v)：在图G中找到顶点v，并返回顶点v的相关信息。(3)求第一个邻接点操作FirstAdjVex(G，v)：在图G中，返回v的第一个邻接点。若顶点v在G中没有邻接顶点，则返回“空”。(4)求下一个邻接点操作NextAdjVex(G，v，w)：在图G中，返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。15432无向图G1图--基本操作(5)插入顶点操作InsertVex(G，v)：在图G中增添新顶点v。(6)删除顶点操作DeleteVex(G，v)：在图G中，删除顶点v以及所有和顶点v相关联的边或弧。(7)插入弧操作InsertArc(G，v，w)：在图G中增添一条从顶点v到顶点w的边或弧。(8)删除弧操作DeleteArc(G，v，w)：在图G中删除一条从顶点v到顶点w的边或弧。(9)深度优先遍历图DFSTraverse(G，v)：在图G中，从顶点v出发按深度优先对图中每个结点访问一遍且仅一遍。(10)广度优先遍历图BFSTraverse(G，v)：在图G中，从顶点v出发按广度优先对图中每个结点访问一遍且仅一遍。图的这10个基本操作中，5-8操作涉及图的修改，一般情况下不常用到。7.2图的存储结构图是一种结构复杂的数据结构，任意两个顶点之间都有可能存在联系。MLADKJIHGFECB同学们，用顺序存储结构可以图吗？

链式存储结构可以吗？7.2图的存储结构

--邻接矩阵图是一种结构复杂的数据结构，任意两个顶点之间都有可能存在联系。一个图的信息包括两部分：即图中顶点的信息描述顶点之间的关系—边或者弧的信息。MLADKJIHGFECB图的信息包括两部分：顶点的信息、顶点之间的关系(边或者弧的信息)。分两部分存储：

用一维数组来存储顶点信息;

顶点与顶点之间的关系用二维数组存储--邻接矩阵。V0V2V3V4V1图的存储结构

--邻接矩阵假设图G = (V，E)，有n个顶点，即V = {v0，v1，…，vn-1}，则表示G中各顶点相邻关系为一个n × n的矩阵，将矩阵arcs称为邻接矩阵。图的存储结构

--邻接矩阵V0V2V3V4V1(c)邻接矩阵存储结构(b)顶点数组(a)无向图图的存储结构

--邻接矩阵在无向图中判断顶点vi到vj是否有边，只要判断arcs[i][j] 是否等于1；顶点vi的度就是第i行的元素之和；如果要找顶点vi的所有邻接点，查找第i行值为1的矩阵元，其所在列的序号即为其邻接点的序号。图的存储结构

--邻接矩阵判断顶点vi到vj是否有弧，只要判断arcs[i][j] 是否等于1。每个顶点的度分出度和入度，如果要找顶点vi的所有邻接点，查找第i行值为1的矩阵元，其所在列的序号即为其邻接点的序号。V0V2V3V1(c)邻接矩阵存储结构(b)顶点数组(a)无向图图的存储结构

--邻接矩阵若G是网，则邻接矩阵可定义为：若(vi，vj)或<vi，vj>是G的边或弧若i = j反之图的存储结构

--邻接矩阵图或网的邻接矩阵存储结构的C语言描述形式如下：1#defineINFINITY<整数中允许的最大值>2#defineMAXNODE<图中顶点的最大个数>3typedefcharVertexType;4typedefstruct5{intadj;

6……7}ArcType;/*定义表示无穷大整数*//*定义图中顶点的最大个数*//*假设顶点数据为字符型*//*图：两顶点相邻则adj=1，否则adj=0；网：两顶点相邻则adj=wij，i=j则adj=0；否则adj=∞*//*其他信息*/8typedefstruct9{VertexTypevertexes[MAXNODE];10ArcTypearcs[MAXNODE][MAXNODE];11intvexnum,arcnum;12}GraphType;/*顶点数组*//*邻接矩阵*//*图的顶点数和弧数*/图的存储结构

--邻接矩阵intadj[MAXNODE][MAXNODE]。在实际应用中，如果人们所关心的只是两顶点之间是否有边(或者弧)相连，而不考虑顶点本身的信息，在这种情况下，可以用编号作为图中各个顶点信息，图或网的邻接矩阵存储结构可以简单地表示为：图的存储结构

--邻接矩阵图的邻接矩阵存储具有4个特点：①用邻接矩阵存储图简单明了，极易在图中查找、插入、删除一条边或顶点，但要占用O(n2)个存储空间(n是顶点数)，无论图中实际含有多少条边。因此，对于稀疏图而言，不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。②无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上(或下)三角矩阵的元素即可。③对于无向图或网，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度TD(vi)。④对于有向图或网，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度OD(vi)(或入度ID(vi))。图的存储结构

--邻接矩阵1intCreateDN(GraphType*G) /*创建一个有向网*/2{3inti,j,k,weight;4VertexTypev1,v2;5scanf(″%d,%d″,&G->vexnum,&G->arcnum);/*输入图的顶点数和弧数*/6for(i=0;i<G->vexnum;i++)7for(j=0;j<G->vexnum;j++)8G->arcs[i][j].adj=INFINITY;/*初始化邻接矩阵*/9for(i=0;i<G->vexnum;i++)10scanf(″%c″,&G->vertexes[i]); /*输入图的顶点*/11for(k=0;k<G->arcnum;k++)12{13scanf(″%c,%c,%d″,&v1,&v2,&weight);/*输入弧的两个顶点及权值*/14i=LocateVex(G,v1);/*定位函数，时间复杂度为O(n)，*/15j=LocateVex(G,v2);/*定位函数，时间复杂度为O(n)，*/16G->arcs[i][j].adj=weight; /*弧上赋权值*/17}18return(OK);19}基本操作执行n2次循环次数为e次时间复杂度为：O(e × n)所以，此算法的时间复杂度为：O(n2 + e × n)。图的存储结构

--邻接矩阵v0v1v2v3v401234顶点数组：（a）无向图边矩阵：（c）邻接矩阵存储结构（b）顶点数组0123401234V0V1V2V3V4图的存储结构

--邻接表V50501005010000012345678∧∧∧12345689序号datafirstchild对图中的每一个结点的邻接点用一个单链表存储，所有顶点用一个数组存放。把这种顺序存储与链式存储相结合的存储方法称为邻接表。ABCDEFGHIBCDEFGHIA∧∧∧∧∧∧图的存储结构

--邻接表012345678∧∧∧12345689序号datafirstchild图的邻接表存储结构是顺序存储结构和链式存储结构完美结合。顺序存储结构和链式存储结构各有优缺点，在这里充分发挥了各自的优势，所以大家要博学多识，积累知识，掌握各种理论与方法，在具体应用中才能够将所学知识融会贯通。要善于运用事物或人本身所具有的长处。ABCDEFGHIBCDEFGHIA∧∧∧∧∧∧图的存储结构

--邻接表adjvexnext①图中的顶点用一个一维数组存储，每个数组元素包含两部分：

一部分用于存储顶点信息data，一部分用于存放指向该顶点的第一个邻接点的指针firstarc。②图中每个顶点vi的所有邻接点构成一个单链表。

若是无向图，该链表称为顶点vi的边表；

若是有向图，该链表称为顶点vi作为弧尾的出边表。firstarc如果边上有其他信息需要保存，可以增加域，比如是网，可以增加权值weght。adjvexweightnextdata图的存储结构

--邻接表01234^^^1302413datafirstarc02^^413adjvexnextv0v1v2v3v4对于有n个顶点、e条边的无向图而言，若采用邻接表作为存储结构，则需要n个表头结点和2e个表结点。v0v1v2v3v4图的存储结构

--邻接表在无向图的邻接表存储结构中，若要获得某结点的度，只需要查找这个顶点的边表结点的个数即可。若要判断顶点vi和vj是否存在边，需要在vi(或vj)的邻接点单链表中查找邻接点域adjvex是否存在结点vj(或vi)的下标j(或i)。若求顶点的所有邻接点，就是对此顶点的邻接点单链表进行遍历，得到的邻接点域adjvex域对应的顶点。图的存储结构

--邻接表有向图0123^123datafirstarc01adjvexnext^^^v0v1v2v3有向图采用邻接表存储结构类似无向图，但是要注意有向图中的弧是有方向的，以顶点为弧尾来存储弧。有向图邻接表v3v0v1v2图的存储结构

--邻接表有向图逆邻接表逆邻接表中，图中第i个顶点的入度等于第i条链表中边结点的个数。0123300datafirstarc2adjvexnext^^v0v1v2v33^^v3v0v1v2图的存储结构

--邻接表对于网，在边表结点上增加一个权值weight域，用于存放与边或弧相关的信息。当然如果边上有其他的信息需要保存，也可以增加域。adjvexweightnextv0v1v2v3v401234datafirstarcv0v1v2v3v4adjvexweightnext^^^^^1233022645116384032847152137通过无向网邻接表存储实例，我们可以看到边结点增加的存储权值域。图的存储结构

--邻接表#defineMAXNODE＜图中顶点的最大个数＞typedefstructarc {

intadjvex; intweight; structarc*next;}ArcType;typedefstruct{ElemTypedata; ArcType*firstarc; }VertexType; typedefstruct{VertexTypevertexes[MAXNODE];intvexnum,arcnum; }AdjList;/*边表结点*//*邻接点域，存储邻接点在表头结点表中的位置*//*权值域，用于存储边或弧相关的信息，非网图可以不需要*//*链域，指向下一邻接点*//*顶点信息*//*指向第一条依附该顶点的边或弧的指针*//*顶点表结点*//*图中顶点数和弧数*/图的存储结构

--邻接表

1#defineMAXNODE302intCreateUDN(AdjList*G)3{4inti,j,k;5intv1,v2;6intn,e;7ArcType*p,*q;8printf(″\n输入图中顶点的个数n和边数e：\n″);9scanf(″%d,%d″,&n,&e,);10G->vexnum=n;11G->arcnum=e;12printf(″\n输入顶点的信息：\n″);13for(k=0;k<n;k++)14{15scanf(″%d″,&(G->vertexes[k].data));16G->vertexes[k].firstarc=NULL;17}

/*创建一个无向图G*//*输入图中的顶点数和边数*/

/*输入n个顶点信息*/循环次数为n图的存储结构

--邻接表18printf(″\n输入图中各边:\n″)19for(k=0;k<e;k++)20{21scanf(″%d,%d″,&v1,&v2);22i=LocateVex(*G,v1);23j=LocateVex(*G,v2);24q=(ArcType*)malloc(sizeof(ArcType));25q->adjvex=j;26q->next=G->vertexes[i].firstarc;27G->vertexes[i].firstarc=q;28p=(ArcType*)malloc(sizeof(ArcType));29p->adjvex=i;30p->next=G->vertexes[j].firstarc;31G->vertexes[j].firstarc=p;32}33return(1);34}

/*依次读入e条边信息，建立边表*//*读入边（v1，v2）*//*查找v1的位置i*//*查找v2的位置i*//*申请结点q指向*//*邻接点赋值为j*//*在顶点数组的第i个顶点的边表中插入边结点*//*申请结点p指向*//*邻接点赋值为i*//*在顶点数组的第j个顶点的边表中插入边结点*/该算法时间复杂度为O(e × n)采用头插法建立单链表邻接矩阵和邻接表是两种最常用的图的存储结构，前者适合于图的静态存储，后者适合于图的动态存储。循环次数为e时间复杂度O(n)时间复杂度O(n)图的存储结构

--邻接表7-3图的深度优先遍历图的遍历，是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次，图的遍历有两种：图的深度优先遍历、广度优先遍历。图的遍历进行图的遍历时，需要为图设置一个访问标识数组:visited[n]，用于表示图中每个顶点是否被访问过。visited[1~n]=0(“假”)，表示顶点均未被访问；visited[i]=1(“真”)，表示顶点已被访问。V0V2V3V4V12376815设置访问标识数组记录结点是否被访问过。这种处理方式是为了让我们记住来时路。“记得来时路，继续向远方”不忘初心砥砺前行。深度优先遍历(depthfirstsearch)类似于树的先根遍历，是树先根遍历的推广。生成的树称为深度优先生成树。图的遍历

--深度优先遍历ABCGDHEFABDHECFG深度优先遍历的序列为：深度优先遍历图的算法：(1)访问结点v；(2)找到v的第一个邻接点w；(3)如果邻接点w存在且未被访问，则从w出发深度优先遍历图；否则，结束；(4)找顶点v关于w的下一个邻接点，转(3)。图的遍历

--深度优先遍历9voidDepthFirstSearch(GraphG,intv)10{intw;11visit(v); 12visited[v]=1; 13w=FirstAdjVertex(G,v); 14while(w!=-1) 15{16if(!visited[w])17DepthFirstSearch(G,w); 18w=NextAdjVertex(G,v,w); 19}20}/*深度遍历v所在的连通子图*//*访问顶点v*//*置访问标识数组相应分量值*//*找第一个邻接点*//*邻接点存在*//*递归调用DepthFirstSearch*//*找下一个邻接点*/图的遍历

--深度优先遍历深度优先遍历的序列在存储结构给定的情况下是唯一的，因为存储结构给定之后，顶点的存储位置及邻接点的排列顺序也给定了。对于非连通图，只要对图中所有的连通分量进行深度优先遍历。从一个顶点开始深度优先遍历结束之后，如果图中还有未被访问的顶点，就另选一个没有访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问过。所以图的遍历算法在从某一个顶点出发深度访问之前需要做一些预处理：1、访问标志数组初始化；2、找没有遍历的顶点。图的遍历

--深度优先遍历intvisited[MAXNUM];1voidTraveGraph(CraphG)2{

3intv;4for(v=0;v<G.vexnum;v++) 5visited[v]=0;6for(v=0;v<G.vexnum;v++)7if(!visited[v])DepthFirstSearch(G,v); 8}/*初始化访问标识数组*//*找没有被访问过的顶点，找到后进入深度优先*//*调用深度遍历算法*//*对图G进行深度优先搜索，Craph是图的一种存储结构，如邻接矩阵表示法或邻接表*//*访问标识数组*/图的遍历

--深度优先遍历一个连通图的生成树不唯一。（1）（2）（3）连通图图的遍历

--深度优先遍历对于非连通图，每个连通分量中的顶点集和深度优先遍历时走过的边一起构成若干棵深度优先遍历生成树，这些连通分量的生成树组成非连通图的深度优先遍历生成森林。第一次从顶点1出发，深度优先遍历的序列为:1-2-4-3-9；第二次从5出发，深度优先遍历的序列为:5-6-7；第三次从8出发，深度优先遍历的序列为:8-10。（1）（2）（3）图的遍历

--深度优先遍历7-3-2图的广度优先遍历图的遍历--广度优先遍历ACBEFGDHI

广度优先遍历实质上是从指定顶点出发，按照到该顶点的路径长度由短到长的顺序访问图中的所有顶点。遍历时需要设立访问标识数组visited[n]：

visited[i]=0，节点未被访问；

visited[i]=1，节点已被访问。在广度优先遍历中需要设置一个队列Queue来记录访问次序。广度优先遍历是对图进行遍历的另一种常用方法，它类似于树的层次遍历，是树的按层次遍历的推广，在遍历过程中需要用队列记录遍历过程中的顶点。图的遍历--广度优先遍历ACBEFGDHI出队列入队列ABCEFGHDIAABCDEFGHBCDEFGHII广度优先遍历过程：在对连通图进行广度优先遍历过程中，连通图的所有的顶点及广度优先遍历走过的边构成了一棵生成树，称为广度优先生成树。对于非连通图，每个连通分量中的顶点集和广度优先遍历时走过的边一起构成若干棵广度优先遍历生成树，这些连通分量的生成树组成非连通图的广度优先遍历生成森林。图的遍历--广度优先遍历ABCDEFGHIABCDEFGHI非连通图（1）（2）广度优先遍历算法描述如下：(1)设图G的初态是所有顶点均未访问，设置辅助队列Q，队列Q置空；(2)任选图中一个未被访问过的顶点v作为遍历起点；(3)访问v(将其访问标识置为已被访问，即visited[v] = 1)，并且将v入队列；(4)若队列Q不空，从队头取出一个顶点v；(5)查找v的所有未访问的邻接点vi并对其访问(将其访问标识置为已被访问，即visited[i] = 1)，并入队列，转(4)，直到队列Q为空；(6)若此时图中还有未被访问过的顶点，则转(2)；否则，遍历结束。图的遍历--广度优先遍历1intvisited[MAXNUM];

2voidBFSTraveGraph(GraphTypeG)3{4intv;5QQTypeQ;

6InitQueue(&Q);

7for(v=0;v<G.vexnum;v++)

8visited[v]=0;9for(v=0;v<G.vexnum;v++)10if(!visited[v])BreadthFirstSearch(G,v);

11}图的遍历--广度优先遍历/*访问标识数组*//*QQType为队列类型标识符*//*初始化队列*//*初始化访问标识数组*//*找没有被访问过的顶点，进行广度优先调用深度遍历算法*/12voidBreadthFirstSearch(GraphTypeg,intv0)13{intv,vj,w;14visit(v0);15visited[v0]=1;16EnterQueue(&Q,v0); 17while(!QueueEmpty(Q))

18{v=DeleteQueue(&Q); 19for(vj=0;vj<n;vj++)20if(!visited[vj]&&g.arcs[v][vj].adj==1)

21{visit(vj);22visited[vj]=1;23EnterQueue(&Q,vj)24}25}26}/*访问v0*//*访问标志修改为访问过*//*v0入队列*/图的遍历--广度优先遍历/*循环判断队列是否为空*//*队头元素出队*//*找V的所有邻接点*//*vj入队列*//*若邻接点存在且没有被访问过*/7-4-1普里姆算法一个带权网，这个网中v1～v6代表6个村镇，联线上的数字就是两个村镇架设通讯设施的耗费。v1v4v2v3v5v65615366425最小生成树

所谓最小成本，就是在这6个村镇之间找到5条边把6个村镇连起来，同时达到5条边上的权值之和最小。你找到的会是下面的一个无回路的联通网，这就是最小生成树.v1v4v2v3v5v615342最小生成树最小生成树:

一个无向连通网，它所有的生成树中必有一棵边的权值之和最小的生成树，我们称这棵树为最小代价生成树，简称最小生成树。求最小生成树的经典算法有两种：普里姆算法和克鲁斯卡尔算法。普里姆(Prim)算法构造最小生成树：

假定有连通网N = (V,E)，其中V为网中所有顶点的集合，E为网中所有带权边的集合。

①设TE为最小生成树中边的集合，初始化TE为 Φ，引入U集合，初始化U 集合只包含V中的一个顶点u0。

②在U集合到V-U集合的所有的边中选一条代价最小的边(u0,v0)。将边(u0,v0)并入集合TE，同时将顶点v0并入U集合。

③重复②，直到U = V为止。 此时TE中必含有n-1条边。 顶点集V、边集为TE的生成树T = (V,TE)，就是N的最小生成树。

普里姆(Prim)算法也可称为“加点法”。最小生成树

--普里姆(Prim)算法v1v4v2v3v5v6142533425561665v1v2v3v4v5v6v4U={v1}

，V-U集合= {v2,v3,v4,v5,v6}。U={v1,v3}

，V-U集合= {v2,v4,v5,v6}。U={v1,v3,v6}

，V-U集合= {v2,v4,v5}。U={v1,v3,v6,v4}

，V-U集合= {v2,v5}。U={v1,v3,v6,v4,v2}

，V-U集合= {v5}。U={v1,v3,v6,v4,v2,v5}

，V-U集合= {}。U = V，找到最小生成树最小生成树

--普里姆(Prim)算法普里姆(Prim)算法实现需要设置一个辅助数组closedge[]，定义为一个结构体：typedefcharVertexType;struct{VertexTypevex;/*U中的顶点*/intlowcost;/*min({cost(vex,v)|vex∈U})*/}closedge[MAXNUM];/*求最小生成树时的辅助数组*/closedge[]用来记录从U集合到V-U集合具有最小代价的边。对每个V-U集合中的顶点在辅助数组中存在一个分量closedge[v]，它包括两个域：U中的顶点域vex和边(u,v)上的耗费lowcost，（v,u）是当前权值最小的边。

closedge[v].lowcost

=

min({cost(u,v)|u∈U}）最小生成树

--普里姆(Prim)算法

以邻接矩阵作为图的存储方式来展示普里姆(Prim)算法的实现。从顶点u出发，按普里姆算法构造连通网G的最小生成树，并输出生成树的每条边。1MiniTreePrim(GraphTypeG,VertexTypeu)2{intk,i,j,e,k0,mincost;3charu0,v0;4k=LocateVex(G，u); 5closedge[k].lowcost=0;6for(i=0;i<G.vexnum;i++)7if(i!=k)8{closedge[i].vex=u;9closedge[i].lowcost=G.arcs[k][i].adj;10}11for(e=1;e<=G.vexnum-1;e++)

12{mincost=32767;

13k0=0;/*确定u在图G中的位置*//*初始化U = {u}*//*对V-U中的顶点i，初始化closedge[i]*//*依次找到n-1条边*/循环次数为n/*mincost为一个比任何边的权都要大的数*/最小生成树

--普里姆(Prim)算法14for(j=0;j<G.vexnum;j++) 15if(closedge[j].lowcost!=0&&closedge[j].lowcost<mincost)16{17k0=j; 18mincost=closedge[j].lowcost;19}20u0=closedge[k0].vex;21v0=G.vertexes[k0];22printf(″(%c,%c)\n″,u0,v0);23closedge[k0].lowcost=0; 24for(i=0;i<G.vexnum;i++)25if(G.arcs[k0][i].adj<closedge[i].lowcost)26{closedge[i].lowcost=G.arcs[k0][i].adj;27closedge[i].vex=v0;28}29}30}算法的时间复杂度为O(n2)，与网中的边数无关，适合于求边稠密的网的最小生成树。/*选择当前代价最小的边*/循环次数为n/*输出生成树的当前最小边*//*将顶点v0并入U集合*//*在顶点v0并入U后，更新closedge[i]*//*closedge[k0]中存有当前代价最小的边*/最小生成树

--普里姆(Prim)算法7-4-2克鲁斯卡尔算法克鲁斯卡尔算法的基本思想是：(1)初始化最小生成树的初始状态为：

只有n个顶点而无边的非连通图T=(V,Φ)；

图中每个顶点自成一个连通分量。(2)在边集E中选择代价最小的边，如果这个边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则舍去此边而选择下一条代价最小的边。(3)重复(2)，直到T中所有的顶点都在同一连通分量上为止。最小生成树

--克鲁斯卡尔算法克鲁斯卡尔算法逐步增加生成树的边，与普里姆算法相比，可称为“加边法”。

对于图中的连通网，设N = {V,{E}}，最小生成树T的初态中边集为空，TE=NULL，每个顶点自成一个联通网。1236541236543151561816361114362011616最小生成树

--克鲁斯卡尔算法克鲁斯卡尔算法是不断地扫描边集合，至多对e条边各扫描一次，如果用堆来存放边，则每次选择最小边仅需O(lb e)的时间代价。可以证明，克鲁斯卡尔算法的时间复杂度为O(elb e)，它适合于求边稀疏的网的最小生成树。最小生成树

--克鲁斯卡尔算法在解决问题时不断刻苦钻研，获取最优的解决方案，不能满足于在找到答案。7-5-1迪杰斯特拉算法最短路径

在实际生活中经常遇到这样的问题，从A城市到B城市有若干条路,需要选择一条距离最短的路。假如要用计算机解决这一问题，可以采用网描述交通网络。

在图中顶点表示城市，边代表城市之间的通路，边上的权代表通路的距离。这样，上述问题就变成了在图中寻找一条从顶点A到顶点B所经过的路径上权值累加和最小的路径。我们把这样一类问题称为最短路径问题。v0v1v2v3v4v5v620301051291081518最短路径有两种最短路径问题：①求某一源点到其余各顶点的最短路径；②求任意两顶点间的最短路径。从源点到终点的路径可能存在三种情况：①没有路径；②只有一条路径，则该路径即为最短路径；③存在多条路径，则其中必存在一条最短路径。v0v1v2v3v4v5v6

有向网G = (V，E),求源点v0到其他各顶点的最短路径。从源点v0到v5没有路径从源点v0到v1只有一条路径(v0，v1)从源点v0到v4有两条路径，其中以长度为15的路径(v0，v2，v4)为最短路径20301051291081518最短路径--迪杰斯特拉最短路径--迪杰斯特拉

迪杰斯特拉(Dijkstra)提出了一种按路径长度递增的次序求从源点到各终点的最短路径的算法。这个算法就称为迪杰斯特拉算法

有向网G = (V，E)，用邻接矩阵存储02030

1009

05

0

01215

010018

v0v1v2v3v4v5v620301051291081518

终点v1v2v3v4v6v5从v0到各终点的最短路径及最短路径长度求解过程i-1i-2i-3i-4i-5i-6(v0，v1)20(v0，v2)10(v0，v3)30

(v0，v1)20(v0，v3)30(v0,v2

,

v4)15

(v0，v1)20(v0,v2,v4,v3)27(v0,v2,v4,v6)30

(v0,v2,v4,v3)27(v0,v1,v6)29

(v0,v1,v6)29

v0v1v2v3v4v5v602030

1009

05

0

01215

010018

20301051291081518最短路径--迪杰斯特拉算法实现过程中需要记录依次找到的最短路径建立一个集合S，初始时该集合只有源点v0，然后逐步将已求得最短路径的顶点加入到集合中。

为了实现算法，需要引进辅助向量dist[]，它的每个分量dist[i]表示已经找到的从开始点v0到终点vi的当前最短路径的长度。它的初态为：如果从v0到vi有弧，则dist[i]为弧的权值；否则dist[i]

为∞。最短路径--迪杰斯特拉v0v1v2v3v4v5v62030105129108151802030

1009

05

0

01215

010018

从dist[]向量中选择一个长度最小的路径dist[j]此路径为(v0，vj)。设下一条最短路径的终点是vk，这条路径可能是弧(v0，vk)；可能是：v0到vj，vj到vk，路径长度是从v0到vk的弧上的权值之和。最短路径--迪杰斯特拉v0v1v2v3v4v5v62030105129108151802030

1009

05

0

01215

010018

dist[i](v0，v2)就是从v0到v2的最短路径，dist[2]记录最短路径长度10这里我们选择了(v0，v2)比如：从v0到v4初始值为无穷大，但是v0经过v2再到v4有路径，而且路径长度是最短的，从v0到v4的路径为：v0到v2，v2到v4，路径长度为15。设置集合S：用于存放已经找到的从v0出发的最短路径的终点集合。用邻接矩阵g表示网(1)S集合初态只包含一个顶点{v0}；辅助向量dist[i]

=

g.arcs[0][i]。(2)在向量dist中选择路径长度最短的一条路径，v0到vk的路径，将vk并入S集合。(3)更新向量dist，使得向量dist中始终记录从v0出发到集合V-S上任意一个顶点vi的最短路径。判断V0是否可借助S中的顶点到达集合V-S上任一顶点vi？如果可达，且路径长度比原来的短，就修改v0到vi的路径，修改dist[i]，否则保持原来的路径及原来的dist[i].(4)重复(2)、(3)步n-1次，逐个求出v0到图其他每个顶点的最短路径最短路径--迪杰斯特拉n个顶点，自然要有循环做n次循环n次总的时间复杂度是O(n2)。循环n-1次循环n次

引入向量P、D、final;

P[v]记录有向网G的v0顶点到其余顶点v的最短路径;若P[v][w] 为1，则w是从v0到v当前求得最短路径上的顶点；D[v] 记录有向网G的v0顶点到其余顶点v的最短路径长度；final[v] 为1，当且仅当v∈S，即已经求得从v0到v的最短路径。1voidDijkstra(GraphTypeG,intv0,PathMatrix*P,ShortPathTable*D)2{/*常量INFINITY为边上权值可能的最大值*/3for(v=0;v<G.vexnum;++v) /*初始化*/4{5fianl[v]=0; /*v顶点属于V-S集*/6D[v]=G.arcs[v0][v];/*初始化源点到其他顶点的最短路径*/7P[v]=0; /*设空路径*/8if(D[v]<INFINITY) /*初始化最短路径上的点*/9P[v]=1;10}11D[v0]=0;final[v0]=1;/*初始化，v0顶点属于S集*/引入向量P、D、final;

P[v]记录有向网G的v0顶点到其余顶点v的最短路径若P[v][w] 为1，则w是从v0到v当前求得最短路径上的顶点；D[v] 记录有向网G的v0顶点到其余顶点v的最短路径长度；final[v] 为1，当且仅当v∈S，即已经求得从v0到v的最短路径。12for(i=1;i<G.vexnum;++i)/*其余G.vexnum-1个顶点*/13{/*开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集*/14min=INFINITY;/*min为当前所知离v0顶点的最近距离*/15for(w=0;w<G.vexnum;++w)/*在v0到其他顶点vi中查找最短路径*/16if(!final[w]) /*w顶点在V-S中*/17if(D[w]<min)18{v=w;19min=D[w];20}21final[v]=1 /*离v0顶点最近的v加入S集合*/22for(w=0;w>G.vexnum;++w)/*更新当前最短路径*/if(!final[w]&&(min+G.arcs[v][w]<D[w]))/*修改D[w]和P[w]*24{D[w]=min+G.arcs[v][w];25P[w]=P[v];P[w][v]=1;/*P[w]=P[v]+P[w]*/26}}}/*Dijkstra*/算法的运行时间分析：设图中有n个顶点，e条边。语句3～语句10：for循环的次数为n，时间复杂度是O(n)。语句12～语句27：for循环共进行n-1次，其中包含两个并列的循环，

语句15～语句20是查找最短路径，循环n次；

语句22～语句26是更新当前最短路径，循环n次。所以总的时间复杂度是O(n2)。7-5-2弗洛伊德算法

对于一个有向网，求每对顶点之间的最短路径，显然可调用Dijkstra算法。

具体方法是：每次以不同的顶点为源点，用Dijkstra算法求出从该顶点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每个顶点到其余顶点的最短路径。

最短路径--弗洛伊德算法02030

1009

05

0

01215

010018

v0v1v2v3v4v5v620301051291081518这种方法的时间复杂度为O(n3)。574设用邻接矩阵表示图g最短路径--弗洛伊德算法(1)求图g中任意一对顶点vi、vj间的最短路径。将vi到vj的最短路径长度初始化为g.arcs[i][j]，这个不一定是vi到vj的最短的路径，需要做n次试探。02030

1009

05

0

01215

010018

v0v1v2v3v4v5v6203010512910815185274(2)在vi、vj间加入顶点v0，判别(vi,v0,vj)是否存在(即判别弧(vi,v0)和(v0,vj)是否存在)。如果存在，比较(vi,v0,vj)和(vi,vj)的路径长度，取其中较短的路径作为vi到vj的且中间顶点号不大于0的最短路径。设用邻接矩阵表示图g最短路径--弗洛伊德算法02030

1009

05

0

01215

010018

v0v1v2v3v4v5v6203010512910815185274(3)再将顶点v1加入vi、vj间，若(vi,…,v1)和(v1,…,vj)分别是中间顶点序号不大于0的最短路径，这两条路径在上一步中已求出。将(vi,…,v1,…,vj)与上一步已求出的且vi到vj中间顶点号不大于0的最短路径比较，取其中较短的路径作为vi到vj的且中间顶点号不大于1的最短路径。(4)继续在vi、vj间加入顶点v2、v3v4…..，依次类推，……经过n次比较和修正，在第n步，将求得vi到vj的且中间顶点号不大于n的最短路径，这必是从vi到vj的最短路径。弗罗伊德算法

路径可直接从邻接矩阵获得

vivjcost[i，j]v1中间顶点序号不大于1的最短路径

v2中间顶点序号不大于2的最短路径

…Vn中间顶点序号不大于n的最短路径

图g中所有顶点偶对<vi，vj>间的最短路径长度对应一个n阶方阵D。依次在<vi，vj>间增加v1,v2,v3……过程中，方阵D中的值不断变化，对应一个n阶方阵序列。定义一个n阶方阵序列：

D(-1)，D(0)，D(1)，…，D(k)，…，D(n-1);其中：D(-1)用邻接矩阵初始化，D(-1)[i][j] = G.arcs[i][j]D(k)[i][j] = Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}，0≤k≤n-1D(1)[i][j] 是从vi到vj的中间顶点的序号不大于1的最短路径的长度；D(k)[i][j] 是从vi到vj的中间顶点的序号不大于k的最短路径的长度；D(n-1)[i][j] 就是从vi到vj的最短路径的长度。

最短路径--弗洛伊德算法

为了能记录路径，我们定义一个方阵P，记录所有顶点偶对<vi，vj>间的最短路径，用它代表对应顶点的最短路径的前驱矩阵。方阵P随着D的变化而变化，所以，P也对应一个方阵序列：P(-1)，P(0)，P(1)，…，P(k)，…，P(n-1)。P(-1)是初始设置,P(-1)[i][j] = jP(1)[i][j]是从vi到vj的中间顶点的序号不大于1的最短路径；P(k)[i][j] 是从vi到vj的中间顶点的个数不大于k的最短路径；P(n-1)[i][j] 就是从vi到vj的最短路径。

最短路径--弗洛伊德算法

typedefintPathMatrix[MAXVEX][MAXVEX]typedefintDistancMatrix[MAXVEX][MAXVEX]1voidFloyd(GgraphG,PathMatrix*P[],DistancMatrix*D)2{3for(v=0;v<G.vexnum;++v)4for(w=0;w<G.vexnum;++w)5{6D[v][w]=G.arcs[v][w]; 7P[v][w]=w;8}9for(u=0;u<G.vexnum;++u)10for(v=0;v<G.vexnum;++v)11for(w=0;w<G.vexnum;++w)12if(D[v][u]+D[u][w]<D[v][w]) 13{14D[v][w]=D[v][u]+D[u][w];15P[v][w]=P[v][u];16}17}/*初始化DP;*//*先定义两个矩阵DP*//*G：带权有向图，P[v][w]为v到w的当前最短路径，D[v][w]记录路径长度*/最短路径--弗洛伊德算法算法的时间复杂度为O(n3)Dijkstra、RobertFloyd这两位科学家在计算机领域成果斐然，是我们学习的榜样。

通过树立榜样，学习先进典型人物，鼓励学生不懈努力、改革创新，思考计算机专业的新的方法和理论，助力科技强国，并注重新技术的应用转化，提高生产生活效率。7.6有向无环图及其应用一个无环的有向图称做有向无环图(directedacyclinegraph)，简称DAG图。DAG图是一类较有向树更一般的特殊有向图。有向树DAG有向示意图对于无向图来说，若深度优先遍历过程中遇到回边(即指向已访问过的顶点的边)，则必定存在环；检查一个有向图是否存在环要比无向图复杂，因为这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，在深度优先遍历结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图必定存在包含顶点v和u的环有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程(project)