数据结构中图的教学课件

第6章图图作为一种非线性数据结构，被广泛应用于多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人二智能、编译系统等领域，在这些技术领域中把图结构作为解决问题的数学手段之一。在离散数学中侧重于对图的理论进行系统的研究。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。1

图是一种比树更为复杂的非线性结构。在图状结构中，任意两个结点之间都可能具有邻接关系，即在图的数据元素之间存在多对多的关系。2

本章主要介绍以下几个方面的内容：图的定义及常用术语；图的各种存储结构；图的遍历；构造最小生成树的算法；求最短路径的算法；拓扑排序及其算法。36.1图的基本概念在讲述图时，习惯把数据元素统称为是顶点。“图”是图状结构的简称，它由一个非空的顶点集合V和一个描述顶点之间邻接关系的边集合E组成，E中每条边连接的两个顶点都必须属于集合V。于是，一个图可以记为：

G=（V，E）

6.1.1

图的定义4 对于一个图G来说，边的集合E可以是空的。若vi、vj是V集合中的两个顶点，且有边连接，那么就用记号（vi，vj）表示顶点vi到顶点vj之间的边。通常，边是没有方向的，即若图G中有边（vi，vj），那么也可以说有边（vj，vi）。当图中的边不带有方向时，称该图为“无向图”。5若图中的边是有向的，这样的图被称为“有向图”。在有向图中，有边（vi，vj），并不意味着也有边（vj，vi）。常称有向图的边为“弧”，把有向图中从顶点vi到顶点vj的弧记为<vi，vj>，而把从顶点vj到顶点vi的弧记为<vj，vi>，这是两条不同的弧。由于有向图的弧是有方向的，因此常称弧的起始顶点为“弧尾”，弧的终止顶点为“弧头”。

6图6-1无向图和有向图71．顶点的度、入度、出度6.1.2有关图的常用术语无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，则表明顶点vi和vj互为邻接点，简称vi与vj相邻接。所谓顶点vi的“度”，是指与它相邻接的顶点的个数，记为D(vi)。

8注：1）

顶点的位置顶点在图中的位置如何确定？从图的逻辑结构定义来看，图中的顶点是非线性序列，不能像线性序列排列有唯一的序列。在图中可以将任一个顶点看成是图的第一个顶点，同理，对于任一顶点而言，它的邻接点之间也不一定存在顺序关系。9为了对图的操作方便，需要将图中的顶点按排列起来。所谓的“顶点在图中的位置”是指该顶点在存储中形成的位置序号，（如果是顺序存储可能是数组下标，如果是链式存储可能是存储的地址指针）。102）邻接点对于无向图G＝(V，{E})，如果边（v1，v2）∈E，则称顶点v1，v2互为邻接点，即v1，v2相邻接。边（v1，v2）依附于顶点v1和v2

，或者说边（v1，v2）与顶点v1和v2相关联。

11在有向图中，以顶点vi为弧尾的弧的个数，称为顶点vi的“出度”，记为OD(vi)；以顶点vi为弧头的弧的个数，称为顶点vi的“入度”，记为ID(vi)。这时，一个顶点vi的度是指它的入度与出度之和，即：D(vi)=ID(vi)+OD(vi)。121314

在无向图G中，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个边的序列：（vi,vi1），（vi1,vi2），…，（vim,vj）其中顶点vi、vi1、vi2、…、vim、vj属于G的顶点集合V，边（vi,vi1）、（vi1,vi2）、…、（vim,vj）属于G的边的集合E。2．路径、路径长度15对于有向图G，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个弧的序列：

<vi,vi1>，<vi1,vi2>，…，<vim,vj>

其中顶点vi、vi1、vi2、…、vim、vj属于G的顶点集合V，弧<vi,vi1>、<vi1,vi2>、…、<vim,vj>属于G的弧的集合E。16

所谓顶点vi到顶点vj的路径“长度”，是指在这条路径上拥有的边的个数。V1V2V3V4G4V1V2V3V4G317在图G＝(V，E)中，如果有结点序列：

Vp，Vi1，Vi2…，Vin，Vq，使得{(Vp，Vi1)，(Vi1，Vi2)，…，(Vin，Vq)}∈E（若对有向图，则存在一系列弧）则称从结点Vp到结点Vq存在一条路径，路径长度就为这条路径上的边数。如果一条路径上的结点除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一简单路径。

3．简单路径、回路18把路径(V1，V2)，(V2，V3)，(V3，V4)缩写成V1V2V3V4。在图G3中V1，V2，V3和V1V3V4V1V3是两条路径，前者是一条简单路径，我们只研究简单路径。当Vp=Vq时简单路径Vp，Vi1，Vi2…，Vin，Vp，称为回路(也称环)。19若一个有n个顶点的无向图，拥有n(n−1)/2条边，那么就称该图为“无向完全图”。对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。若一个有n个顶点的有向图，拥有n(n−1)条弧，那么就称该图为“有向完全图”。 对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。

4．无向完全图、有向完全图20图6-2（a）所示为一个无向完全图，由于它有4个顶点，所以它有4

(4−1)/2=6条边；图6-2（b）所示为一个有向完全图，由于它有4个顶点，所以它有4

(4−1)=12条弧。

21图6-2无向、有向完全图22

无论是无向图还是有向图，图中的每一条边或弧都与两个顶点有关。 因此，在图的顶点数n、边数e以及各顶点的度D(vi)（1≤i≤n）三者之间，有如下的关系存在：23已知两个图G=（V，E），G′=（V′，E′）。若有V′是V的子集，E′是E的子集，且E′中的边（或弧）都依附于V′中的顶点，那么就称G′是G的一个“子图”。

5．子图24图6-3子图示例25

连通、连通图、连通分量都是关于无向图的概念。在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vi与vj是“连通”的。如果无向图G中任意一对顶点之间都是连通的，则称该图G为“连通图”，否则是非连通图。6．连通、连通图、连通分量26在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个“连通分量”。27图6-4连通图、非连通图、连通分量2829有时，可以给图的边或弧依附上某种数值，这种与图的边或弧相关的数值被称为“权”。边或弧上带有权的图称为“网图”或“网络”。7．边的权、网络30图6-5无向网图和有向网图318.生成树：n个顶点的连通图的生成树是一个极小连通子图，它包含连通图的全部顶点及n-1条边，使所有顶点都连通但不构成回路。生成树具有两个特点：1）n个顶点的生成树包含n-1条边；2）如果在生成树中任意增加一条边，则有一条回路。

3233课堂作业：选择题：1.设无向图G中顶点数为n,则图G中最少有()条边A.n(n-1)B.n-1C.n+1D.2n2.若图G为n个顶点的有向图,则图G中最多有()条边A.n(n-1)B.n-1C.n(n+1)D.n+13.在一个图G中,所有顶点的度数之和等于所有边数的()倍A.3B.1/2C.4D.2344.在具有n个顶点的无向完全图G中边的总数为()A.n+1

B.n(n-1)/2C.n(n+1)D.n-15.在具有6个顶点的无向图G中至少应有()条边才能确保是一个连通图.A.8B.7C.6

D.56.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是()A.n-1B.n+1C.n2D.(n-1)235答案：BADBDC36

6.2

图的存储结构图是一种用途非常广的数据结构，存储方法是多种多样，对于不同的应用问题有不同的表示方法。不论哪种数据结构，在存储时主要有两方面：第一.如何存储数据；第二.如何存储数据间的关系。当数据和关系都存储在存储器中，就可以按数据间的关系，实现对数据的各种操作。37图有四种比较常用的存储方法：①邻接矩阵表示法；②邻接表；③邻接多重表；④十字链表。386.2.1

邻接矩阵所谓“邻接矩阵”，是表示顶点之间相邻关系的矩阵，是指一种存储结构的组合。

用一个一维数组存储图中顶点的数据信息；用一个二维数组（即矩阵）存储图中各顶点间的邻接关系。通常，简略地只是把这个组合中的二维数组称作是图的“邻接矩阵”。39假设图G=（V，E）有n个顶点，为了表示n个顶点之间的邻接关系，说明一个n

n的矩阵，并把其元素规定为：

40例6-1:对于下面所示的无向图，请给出它的邻接矩阵，并根据邻接矩阵计算顶点v2的度。

4142图6-6无向图及相应的邻接矩阵43分析有向图的邻接矩阵图6-7有向图及相应的邻接矩阵44练习:对于下面所示的无向图和有向图，判断它们邻接矩阵是否正确，并根据邻接矩阵计算顶点v1的度。45对于一个网图来说，不仅应该通过邻接矩阵反映出顶点之间的邻接关系，还应该利用它反映出依附于边或弧的权值。因此，这时规定邻接矩阵的元素为：

46图6-8图6-5中网图的邻接矩阵47对于邻接矩阵，有如下特点。（1）无向图的邻接矩阵是对称的对于无向图来说，由于有边（vi,vj）就意味着有边（vj,vi），所以无向图的邻接矩阵关于其主对角线总是对称的。48（2）邻接矩阵与图中顶点的度有密切关系对于无向（网）图，其相应的邻接矩阵中第i行（或第i列）里非零（且非∞）元素的个数，正好是第i个顶点vi的度D(vi)。49对于有向（网）图，其相应的邻接矩阵中第i行里非零（且非∞）元素的个数，正好是第i个顶点vi的出度OD(vi)；其相应的邻接矩阵中第i列里非零（且非∞）元素的个数，正好是第i个顶点vi的入度ID(vi)。50邻接矩阵的类型描述#defineMAXVEX50 /*最大顶点个数*/typedefintweight; /*权值*/typedefcharDataType;typedefstruct{ weightarcs[MAXVEX][MAXVEX];/*邻接矩阵*/ DataTypedata[MAXVEX];/*顶点信息*/ intvexs; /*顶点数*/}MGraph,*AdjMetrix;51邻接矩阵表示下的基本操作

1．建立一个图的邻接矩阵voidCreateGraph(AdjMetrixg,intm[][MAXVEX],DataTyped[],intn){inti,j; g->vexs=n;for(i=0;i<n;i++){g->data[i]=d[i];for(j=0;j<n;j++)g->arcs[i][j]=m[i][j]; }}522.显示邻接矩阵voidDispGraph(AdjMetrixg){

inti,j; printf("项点：\n\t"); for(i=0;i<g->vexs;i++) printf("%c\t",g->data[i]); printf("\n\n矩阵:");for(i=0;i<g->vexs;i++){

printf("\n%c:\t",g->data[i]);for(j=0;j<g->vexs;j++) printf("%d:\t",g->arcs[i][j]);}printf("\n\n");}

533．取第一个邻接点intGetFirst(AdjMetrixg,intk){inti;if(k<0||k>g->vexs){printf("参数k超出范围！\n");return-1;}for(i=0;i<g->vexs;i++)if(g->arcs[k][i]==1)returni; return-1;}

544．下一个邻接点intGetNext(AdjMetrixg,intk,intt){ inti;if(k<0||k>g->vexs||t<0||t>g->vexs){ printf("参数k或t超出范围！\n"); returnNULL; } for(i=t+1;i<g->vexs;i++) if(g->arcs[k][i]==1)returni; return-1;}

55main(){MGraphgg; AdjMetrixg=≫ intpos,i; chard[]={'A','B','C','D','E'}; intm[][MAXVEX]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,0,0},{0,1,0,0,1},{1,0,0,1,0}}; CreateGraph(g,m,d,5); DispGraph(g); for(i=0;i<g->vexs;i++)

56{pos=GetFirst(g,i);if(pos!=-1)printf("\n[%c]\t%c",g->data[i],g->data[pos]);elseprintf("\n[%c]",g->data[i]);while(pos!=-1){pos=GetNext(g,i,pos); if(pos!=-1) printf("\t%c",g->data[pos]);}}printf("\n");}57课堂练习:写出下面所示图的邻接矩阵。58分析

用邻接矩阵表示图的不足之处：无论图中实际包含多少条边，图的读入、存储空间初始化等需要O（n2）个单位时间，这对边数较少（当边数m<<n2）的稀疏图不是很经济的。对于边数较多（如m>n*logn）的稠密图，这种存储方式是有效的。59邻接表表示图是由两部分构成，即顶点数据表和表示数据关系的边（弧）构成的表：

⑴顶点数据表：由所有顶点数据信息以顺序结构的向量表形式存储，一个表目对应于图的一个结点，每个表目包括两个部分，其一是表示数据的，可以是数据或指向结点数据的指针（data）；另一个是表示边（弧）的指针，该指针（firstarc）指向相邻的第一条边（弧），通过这个指针便可以随机访问相邻的任一顶点。表头结点的结构如图(a)所示。

6.2.2

邻接表6061

⑵表示边的表：图中有n个顶点，就有n个表示边的链表，其中第i条链是由与第i个顶点相邻的边构成的链表。图的每个结点都有一个边链表，这个链表的表头是顶点数据表中第i个表目的指针域。边链表中结点的结构如图(b)所示。它由三部分组成，邻接点域(adjvex)：用于存放与顶点vi相邻接的顶点在顶点表中的位置；链指针域(nextarc)用于指向与顶点vi相关联的下一条边或弧的结点；数据域(info)用于存放与边或弧相关的信息(权的信息)。6263把有关每一个顶点的单链表表头结点汇集在一起，成为一个一维数组。这样，这个一维数组、各顶点的单链表以及记录图顶点和边（或弧）个数的变量，就统称是图的邻接表。6465表示下面图的邻接表

DBACFE66

A14

B045

C35

D25

E01

F12301234567有向图的邻接表可见，在有向图的邻接表中不易找到指向该顶点的弧ABECF142301201234

ABCFE

68V5V1V2V3V4G869图6-10无向图（图6-6）的邻接表70图6-11有向图（图6-7）的邻接表71图6-11无向网图和有向网图的邻接表结构72邻接表的类型描述#defineMaxVertices20/*链表的结点结构信息*/typedefstructArcNode{intadjvex;/*该弧所指向的顶点的位置*/

structArcNode*nextarc;/*指向下一条弧的指针*/InfoTypeinfo/*弧上的信息*/}ArcNode;73/*表头向量的结点结构信息*/typedefstructVnode{VertexTypedata;/*顶点信息*/

ArcNode*firstarc;/*指向第一条依附该顶点的的指针*/

}Vnode;74/*图的结构信息*/typedefstruct{Vnodevertex[MaxVertices];/*表头向量*/

intvexnum,arcnum;/*图的当前顶点数和弧数*/

}AdjList;75基本操作的实现 1．建立图的邻接表函数 该函数包含两部分内容：顶点信息的输入和边信息的输入。也可以理解为顶点的插入和边的插入。 算法如下:76VoidCreateGraph(AdjList*G,intn,inte)/*输入图的数据信息，建立邻接链表*/{ArcNode*q1,q2;G->arcnum=e;G->vexnum=n;Printf("\n输入顶点的信息（整型）：");for(inti=1;i<=G->vernum;i++)G->Vertex[i].data=i;/*初始化*/77for(inti=1;i<=G->arcnum;i++) {printf("\n输入边的信息（顶点号i顶点号j边的权值W）："); Scanf(“％d,%d,%d”,&i,&j,&w);/*对于无向图*/if(i<1||i>G->vexnum||j<1||j>G->arnum){printf("参数1或2越界出错!\n");return;}/*在第i条链表上，链入边（i,j）的结点*/q1=(ArcNode*)malloc(sizeof(ArcNode));78

q1->adjvex=j;q1->infi=w;q1->nextarc=G->Vertex[i-1].firstarc;G->Vertex[i-1].firstarc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode));q2->adjvex=i;q2->infi=w;q2->nextarc=G->Vertex[j-1].firstarc;G->Vertex[j-1].firstarc=q2;}}796.3图的遍历所谓“图的遍历”，即是指从图的某一个顶点出发访问图中的所有顶点，且每个顶点只被访问一次的这样一个过程。80

遍历图比遍历树要繁杂，因为图中的某一个顶点可能与图中其余顶点相邻接，即图中允许有回路。所以当从某一顶点访问了其他顶点后有可能顺着某一些边又回到了该顶点。因此在遍历图时，为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，设置一个数组，用于标示图中每个顶点是否被访问过，它的初始值全部为0(“假”)，表示顶点均未被访问过；某一个顶点被访问后，置相应访问标志数组中的值为1(“真”)，以表示该顶点已被访问过。81按图中结点的访问顺序，图的遍历分两种：一种深度优先遍历，另一种是广度优先遍历。

82深度优先搜索(Depth_FirstSearch)是指按照深度方向搜索，它类似于树的先根遍历。深度优先搜索的基本思想是：⑴从图中某个顶点vi出发，首先访问vi

。⑵找出顶点vi的第一个未被访问的邻接点vj，然后访问顶点vj。找出顶点vj的第一个未被访问的邻接点vj1，……,重复本步骤，直到顶点vj1的所有的邻接点都被访问为止。6.3.1

图的深度优先搜索83⑶返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个末被访问的邻接点，然后执行步骤⑵。否则行步骤⑷。⑷若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述搜索过程，直至图中所有顶点均被访问过为止。84深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先生成树85图的遍历算法如下：

voidTraver(GraphG)/*Graph表示图G的存储结构,深度优先遍历图G*/{for(vi=0;vi<G.vexnum;vi++)/*初始化*/visited[vi]=flase;for(vi=0;vi<G.vexnum;vi++)if(!visited[vi])DFS(G，vi);/*如果vi没访问，就从vi开始深度遍历*/}其中从v0出发的递归过程如下：voidDFS(GraphG,intv0)/*从v0出发深度优等遍历图G*/{visit[v0];visited[v0]=TRUE;w=Firstadj(G，v0);/*w为v0的邻接点*/while(w>0)/*当存在邻接点*/{if(!visited[w])DFS(G，w);w=Nextadj(G，v0，w);/*找下一邻接点*/}}86算法中对于Firstadj(G，v0)以及Nextadj(G，v0，w)并没有具体实现。因为对于图的不同存储方法，两个操作的实现方法不同，时间复杂度也不同。87⑴用邻接矩阵方式实现voidDFS(MGraphG,intv0)/*图G为邻接矩阵类型*/{visit(v0);visited[v0]＝TRUE;for(vj＝0;vj<G.vexnum;vj++)if(!visited[vj]&&G.arc[v0][vj].adj==1)DFS(G，vj);/*找与v0相邻没访问的所有点遍历*/}88⑵用邻接表方式实现深度优先搜索voidDFS(ALGraph,intv0){visit(v0);visited(v0)=TRUE;p=G.vertices[v0].firstarc;/*找到与v0相邻的第一个结点*/while(p){if(!visited(p->adjvex))DFS(G，p->adjvex);p=p->nextarc;}}89DFS

在访问图中某一起始顶点v

后,由

v

出发,访问它的任一邻接顶点

w1;再从w1出发,访问与w1邻

接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。90例:图6-12（a）所示为一个无向图，图6-12（b）是该图的邻接表。试求对该图实施深度优先搜索后，所得到的遍历序列。91图6-12基于邻接表的无向图深度优先搜索92解：假定我们从顶点v1出发对图进行深度优先遍历。遍历的序列为：

v1→v2→v4→v5→v6→v393问题:深度优先遍历的访问顺序与图的邻接表存储状态有关，由于图的邻接表不是唯一的，因此对于同一个图，其深度优先遍历输出的结果也可能是不同的。但采用邻接矩阵或邻接表存储结构内容已确定的图的DFS序列将是确定的。例如：下面是同一个图，但存储结构不同，因此深度优先遍历序列也不同，请大家动手做做。94BACDFEABFDCE请问为什么会出现这种现象？9596连通图的深度优先搜索遍历

从图中某个顶点V0

出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。97V0w1w3w2w4w5w6w8w7w10w9w11G1G2G3V0w1w3w298由此可以看出:1.从深度优先搜索遍历连通图的过程类似于树的先根遍历;2.如何判别V的邻接点是否被访问？解决的办法是:为每个顶点设立一个“访问标志visited[w]”;99非连通图的深度优先搜索遍历

以邻接矩阵作为存储结构,实现非连通图的深度优先搜索遍历。对于非连通图，一次遍历仅能访问开始顶点所在连通分量中的每个顶点，其他连通分量中的顶点则无法访问到。因此，对于非连通图，在遍历完一个连通分量之后，还要再选择一个开始顶点，遍历下一个连通分量，重复这个过程，直到图中的所有顶点…100abchdekfg812345670achkfedbg例如:访问次序:achdkfebg101分析 采用邻接链表来表示图时，需要访问表头向量时间为O(n)。而外接的边结点无向图为2e（e为图的边数）个，有向图为e个，时间消耗大约为O(e)。因此DFS算法的时间复杂度为O(n+e)。对于边数很少的图适合采用邻接表存储结构.102广度优先搜索(BreadthFirstSearch)

是指照广度方向搜索，和深度优先搜索不同的是：广度优先搜索先访问完所有的邻接点，再去寻找与邻接点相邻的下一层的其他顶点，它类似于树的层次遍历。广度优先搜索的基本思想是：⑴从图中某个顶点v0出发，首先访问v0。⑵依次访问v0的各个末被访问的邻接点。6.3.2

广度优先搜索103⑶分别从这些邻接点(端结点)出发，依次访问它们的各个末被访问的邻接点(新的端结点)。访问时应保证：如果vi和vk为当前结点，且vi在vk之前被访问，则vi的所有末被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复步骤⑶，直到所有结点均没有末被访问的邻接点为止。⑷若此时还有顶点末被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。104广度优先搜索的示例ACDEGBFIHACDEGBFH123456789123456789广度优先搜索过程广度优先生成树I105BFS在访问了起始顶点v之后,由v出发,依次访问v的各个未被访问过的邻接顶点w1,w2,…,wt,然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。106广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。107108注：采用邻接链表存储结构，广度优先搜索遍历图的时间复杂度与深度优先遍历是相同的，其时间复杂度也是O(n2)。

109课堂练习:对于下图所示的无向图，求：（1）邻接矩阵、邻接表。（2）给出从顶点A出发深度优先搜索遍历序列（3）给出从顶点C出发广度优先搜索遍历序列110课堂练习:1、n个顶点的连通图最多有———条边。2、在一个具有n个顶点的无向图中，要连通全部顶点至少需要——条边3、设图G有n个顶点和e条边，进行深度优先遍历的时间复杂度至多为——，进行广度优先遍历的时间复杂度至多为——。1114、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于——5、已知图G的邻接表如图所示，其从顶点v1出发的深度优先遍历序列为————，其从顶点v1出发的广度优先遍历序列为——12＾34＾53244＾5＾24＾1121、对于如图所示的有向图，试给出（1）图的邻接矩阵；（2）邻接表（出边表）和逆邻接表（入边表）1131146.4生成树与最小生成树问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？115该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。1166.4.1生成树与最小生成树的概念有n个顶点的无向连通图G=（V，E）的“生成树”，是G的一个子图S，它是包含G的所有n个顶点在内的一个极小连通子图。即S由V中的n个顶点、E中的n−1条边组成。117作为无向连通图的生成树，有这样的性质：

只要往这个生成树里添加一条属于原图中的边，就会产生回路；

只要在这个生成树里减少任意一条边，它就成为了一个非连通图；

无向连通图的生成树不是唯一的。118对于一个无向连通网图G的生成树S来说，称各边权值之和为该生成树的权。所有生成树中权值最小的那棵生成树T，被称作是图G的最小代价生成树，简称为“最小生成树（MST）”。119算法的基本思想：设G=(V,E)是连通网，V是连通网中顶点集合，E是连通网中边的集合。T=(U,D)是正在构造的最小生成树，U是最小生成树的顶点的集合，D是最小生成树的边的集合。V-U表示属于集合V，但不属于集合U的顶点集合。6.4.2构造最小生成树的算法1．构造最小生成树的普里姆算法120（1）若从顶点v0开始构造最小生成树，则从集合V中取出顶点v0放入集合U中。此时，集合U={v0}，集合V-U={除v0以外的所有顶点}，集合D为空。（2）若在集合U中的顶点vi和集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不构成回路。将顶点vj加入集合U中，将边(vi,vj)加入集合D中。（3）重复步骤（2），直至U与V相等为止。此时，D中必有n-1条边，则T=(U,D)即是最小生成树。121例6-15:已知一个如图所示的带权图，请给出根据普里姆算法构造的一颗最小生成树（假设从顶点1开始构造）。

122123图6-14使用普里姆算法求网图的最小生成树过程124图6-14使用Prim算法求网图的最小生成树过程125 克鲁斯卡尔算法的思想是：设G=(V,E)是一个具有n个顶点的带权连通图，T=(U,D)是G的最小生成树。初始时，U中包含G的全部n个顶点，D为空。

2．构造最小生成树的克鲁斯卡尔算法1263.从E中选择一条以前未选择过的、边上的权值最小的边加入D中。但注意两点:(1)若加入后，并未使T形成回路，则继续选择下一条边；(2)若加入后，使T形成回路，则放弃选择的边。4.重复以上过程，直至D中包含了n-1条边为止。此时，T即为G的最小生成树。127 这样，最小生成树T中的各个顶点各自构成一个连通分量。然后，按照边的权值递增的顺序考察网G中的边集E中的各条边：若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到最小生成树T，同时把两个连通分量连接为一个连同分量；128 若被考察的边的两个顶点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为１时，此T中的该连通分量即为网G的一棵最小生成树。129图6-15使用Kruskal算法求网图的最小生成树过程130图6-15使用Kruskal算法求网图的最小生成树过程131图6-15使用Kruskal算法求网图的最小生成树过程132abcdegf195141827168213127aedcbgf1485316211336.5最短路径

如果将交通网络画成带权图，假如用顶点表示城市，边表示公路段，则由这些顶点和边组成的图可表示构通各城市的公路网。边的权用以表示两个城市之间的距离、走过这段公路所需要的时间、通过这段朗的难易程度等。作为司机和乘汽车的人，自然关心如下两个问题：⑴从甲地到乙地是否有公路？⑵从甲地到乙地有几条公路，哪条公路最短或费用的代价最小？134这就是最短路径所要讨论的问题，所以下面探讨有向图的最短路径。路径的开始顶点：源点，路径的最后一个顶点：终点或目标点。除非特别说明，否则，所有的权大于零。设有带权的有向图G=(V，{E})，G中的边权为w(e)。已知源点为v1，求v1到其它各顶点的最短路径。135求最短路径是图的又一个典型应用。图6-16最短路径136最短路径分为单源最短路径和每对顶点间的最短路径两类问题，前者讨论的是图中某个顶点到其他各顶点的最短路径，后者讨论的是图中每对顶点间的最短路径。137所谓“单源最短路径”，即已知有向网图G=（V，E）和一个源（顶）点V0，求V0到其他各顶点的最短路径。求从源点V0到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径

6.5.1单源最短路径138源点v1…v2其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。139注意理解下面结论:1.路径长度最短的最短路径的特点:在这条路径上，必定只含一条弧，并且这条弧是所有从源点出发的弧中权值最小。

2.下一条路径长度次短的最短路径的特点:它只可能有两种情况:或者是直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。1403.再下一条路径长度次短的最短路径的特点:它可能有三种情况：或者是，直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是，从源点经过顶点v2，再到达该顶点。4.其余最短路径的特点：它或者是直接从源点到该点(只含一条弧)；或者是，从源点经过已求得最短路径的顶点，再到达该顶点。141V4V0V1V2V3V5V6V8V76144248533912图6.40有向带权图142源点终点最短路径长度v0v1v0v16v2v0v24v3v0v35v4v0v2v46v5v0v2v4v57v6v0v2v4v5v7v613v7v0v2v4v5v7v611v8v0v2v4v5v7v6v815143求单源最短路径的Dijkstra（迪杰斯特拉）算法思路:按路径长度递增的顺序，逐个产生各最短路径。把图中的所有顶点分成两组：第一组取名为U，里面包含的是那些从源点u到它们的最短路径已经确定的顶点；第二组取名V−U，里面包含的是那些从源点u到它们的最短路径还未最后确定的顶点。具体步骤如下：

144算法思想：设集合S存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点，不妨设为v1。以后每求得一条最短路径（v1，…，vk），就将vk加入到集合S中，直到全部顶点全部都加入到集合S中为止。145（1）初始时，集合S里只含一个源点v1，集合V−S里是图中除v1以外的所有顶点，v1到其他顶点的距离是它们间弧的权值（当不存在弧时，长度为∞）；146（2）从V−S里挑选出一个与源点v1的距离为最小的顶点vi，把它从V−S移到S里，然后对V−S里剩下的顶点（比如vk）到源点v1的距离进行修改，方法是若图中存在弧（vi,vk），且该弧的权值加上v1到vi的距离之和小于原先v1到vk的距离，那么就用此和代替原先v1到vk的距离，否则原先v1到vk的距离保持不变；147（3）不断地对集合V−S实行操作 （2），当V−S为空时，算法结束，所求得的v1到各顶点的距离即是源点到其他顶点的最短路径长度。148例如用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径149

（1）初始时，S={1}，V-S={2，3，4，5}。各点的距离值及路径为：

1502.从V-S中选择距离值最小的顶点2，加入到S中。此时S={1，2}，V-S={3，4，5}。然后对V-S中各点的距离值进行修正，修正后各点的距离值及路径为：

1513.再从V-S中选择距离值最小的顶点4，加入到S中。此时S={1，2，4}，V-S={3，5}。修正V-S中的点的距离值为：1524.继续从V-S中选择距离值最小的顶点3，加入到S中。此时S={1，2，3，4}，V-S={5}。修正V-S中的点的距离值为：1535.最后从V-S中选择距离值最小的顶点5，加入到S中。此时S={1，2，3，4，5}，V-S={}，算法结束。154课堂练习:求有向网G的a顶点到其余顶点的最短路径24158639735104afedbcg2155求解过程:1.初始时，S={a}，V-S={b,c,d,e,f,g,}。各点的距离值及路径为：1组顶点:{a}2组顶点:{b,c,d,e,f,g}最短路径:0距离值:24,8,15,∞,∞,∞经过路径:a->a经过路径:a->b,a->c,a->d,a->e,a->f,a->g1562.从V-S中选择距离值最小的顶点c，加入到S中。此时S={a,c}，V-S={b,d,e,f,g}。然后对V-S中各点的距离值进行修正，修正后各点的距离值及路径为：1组顶点:{a,c}2组顶点:{b,d,e,f,g}最短路径:0,8距离值:24,15,15,11,∞经过路径:a->a,a->c经过路径:a->b,a->d,a->c->e,a->c->f,a->g

1573.从V-S中选择距离值最小的顶点f，加入到S中。此时S={a,c,f}，V-S={b,d,e,g}。然后对V-S中各点的距离值进行修正，修正后各点的距离值及路径为：1组顶点:{a,c,f}2组顶点:{b,d,e,g}最短路径:0,8,11距离值:24,15,13,21经过路径:a->a,a->c,经过路径:a->b,a->d,a->c->fa->c->f->e,a->c->f->g1584.从V-S中选择距离值最小的顶点e，加入到S中。此时S={a,c,f,e}，V-S={b,d,g}。然后对V-S中各点的距离值进行修正，修正后各点的距离值及路径为：1组顶点:{a,c,f,e}2组顶点:{b,d,g}最短路径:0,8,11,13距离值:24,15,21,经过路径:a->a,a->c,经过路径:a->b,a->d,a->c->fa->c->f->e,a->c->f->ga->c->f->e,

1595.从V-S中选择距离值最小的顶点d，加入到S中。此时S={a,c,f,e,d}，V-S={b,g}。然后对V-S中各点的距离值进行修正，修正后各点的距离值及路径为：1组顶点:{a,c,f,e,d}2组顶点: