图(Graph)是一种复杂的非线性结构在人工智能

1、第7章 图概述v图(Graph)是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。 本章先介绍图的概念，再介绍图的存储方法及有关图的算法。7.1 图的概念v图的二元组定义图的二元组定义v有向图和无向图有向图和无向图图的二元组定义图的二元组定义v图G由两个集合V和E组成，记为： G=(V，E)其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。 通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。1有向图有向图v若图G中的每条边都是有方向的，则称G为有向图(Di

2、graph)。（1）有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。 【例】表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，和是两条不同的有向边。（2）有向图的表示下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为： V(G1)=v1，v2，v3 E(G1)=，2无向图无向图v 若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。（1）无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括

3、号表示。示例v【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为： V(G2)=v1，v2，v3，v4 E(G2)=(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)无向图示例v V(G3)=v1，v2，v3，v4，v5，v6，v7 E(G3)=(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)注意：v 在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或是E(G)中的一条边，则要求v1v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。完全图v无向图的完全图：每二

4、个顶点之间都有边相连：边数=n(n-1)/2，n为顶点个数v有向图的完全图：边数=n(n-1)，n是顶点个数。3图图G的顶点数的顶点数n和边数和边数e的关系的关系v（1）若G是无向图，则0en(n-1)/2 恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)（2）若G是有向图，则0en(n-1)。 恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。图的边和顶点的关系图的边和顶点的关系1.无向边和顶点关系无向边和顶点关系v 若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，

5、或称vi和vj相邻接；并称(vi,vj)依附或关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。【例】下图G2中： 与顶点v1相邻接的顶点是v2，v3和v4 关联于顶点v2的边是(v1，v2)，(v2，v3)和(v2，v4)2有向边和顶点关系有向边和顶点关系v 若是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边关联于vi和vj或称与顶点vi和vj相关联【例】在下图G1中，关联于顶点v2的弧是，和。vn个顶点的完全有向图，它的入度为多少？出度为多少？n(n-1)3顶点的度顶点的度(Degree)v（1）无向图中顶点v的度(Degree) 无向

6、图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。【例】上图G2中顶点v1的度为3有向图的入度和出度v（2）有向图顶点v的入度(InDegree) 有向图中，以顶点v为终点的边的数目称为v的入度(Indegree)，记为ID(v)。【例】上图G1中顶点v2的人度为l（3）有向图顶点v的出度(Outdegree) 有向图中，以顶点v为始点的边的数目，称为v的出度(Outdegree)，记为OD(v)【例】上图G1中顶点v2的出度为2注意：v 有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。e与n之间的关系v无论有向图还是无向图，顶点数n、

7、边数e和度数之间有如下关系：niivDe1)(21子图子图v设G=(V，E)是一个图，若V是V的子集，E是E的子集，且E中的边所关联的顶点均在V中，则G=(V，E)也是一个图，并称其为G的子图(Subgraph)。有向图的子图例子无向图的子图例子注意：v 设V=v1，v2，v3，E=(vl，v2)，(v2，v4)，显然，V属于V(G2)，E属于E(G2)，但因为E中序偶对(v2，v4)所关联的顶点v4不在V中，所以(V，E)不是图，也就不可能是G2的子图。路径v路径路径(Path)1无向图的路径无向图的路径在无向图G中，若存在一个顶点序列vp,vi1，vi2,，vim，vq，使得(vp，vi1

8、)，(vi1，vi2)，(vim，vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path)。v简单路径： v2有向图的路径有向图的路径 在有向图G中，路径也是有向的,它由E(G)中的有向边，组成。3路径长度路径长度 路径长度定义为该路径上边的数目。5简单回路或简单环简单回路或简单环(Cycle)v 起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。【例】图G2中，顶点序列v1，v2，v4，v1是一个长度为3的简单环【例】有向图G1中，顶点序列v1，v2，v1是一长度为2的有向简单环。6有根图和图的根有根图和图的根v 在一个有向图中，若存在一个顶点v，从该顶点有路

9、径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。 连通图和连通分量连通图和连通分量1顶点间的连通性顶点间的连通性v在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。2连通图连通图v若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph)。【例】图G2，和G3是连通图。3连通分量连通分量 无向图G的极大连通子图称为G的连通分量(Connected Component)。 注意： 任何连通图的连通分量只有一个，即是其自身 非连通的无向图有多个连通分量。 【例】下图中的G4是非连通

10、图，它有两个连通分量H1和H2。连通分量的例子强连通图和强连通分量强连通图和强连通分量v1强连通图强连通图 有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。2强连通分量强连通分量 有向图的极大强连通子图称为G的强连通分量。注意： 强连通图只有一个强连通分量，即是其自身。 非强连通的有向图有多个强连分量。例】下图中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。网络网络(Network)v若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。注意：权是表示两个顶点之间的距离、耗费等具

11、有某种意义的数。【例】下图就是一个网络的例子。网络例子7.2图的存储结构v图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一种表示法，主要取决于具体的应用和欲施加的操作。 为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)=v0，v1，Vn-1。图的邻接矩阵表示法图的邻接矩阵表示法v1图的邻接矩阵表示法图的邻接矩阵表示法 在图的邻接矩阵表示法中： 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息2图的邻接矩阵图的邻接矩阵(AdacencyMatrix) 设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵.的边不是或

12、若的边是或若E(G)v(v0E(G)v(v1iiiijjjjvvvvjiA,),),例v例】下图中无向图G5和有向图G6的邻接矩阵分别为Al和A2。ACDB无向图的邻接矩阵v是对称矩阵v每条边在矩阵中出现2次v每和之和和每列之和相等，和代表顶点的度v把矩阵的各元素求和/2，边数v一个优点. A23=0v缺点：插入一个顶点，删除一个顶点，比较麻烦有向图的邻接矩阵v一般情况，它不是对称，如果有向图的邻接矩阵是对称的话?一个完全有向图。v每行之代表出度，每列之和代表入度。网络的邻接矩网络的邻接矩v 若G是网络，则邻接矩阵可定义为：的边不是或若或的边是或若E(G)v(v0E(G)v(vwiiiiijj

13、jjjvvvvjiA,),),说明其中：wij表示边上的权值；表示一个计算机允许的、大于所有边上权值的数。例4图的邻接矩阵存储结构形式说明图的邻接矩阵存储结构形式说明v #define MaxVertexNum l00 /最大顶点数，应由用户定义 typedef char VertexType； /顶点类型应由用户定义 typedef int EdgeType； /边上的权值类型应由用户定义 typedef struct VextexType vexsMaxVertexNum; /顶点表 EdgeType edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 i

14、nt n，e； /图中当前的顶点数和边数 MGragh；注意： 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。 邻接矩阵表示法的空间复杂度S(n)=0(n2)。5建立无向网络的算法。建立无向网络的算法。void CreateMGraph(MGraph *G)/建立无向网的邻接矩阵表示 int i，j，k，w； scanf(“dd”，&G-n，&G-e)； /输入顶点数和边数 for(i=0;in；i+) /读人顶

15、点信息，建立顶点表 G-vexsi=getchar()； for(i=0；in；i+) for(j=0；jn；j+) G-edgesij=0； /邻接矩阵初始化 for(k=0；ke；k+) /读入e条边，建立邻接矩阵 scanf(ddd，&i，&j，&w)； /输入边(vi,vj)上的权w G-edgesij=w； G-edgesji=w； /CreateMGraph思考题v有向图的邻接矩阵如何建立？练习v如果用邻接矩阵表示有向图，写一个算法求各个顶点的入度和出度vvoid GraphDegree(MGraph G, int IndegreeMaxVexNum,int OutDegreeMa

16、xVexNum)vv图的邻接表表示法图的邻接表表示法 v图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。1邻接表的结点结构邻接表的结点结构v（1）表结点结构 adjvex next 邻接表中每个表结点均有两个域: 邻接点域adjvex存放与vi相邻接的顶点vj的序号j。 链域next将邻接表的所有表结点链在一起。（2）头结点结构v vertex firstedge 顶点vi邻接表的头结点包含两个域： 顶点域vertex存放顶点vi的信息 指针域firs

17、tedgevi的邻接表的头指针。注意：v 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。2无向图的邻接表v对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。【例】对于无向图G5，其邻接表表示如下面所示，其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3，它们分别表示关联于v0的三条边(v0，v1)，(v0，v2)和(v0，v3)。无向图的邻接示例vn顶点,e条边的无向图，n

18、+2e3有向图的邻接表有向图的邻接表v 对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。【例】有向图G6的邻接表表示如下面(a)图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：和。 示例注意：v n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。4有向图的逆邻接表有向图的逆邻接表v 在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。 入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。【例】G6的逆邻表如上面(b)图所示

19、，其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：和。5邻接表的形式说明及其建表算法邻接表的形式说明及其建表算法 （1）邻接表的形式说明 typedef struct node/边表结点int adjvex； /邻接点域struct node *next； /链域/若要表示边上的权，则应增加一个数据域EdgeNode;typedef struct vnode /顶点表结点 VertexType vertex； /顶点域 EdgeNode *firstedge；/边表头指针 VertexNode； typedef VertexNode AdjListMaxVert

20、exNum；/AdjList是邻接typedef struct AdjList adjlist；/邻接表 int n，e； 图中当前顶点数和边数 ALGraph； /对于简单的应用，无须定义此类型，可直接使用AdjList类型。 根据无向图的邻接表判断二个顶点是否相联接int IsAdj(ALGraph G,int i,int j)(2)建立无向图的邻接表算法 void CreateALGraph(ALGrahp *G) /建立无向图的邻接表表示 int i，j，k； EdgeNode *s； scanf(dd，&G-n，&G-e)； /读人顶点数和边数 for(i=0；in；i+) /建立顶

21、点表 G-adjlisti.vertex=getchar()； /读入顶点信息 G-adjlisti.firstedge=NULL；/边表置为空表 for(k=0；ke；k+) /建立边表 scanf(dd，&i,&j)；/读入边(vi，vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)； /生成边表结点 s-adjvex=j; /邻接点序号为j s-next=G-adjlisti.firstedge； G-adjlisti.firstedge=s； /将新结点*s插入顶点vi的边表头部 s=(EdgeNode *)malloc(sizeof(Edg

22、eNode)； s-adjvex=i; /邻接点序号为i s-next=G-adjlistj.firstedge； G-adjlistkj.firstedge=s； /将新结点*s插入顶点vj的边表头部 /end for CreateALGraphvs-next=firstedge;firstedge=s;vhead=s; 注意：v该算法的时间复杂度是O(n+e)。 建立有向图的邻接表更简单，每当读人一个顶点对序号时，仅需生成一个邻接序号为j的边表结点，将其插入到vj的出边表头部即可。 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域7.3图的遍历v1、图的遍历、图的遍历 和

23、树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 以下假定遍历过程中访问顶点的操作是简单地输出顶点。2、布尔向量、布尔向量visited0n-1的设置的设置v 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited0n-1，其初值为假，一旦访问了顶点Vi之后，便将visitedi置为真。深度优先遍历深度优先遍

24、历(Depth-FirstTraversal)v1图的深度优先遍历的递归定义图的深度优先遍历的递归定义 1图的深度优先遍历的递归定义图的深度优先遍历的递归定义v 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深

25、度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。2、深度优先搜索的过程、深度优先搜索的过程v 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过

26、的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。3、深度优先遍历的递归算法、深度优先遍历的递归算法（1）深度优先遍历算法 typedef enumFALSE，TRUEBoolean；/FALSE为0，TRUE为1 Boolean visitedMaxVertexNum； /访问标志向量是全局量 void DFSTraverse(ALGraph *G) /深度优先遍历以邻接表表

27、示的图G，而以邻接矩阵表示G时，算法完全与此相同 int i； for(i=0;in;i+) visitedi=FALSE； /标志向量初始化 for(i=0;in；i+) if(!visitedi) /vi未访问过 BFS(G，i)； /以vi为源点开始DFS搜索 /DFSTraverse（2）邻接表表示的深度优先搜索算法v void DFS(ALGraph *G，int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p； printf(“visit vertex：c”，G-adjlisti.vertex)；/访问顶点vi visitedi=TRUE； /标记

28、vi已访问 p=G-adjlisti.firstedge； /取vi边表的头指针 while(p)/依次搜索vi的邻接点vj，这里j=p-adjvex if (!visitedp-adjvex)/若vi尚未被访问 printf(“from %d to %d n”,i,p-adjvex);v DFS(G，p-adjvex);/则以Vj为出发点向纵深搜索 p=p-next； /找vi的下一邻接点 /DFS（3）邻接矩阵表示的深度优先搜索算法v void DFSM(MGraph *G，int i) /以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵 int j； printf

29、(visit vertex：c，G-vexsi)；/访问顶点vi visitedi=TRUE； for(j=0；jn；j+) /依次搜索vi的邻接点 if(G-edgesij=1&!visitedj) DFSM(G，j)/(vi，vj)E，且vj未访问过，故vj为新出发点 /DFSM注意：v遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraph或MGraph类型的参数，而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑，选择指针类型的参数为宜。 4、深度优先遍历序列、深度优先遍历序列v 对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度

30、优先遍历序列，或简称为DFS序列。（1）一个图的DFS序列不一定惟一 当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之。（2）源点和存储结构的内容均已确定的图的DFS序列惟一 邻接矩阵表示的图确定源点后，DFS序列惟一 DFSM算法中，当从vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个例深度优先遍历v【例】对连通图G7用邻接矩阵表示时，以v0为初始出发点的 DFS遍历过程如下图(a)所示，具体算法的执行过程。DFS序列是v0，v1，v2，v5，v4，v6，v3，v75、算

31、法分析、算法分析v 对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。 当访问某顶点vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。 所以，DFSTraverse的时间复杂度为O(n2) （调用DFSM）

32、或0(n+e)（调用DFS）。广度优先遍历广度优先遍历(Breadth-FirstTraversal)1、广度优先遍历的递归定义、广度优先遍历的递归定义v设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，wt，然后再依次访问与wl，w2，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。 若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。 广度优先遍历类似于树

33、的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。2、广度优先搜索过程、广度优先搜索过程v 在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，xs和y1，y2，yt。 为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，xs和y1，y2，yt，对其中未访者进行访问并将其人队。这种方法是将每个已访问

34、的顶点人队，故保证了每个顶点至多只有一次人队。3、广度优先搜索算法、广度优先搜索算法 typedef enumFALSE，TRUEBoolean；/FALSE为0，TRUE为1 Boolean visitedMaxVertexNum； /访问标志向量是全局量 void DFSTraverse(ALGraph *G) /深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同 int i； for(i=0;in;i+) visitedi=FALSE； /标志向量初始化 for(i=0;in；i+) if(!visitedi) /vi未访问过 BFS(G，i)； /以vi为源点开始D

35、FS搜索 /DFSTraverse(1)邻接表表示图的广度优先搜索算法void BFS(ALGraph*G，int k) / 以vk为源点对用邻接表表示的图G进行广度优先搜索 int i； CirQueue Q； /须将队列定义中DataType改为int EdgeNode *p； InitQueue(&Q)；/队列初始化 printf(visit vertex：e，G-adjlistk.vertex)； /访问源点vk visitedk=TRUE； EnQueue(&Q，k)；/vk已访问，将其人队实际上是将其序号人队） while(!QueueEmpty(&Q)/队非空则执行 i=DeQu

36、eue(&Q)； /相当于vi出队 p=G-adjlisti.firstedge； /取vi的边表头指针 while(p) /依次搜索vi的邻接点vj(令p-adjvex=j) if(!visitedp-adivex) /若vj未访问过 printf(visitvertex：c，C-adjlistlp-adjvex.vertex)； /访问vj visitedp-adjvex=TRUE； EnQueue(&Q，p-adjvex)；/访问过的vj人队 /endif p=p-next；/找vi的下一邻接点 /endwhile /endwhile /end of BFS （2）邻接矩阵表示的图的广度

37、优先搜索算法v void BFSM(MGraph *G，int k) 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i，j； CirQueue Q； InitQueue(&Q)； printf(visit vertex：c，G-vexsk)； /访问源点vk visitedk=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q) i=DeQueue(&Q)； /vi出队 for(j=0;jn;j+)/依次搜索vi的邻接点vj if(G-edgesij=1&!visitedj)/vi未访问 printf(visit vertex：c，G-vexsj)

38、；/访问vi visitedj=TRUE； EnQueue(&Q，j)；/访问过的vi人队 /endwhile /BFSM【例】v下图中G7以邻接矩阵为存储结构，以v0为出发点的BFS搜索过程和BFS序列为V0，V1，V3，V4，V2，V6，V5，V76、算法分析、算法分析v 对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次。广度优先遍历(BFSTraverse)图的时间复杂度和DFSTraverse算法相同。 当图是连通图时，BFSTraverse算法只需调用一次BFS或BFSM即可完成遍历操作，此时BFS和BFSM的时间复杂度分别为O(n+e)和0(n2)。 7.4.1 生成树

39、v如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。 生成树是连通图的包含图中的所有顶点的极小连通子图。 图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。2、深度优先生成树和广度优先生成树、深度优先生成树和广度优先生成树v（1）生成树的求解方法 设图G=(V，E)是一个具有n个顶点的连通图。则从G的任一顶点（源点）出发，作一次深度优先搜索（广度优先搜索），搜索到的n个顶点和搜索过程中从一个已访问过的顶点vi搜索到一个未曾访问过的邻接点vj，所经过的边(vi，vj)（共n-1条）组成的极小连通子图就是生成树。（源点是生成树的根

40、） 通常，由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BPS生成树。【例】v从图G7的顶点v0出发所得的DFS生成树如下图(a)，具体生成过程，BFS生成树如下图(b)，具体生成过程。（2）求DFS生成树和BFS生成树算法v只要在DFS(或DFSM)算法的if语句中，在递归调用语句之前加入适当生成边(vi，vj)的操作(如将该边输出或保存)，即可得到求DFS生成树的算法。 在BFS(或BFSM)算法的if语句中，加入生成树边(vi，vj)的操作，可得到求BFS生成树的算法。3、生成树的通用定义、生成树的通用定义v 若从图

41、的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。（此定义不仅仅适用于无向图，对有向图同样适用。）（1）若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。（2）若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。【例】v下图中(a)图是以v0为根的有向图，它的DFS生成树和BPS生成树分别如图(b)和(c)所示。非连通情况v（3）若G是非连通的无向图，则要若干次从外部调用DFS(或BFS)算法，才能完成对G的遍历。每一次外部调用，只能访问到G的一个连通分

42、量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。（4）若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。【例】v下图(a)所示的有向图，其DFS和BFS生成森林分别如(b)和(c)所示。最小生成树最小生成树v1、最小生成树最小生成树 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 这里: TE表示T的边集 w(u，v)表示边(u，v)的权。 权最小的生成树称为G的最小生成树(Minimum S

43、pannirngTree)。最小生成树可简记为MST。TEvuvuwTW),(),()(2、生成树和最小生成树的应用、生成树和最小生成树的应用v 生成树和最小生成树有许多重要的应用。【例】网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。5、普里姆、普里姆(Prim)算法算法v（1）算法思想 T=(U，TE)是存放MST的集合。T的初值是(r，) 即最小生成树初始时只有一个红点r，没有红边。T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生

44、成树 选择紫边集中一条轻边并扩充进T将轻边连接的蓝点改红点将轻边改红边 修改紫边集02101603504505INT_MAXabcghefd2132224111abcghefd21221112（4）Prim算法的伪代码描述v PrimMST(G，T，r) /求图G的以r为根的MST，结果放在T=(U，TE)中 InitCandidateSet()；/初始化：设置初始的轻边候选集，并置T=(r，) for(k=0；kn-1；k+) /求T的n-1条树边 (u，v)=SelectLiShtEdge()；/选取轻边(u，v)； TT(u，v)；/扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U

45、ModifyCandidateSet()； /根据新红点v调整候选轻边集 存储结构v#define 32767 INT_MAXv#define n 100vtypedef int AdjMatrixnn;vtypedef structvint fromvex,tovex;vint length;vTreeEdgeNode;vtypedef TreeEdgeNode MSTn-1;vAdjMatrix G;vMST T;(1)初始化vvoidInitCandidateSet（AdjMatrixG,MSTT,intr)vinti,k=0;for(i=0;in;i+)if(i!=r)Tk.fromv

46、ex=r;Tk.tovex=i;Tk+.length=Gri;选取路径vintSelectLightEdge(MSTT,intk)v/T数组中开始求最小边的位置数组中开始求最小边的位置vvintmin=INFINITY,i,minpos=-1;vfor(i=k;in-1;i+)vif(Ti.lengthmin)vvmin=Ti.length;vminpos=i;vvif(min=INFINITY)verror(“Graphdisconnected”);vreturnminpos;v调整候选集vvoidModifyCandidateSet(AdjMatrixG,MSTT,intk,intv)/新

47、增加的顶新增加的顶点，由于新加入一个顶点，点，由于新加入一个顶点，v/要调整其它顶点到已选顶点的距离要调整其它顶点到已选顶点的距离vinti,d;vfor(i=k;in-1;i+)/i=4,v=2vd=GvTi.tovex;vif(dTi.length)vvTi.length=d;vTi.fromvex=v;vv完整的MST程序vvoidPrimMST(AdjMatrixG,MSTT,intr)vvintk,m,v;vTreeEdgeNodee;vInitCandidateSet(G,T,r);vfor(k=0;kn-1;k+)vvm=SelectLightEdge(T,k);/k=0,m=2

48、ve=Tm;Tm=Tk;Tk=e;vv=Tk.tovex;vModifyCandidateSet(G,T,k+1,v);vv（1）算法思想vT的初始状态 只有n个顶点而无边的森林T=(V， )按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST注意： 安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树 因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。（2）算法特点v 该算法的特点是：当前形成的集合T除最后的结果外，始终是一个森林。（3）Kruskal算法的抽象描述v KruskalMS

49、T(G)/求连通网G的一棵MST T=(V，)； /初始化，T是只含n个顶点不包含边的森林 依权值的递增序对E(G)中的边排序，并设结果在E0.e-1中 for(i=0;ie;i+) /e为图中边总数 取E0e-1)中的第i条边(u，v)； if u和v分别属于T中两棵不同的树then T=T(u，v)；/(u，v)是安全边，将其加入T中 if T已是一棵生成树then return T； /endfor return T； Kruskal算法7.5最短路径1、带权图的最短路径问题、带权图的最短路径问题v带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。 路径长度的的具体含义取决于边上权值所代表的意义。【例】v交通网络中常常提出的如下问题就是带权图中求最短路径的问题。 （1）两地之间是否有路相通? （2）在有多条通路的情况下，哪一条最短?其中:交通网络可以用带权图表示：图中顶点