软件技术基础13-14图

图

软件技术基础（六）西安电子科技大学

电子工程学院

林杰1本章要求1.基本要求（1）熟练掌握图的定义，无向图、有向图、子图、顶点的度、带权图、连通图、强连通图等的概念，边（或弧）与顶点之间的关系。掌握图的两种存储方法，以及存储结构的定义，了解建立图的算法。（2）熟练掌握深度优先和广度优先搜索遍历图的方法，了解相应的算法，写出给定图的遍历序列。掌握生成树的概念，了解相应的算法，根据两种搜索遍历的方法画出生成树；掌握最小生成树的概念，用Prim（普里姆）和Kruskal（克鲁斯卡尔）算法画出最小生成树。2.重点、难点重点：图的定义及图的概念，图的遍历方法和生成树及最小生成树。难点：图的建立和遍历算法，最小生成树算法2本章内容7.1图的基本概念7.2图的存储方法7.3图的遍历7.4生成树和最小生成树7.5最短路径7.6拓扑排序7.7关键路径3哥尼斯堡七桥问题（1736年）4能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？5图的实例：我的毕业旅行十三城市之间火车费用表十三城市之间火车行驶时间表方案1：最省钱方案2：最省时67.1图的基本概念图G是由一个顶点集V(G)和一个边集E(G)构成的数据结构。记为二元组形式：G=(V,E)。其中:

V是由顶点构成的非空有限集合，记为：V＝{V0,V1,V2,…Vn-1}

E是由V中顶点的对偶构成的有限集合，记为：E={(V0,V2),(V3,V4),…}，若E为空，则图中只有顶点而没有边。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。7其中顶点的对偶可以表示成：

(Vi,Vj)—无序的对偶称为边（edge），

即(Vi,Vj)=(Vj,Vi)，其图称为无向图。<Vi,Vj>—有序的对偶称为弧（arc），

即<Vi,Vj>≠<Vj,Vi>，称Vi为弧尾（tail）或起始点，称Vj为弧头（head）或终端点，该图称为有向图。8无向图：边用(x,y)表示，且顶点x与y是无序的。V(G2)={A,B,C}E(G2)={(A,B),(B,C),(C,A)}

={(B,A),(C,B),(A,C)}ABC无向图G2有向图：边用<x,y>表示，且x与y是有序的。a)有向图中的边又称为“弧”

b)x:弧尾或弧的起始顶点；y:弧头或弧的终止顶点V(G1)={A,B,C}E(G1)={<A,B>,<B,A>,<B,C>,<A,C>}ABC有向图G19

（1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或<vi，vj>是E(G)中的一条边，则要求vi≠vj；（2）一对顶点间不能有相同方向的两条有向边；（3）一对顶点间不能有两条无向边。图的说明V0V1V2V3V4V0V1V2V3V4V0V1V2V3数据结构中讨论的都是简单图10

1）顶点的数目n与弧或边的数目e的关系：无向图：0≤e≤n(n-1)/2e=0：任意两顶点之间都没有边

e=n(n-1)/2：任意两顶点之间都有边，称为无向完全图。有向图：0≤e≤n(n-1)e=0：任意两顶点之间都没有弧

e=n(n-1)：任意两顶点之间都有弧，称为有向完全图。V0V1V2V3V0V1V2112）稀疏图：有很少条边的图（e<nlogn）稠密图：e>=nlogn的图3）子图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’

E,则称图G’是图G的子图。ABC有向图G1ABC有向图G1的子图G1’ABC无向图G2ABC无向图G2的子图G2’12v1v2v3v4（a）无向完全图G3子图示例v1v2v4v2v3v4v1v2v3v4无向图G3的部分子图13v1v2v3v4（b）有向完全图G4v1v4v2v3v4v1v1v3v2v4完全有向图G4的部分子图子图示例144）邻接点无向图：若边（Ｖi，Ｖj）∈E(G)则称Ｖi和Ｖj相互邻接，两个顶点互为邻接点，并称边（Ｖi，Ｖj

）关联于顶点Ｖi和Ｖj或称边（Ｖi，Ｖj

）与顶点相关联。有向图：边<Ｖi，Ｖj>∈E(G)则称Ｖi邻接到Ｖj

，或称Ｖj邻接于Ｖi，并称边<Ｖi，Ｖj>关联于顶点Ｖi和Ｖj

，或称边<Ｖi，Ｖj>与顶点Ｖi和Ｖj相关联。ABC无向图G1ABC有向图G215不同结构中逻辑关系的对比FECBAD线性结构ABCDEF树结构V0V1V2V3V4图结构在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。16FECBAD线性结构ABCDEF树结构V0V1V2V3V4图结构在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。不同结构中逻辑关系的对比17

5）度，出度和入度有向图

顶点v的入度ID(v)：以该顶点为终点的弧的数目；

顶点v的出度OD(v)：以该顶点为起点的弧的数目；

顶点v的度D(v)：D(v)=ID(v)+OD(v)；无向图

顶点v的度D(v)：与该顶点相关联的边的数目；ABC有向图G1ABC无向图G2ID(A)=1OD(A)=2D(A)=3D(A)=2D(B)=2D(C)=218顶点的度与弧的关系对于一个有向图或无向图，如果具有n个顶点，e条边（弧），且每个顶点的度为D(Vi)(1=<i<=n)，则存在以下关系：注：图中的每条边均关联于两个顶点ABC有向图G1ABC无向图G2196）权与网如果图的边或弧具有一个与它相关的数时，这个数就称为该边或弧的权。这个数常常用来表示距离或耗费。若将图的每条边都赋上一个权，则称这种带权图为网络，简称为网。V0V1V3V234567825V0V2V1455064（a）无向网络G1

（b）有向网络G220哈夫曼树中的权与网图的权有何区别？V0V1V2V327857423217）路径与回路在图G＝(V,E)中，若从顶点vi

出发，沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vi，vp1，vp2，...vpm，vj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。V0到V3的路径：V0V3

V0

V1V2V3

V0

V1V4V2V3V0V1V2V3V4一般情况下，图中的路径不唯一22路径长度:非带权图的路径长度是指此路径上边/弧的条数。带权图的路径长度是指路径上各边/弧的权之和。V0V1V2V3V4V0V3：路径长度为1V0V1V2V3：路径长度为3V0V1V4V2V3：路径长度为4V0V3：路径长度为8V0V1V2V3：路径长度为7V0V1V4V2V3：路径长度为15V0V1V2V3V425632823

简单路径：若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路：若路径上第一个顶点v1与最后一个顶点vm重合（路径长度≥2）,则称这样的路径为简单回路或简单环。

例如：

a:（0，1，3，2）是简单路径；

b:（0，1，3，0，1，2）是非简单路径；

c:（0，1，3，0）是简单回路。0132a简单路径0132b非简单路径0132c回路24

有根图：在一个有向图中，若存在一个顶点v，从该顶点有路径可到达图中其它的所有顶点，则称这个有向图为有根图，v称为该图的根。V0V1V2V3278525

8）连通图连通：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。连通图：如果图中任意一对顶点都是连通的,则称此图是连通图。连通分量：非连通图的极大连通子图叫做连通分量。1.含有极大顶点数；2.依附于这些顶点的所有边。V0V1V2V3V426

例：非连通图及其连通分量示例V1V2V4V5V3（a）非连通图V1V2V4V5V3（b）G5的两个连通分量H1和H227强连通图：在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。强连通分量：非强连通图的极大强连通子图叫做强连通分量。ABCa：强连通图ABCDEb：非强连通图ABCDEc：（b）图的两个强连通分量28根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连通分量。例如，右图所示的有向图G4是一个具有4个顶点的强连通图。v1v2v3v4有向完全图G4

v1v2v3v4（a）非强连通图G6下图（a）所示的有向图G6不是强连通图（v2、v3、v4没有到达v1的路径），它的两个强连通分量H3与H4如图下图（b）所示。v1v2v3v4（b）G6的两个强连通分量H3和H4

299）生成树，生成深林生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。多——构成回路少——不连通含有n-1条边30V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成树生成森林317.2图的存储结构图的存储结构至少要保存两类信息：

1)顶点的数据

2)顶点间的关系约定:G=<V,E>是图,V={v0,v1,v2,…vn-1},设顶点的下标为它的编号。如何表示顶点间的关系？V0V1V2V3V4V0V1V2V37.2图的存储结构32由于图结构中任意两个顶点之间都可能存在“关系”，因此无法以简单的顺序存储映象表示这种关系。常用的图的存储方法邻接矩阵邻接链表十字链表多重链表337.2.1邻接矩阵图的邻接矩阵表示法，也称为数组表示法。它采用两个数组来表示图。顶点表:一个存储各个顶点信息的一维数组。邻接矩阵：一个存储各个顶点之间的关系（边或弧）的二维数组。设图G=(V,E)是一个有n个顶点的图，则图的邻接矩阵A[n][n]定义为：A[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它34无向图的邻接矩阵的特点？无向图的邻接矩阵V0V2V3V1V0V1V2V3vertex=0101101101001100A=V0V1V2V3V0V1V2V3主对角线为0且一定是对称矩阵。顶点表

邻接矩阵35无向图的邻接矩阵V0V2V3V1如何求顶点i的度？邻接矩阵的第i行（或第i列）非零元素的个数。V0V1V2V3vertex=0101101101001100A=V0V1V2V3V0V1V2V3顶点表

邻接矩阵0101101101001100A=V0V1V2V3V0V1V2V336无向图的邻接矩阵V0V2V3V1如何判断顶点Vi

和Vj

之间是否存在边？测试邻接矩阵中相应位置的元素A[i][j]是否为1。V0V1V2V3vertex=顶点表

邻接矩阵0101101101001100A=V0V1V2V3V0V1V2V337无向图的邻接矩阵V0V2V3V1如何求顶点i的所有邻接点？将数组中第i行元素扫描一遍，若A[i][j]为1，则顶点j为顶点i的邻接点。V0V1V2V3vertex=顶点表

邻接矩阵38有向图的邻接矩阵V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。39有向图的邻接矩阵V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何求顶点i的出度？邻接矩阵的第i行元素之和。40有向图的邻接矩阵V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何求顶点i的入度？邻接矩阵的第i列元素之和。41有向图的邻接矩阵V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何判断顶点i和j之间是否存在边？测试邻接矩阵中相应位置的元素A[i][j]是否为1。42

约定：顶点的“第一个”邻接点：该顶点所对应的行中值为非零元素的最小列号所代表的顶点，其“下一个”邻接点就是同行中离它次最近的值为非零元素的列号所代表的顶点。例如有向图G1中顶点V0的第一个邻接点为"顶点V1"，下一个邻接点是"顶点V2"。V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V343网络，邻接矩阵元素A[i,j]可按以下规则取值：网络的邻接矩阵表示A[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V0V1V2V32785025∞∞0∞

∞

∞

∞087∞∞0A=V0V1V2V3V0V1V2V344当一个图用邻接矩阵表示时，可用以下数据类型来定义：#define n图的顶点数

#define e图的边数

typedefcharvextype;//顶点的数据类型

typedeffloatadjtype;//顶点权值的数据类型

typedefstruct

{

vextypevexs[n];//顶点数组

adjtypearcs[n][n];//邻接矩阵

}graph;顶点表和邻接矩阵中结点的数据类型45无向网络邻接矩阵建立算法:voidCreatGraph(graphg)//建立无向网络{inti,j,k;floatw;

for(i=0;i<n;i++)

g->vexs[i]=getchar();//读入顶点信息，建立顶点表

for(i=0;i<n;i++)

for(j=0;j<n;j++)g->arcs[i][j]=0;//邻接矩阵初始化

for(k=0;k<e;k++)

{scanf(“%d,%d,%f”,&i,&j,&w);//读入边(vi,vj)上的权wg->arcs[i][j]=w;//写入邻接矩阵

g->arcs[j][i]=w;

}}//CreatGraph时间复杂度O(n2+e），由于e<<n2,所以时间复杂度是O(n2)建立无向图，可以在算法中直接对邻接矩阵的元素赋1建立有向网络，只须将写入矩阵的两个语句中的后一个语句g->arcs[j][i]=w去掉即可467.2.2邻接表邻接表存储的基本思想对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表）。所有边表的头指针和存储顶点信息的一维数组构成了顶点表。图的邻接矩阵存储结构的空间复杂度？如果为稀疏图，会出现什么现象？

假设图G有n个顶点e条边，则存储该图需要O(n2)477.2.2邻接表邻接表包括：（1）顶点表；（2）邻接链表邻接表存储方法是一种顺序存储（顶点表）与链式存储（邻接链表）相结合的存储方法。

顶点表：顶点信息和单链表的头指针一起存储在一个一维数组中。一维数组要想表示两类数据类型(顶点信息和头指针)，则必须定义成结构体的数组。

邻接链表：将和同一顶点“相邻接”的所有邻接点链接在一个单链表中。48顶点表和邻接链表中结点的数据类型typedefcharvextype;//定义顶点数据信息类型；typedefstructnode//邻接链表结点，也叫弧结点的结构；{

int

adjvex;//邻接点域，该弧所指向的顶点的位置/下标；

structnode*next;//链域，指向下一条弧的指针；

}edgenode;

typedefstruct//顶点的结构

{

vextype

vertex;//顶点域，放置顶点信息；

edgenode

*link;//指针域，指向第一条依附于该顶点的弧

}vexnode;vexnodega[n];//顶点表49顶点表和邻接链表中结点的数据类型邻接表有两种结点结构：顶点表结点和邻接链表结点vertexlink

adjvex

next

顶点表邻接链表vertex：数据域，存放顶点信息。link：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。50边表，出边表，入边表边表：对于无向图，Vi的邻接链表中每个结点都对应与Vi相关联的一条边，所以将此邻接链表称为边表。出边表：对于有向图，Vi的邻接链表中每个结点都对应于以Vi为起始点射出的一条边（弧），所以有向图的邻接链表也称为出边表。入边表：有向图还有另外一种表示法，叫入边表。即Vi邻接链表中的每个结点对应于以Vi为终点的一条边。51103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。顶点表边表52103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1无向图的邻接表如何求顶点i的度？顶点i的边表中结点的个数。顶点表边表顶点v的度D(v)：与该顶点相关联的边的数目53103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1无向图的邻接表如何判断顶点i和顶点j之间是否存在边?测试顶点i的边表中是否存在终点为j的结点。(或测试顶点j的边表中是否存在终点为i的结点。)顶点表边表54有向图的邻接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何求顶点i的出度？顶点i的出边表中结点的个数。顶点表出边表55有向图的邻接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何求顶点i的入度？各顶点的出边表中以顶点i为终点的结点个数之和。顶点表出边表56有向图的邻接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何判断顶点i和顶点j之间是否存在边?搜索两个结点对应的单链表顶点表出边表57网图的邻接表V0V1V2V3278521V0V1

V2V30123vertexlink∧52∧83∧70∧边表中，添加一个“权值域”58无向图邻接表的建立算法1.确定图的顶点个数和边的个数；2.输入顶点信息，初始化该顶点的边表；3.依次输入边的信息并存储在边表中；

3.1输入边所依附的两个顶点的序号i和j；

3.2生成邻接点序号为j的边表结点s；

3.3将结点s插入到第i个边表的头部；

3.4生成邻接点序号为i的边表结点s；

3.5将结点s插入到第j个边表的头部；59建立邻接表的主要操作是在链表中插入一个结点，以下是输入图的顶点和边建立邻接表的算法。

voidCreatgraphlist(vexnodega[])//建立无向图的邻接表{inti,j,k;

edgenode

*s;

for(i=0;i<n;i++)

{ga[i].vertex=getchar();

//读入顶点信息

ga[i].link=NULL;

//对边表的头指针初始化

}//顶点表初始化顶点表数组的基地址无向图邻接表的建立算法60for(k=0;k<e;k++)//采用头插法建立边表{scanf(“%d%d”,&i,&j);//读入边(vi,vj)的顶点序号（数组下标）

s=(edgenode*)malloc(sizeof(edgenode));//生成邻接点序号为j的边表结点s

s->adjvex=j;

s->next=ga[i].link;//①将s插入顶点vi的边表头部

ga[i].link=s;//②

s=(edgenode*)malloc(sizeof(edgenode));//生成邻接点序号为i的边表结点s

s->adjvex=i;

s->next=ga[j].link;

//①将s插入顶点vj的边表头部

ga[j].link=s;//②

}}//Creatgraphlist时间复杂度O(n+e)12V0V1

V2V30123∧∧∧∧①②s邻接表的建立算法说明对于无向图，每输入一条边需要生成两个结点，分别插入在这条边的两个顶点的链表中。即无向图的邻接表中边结点的个数为图中边的数目的两倍。对于有向图，邻接表中弧结点的个数与图中边的数目相等。61图的存储结构的比较:邻接矩阵和邻接表62O(n2)O(n+e)O(n2)O(n+e)空间性能时间性能适用范围唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一7.3图的遍历图的遍历是指从图中某一顶点出发，沿着某条搜索路径使图中每个顶点仅被访问一次。图的遍历操作要解决的关键问题

①在图中，如何选取遍历的起始顶点？解决方案：从编号小的顶点开始。在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。6364②从某个起点始可能到达不了所有其它顶点，怎么办？

解决方案：多次调用从某顶点出发遍历图的算法。仅讨论从某顶点出发遍历图的算法。③因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环?解决方案：附设访问标志数组visited[n]。④在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？解决方案：深度优先遍历和广度优先遍历。7.3.1深度优先搜索遍历基本思想

：⑴访问顶点v；⑵从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；⑶重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。65深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?深度优先搜索遍历V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5

V5栈深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8

V8深度优先搜索遍历栈深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8深度优先搜索遍历栈深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1

V7V2V4V5V8V3

V3V6

V6V7深度优先搜索遍历栈7.3.1深度优先搜索遍历对于一个图，按深度优先搜索遍历先后顺序得到的顶点序列称为图的深度优先搜索遍历序列（简称DFS序列,depth-firstsearch）。一个图的DFS序列并不唯一，它与遍历算法（选择Vj的原则）、图的存储结构和初始出发点有关。707.3.1深度优先搜索遍历从顶点V0出发的深度遍历序列：

A、B、C、E、D从顶点V1出发的深度遍历序列：

B、A、D、E、C从顶点V2出发的深度遍历序列：

C、B、A、D、E717.3.1深度优先搜索遍历当确定了按照邻接点的序号从小到大进行选择邻接点时，确定了初始出发点，同时邻接矩阵或者邻接表也确定后，DFS就唯一了。对于邻接表存储，也就是要确定邻接表中结点的链接次序。727.3.1深度优先搜索遍历DFS:ABCED7373顶点表边表/邻接链表

A

B

C

D

1

3

1

0

4

0

E

0

2

4

1

∧

∧

∧

∧

∧

74邻接矩阵作为图的存储结构，深度优先遍历算法：intvisited[n];//定义visited为全局变量，n为顶点数graphg;//g为全局变量voidDFSA(inti)//从vi出发深度优先搜索图g，g用邻接矩阵表示{intj;printf(“node:%c\n”,g.vexs[i]);//访问出发点vi

visited[i]=1;//标记vi已被访问

for(j=0;j<n;j++)//按顶点序号从小到大依次搜索vi的某个邻接点

if((g.arcs[i][j]==1)&&(visited[j]==0))

DFSA(j);//若vi的邻接点vj未被访问过，则从vj出发进行深度优先搜索遍历}//DFSA时间复杂度O(n2)75邻接表作为图的存储结构，深度优先搜索遍历算法：voidDFSL(inti)//从vi出发深度优先搜索遍历图ga，用邻接表表示{edgenodep;

printf(“node:%c\n”,ga[i].vertex);//访问顶点vi

visited[i]=1;//标记vi已被访问

p=ga[i].link;//取vi的边表头指针

while(p!=NULL)//依次搜索vi的邻接点

{if(visited[p->adjvex]==0)

DFSL(p->adjvex);//从vi的未曾访问过的邻接点出发进行深度优先遍历

p=p->next;

}}//DFSL

时间复杂度O(n+e)注：由于图的邻接表表示不唯一，所以DFSL算法得到的DFS序列也不唯一。7.3.2广度优先搜索遍历基本思想：⑴访问顶点v；⑵依次访问v的各个未被访问的邻接点v1,v2,…,vk；⑶分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。(4)直至图中所有与顶点v有路径相通的顶点都被访问到。767.3.2广度优先搜索遍历注：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。和树的广度优先搜索一样，用队列实现。7778广度优先搜索遍历的顺序和结束条件:根据广度遍历思想，先遍历的结点，其相邻结点一定首先被遍历。

故采用队列来构造遍历顺序。对于连通图，结束条件是队列为空；对于非连通图，结束条件是队列为空并且图的所有结点都被遍历。7.3.2广度优先搜索遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V1广度优先搜索遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3广度优先搜索遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5广度优先搜索遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7广度优先搜索遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8广度优先搜索遍历84BFSA：以邻接矩阵为存储结构时的广度优先搜索遍历算法。BFSL：以邻接表为存储结构时的广度优先搜索遍历算法。一个图的BFSA和BFSL序列都不唯一，它与算法、存储结构和初始出发点有关。当确定了按照序号（下标）从小到大的方式进行选择邻接点，确定了初始出发点后，以邻接矩阵作为存储结构得到的BFSA就唯一了。当采用邻接表存储时还必须确定边表结点的链接次序，BFSL才唯一。85邻接矩阵作为图的存储结构，广度优先搜索遍历算法如下：voidBFSA(intk)//从vk出发广度优先搜索遍历图g，g用邻接矩阵表示{ int i,j;

SETNULL(*sq);//sq置为空队

printf(“%c\n”,g.vexs[k]);//访问出发点vk

visited[k]=1;//标记vk已被访问

ENQUEUE(*sq);//访问过的顶点序号入队,为访问它的邻接点作准备

while(!EMPTY(*sq))//队非空时执行下列操作

{i=DEQUEUE(*sq);//队头元素序号出队

for(j=0;j<n;j++)//

if((g.arcs[i][j]==1)&&(visited[j]!=1))

{printf(“%c\n”,g.vexs[j]);visited[j]=1;

ENQUEUE(sq,j);//访问过的顶点入队

}//按顶点序号从小到大的顺序，访问未曾访问的vi的邻接点vj

}}//BFSA86邻接表作为图的存储结构，广度优先搜索遍历算法如下：voidBFSL(intk)//从vk出发广度优先搜索遍历邻接表图ga{ inti;edgenodep;

SETNULL(sq);//置空队

printf(“%c\n”,ga[k].vertex);//访问出发点vk

visited[k]=1;//标记vk已被访问

ENQUEUE(sq,k);//访问过的顶点序号入队,为访问它的邻接点作准备

while(!EMPTY(sq))

{i=DEQUEUE(sq);//队头元素序号出队

p=ga[i].link;//取vi的边表头指针

while(p!=NULL)//依次搜索vi的邻接点

{if(visited[p->adjvex]!=1)//vi的邻接点未曾访问

{printf(“%c\n”,ga[p->adjvex].vertex);

visited[p->adjvex]=1;

ENQUEUE(sequeue*sq,p->adjvex);//访问过的顶点入队

}p=p->next;

}

}}//BFSL87图的广度优先遍历实例:以下图为例说明，从结点A开始ADBCEFG01324560123456visited[]queue初始状态frADBCEFG01324560123456visited[]queuefr访问开始结点A，并将A的序号入队10r880123456visited[]1queue0fr0123456visited[]1queue0frfADBCEFG0132456ADBCEFG0132456A的序号出队，同时访问其所有的邻接点：B,C并将B,C的下标按照次序依次入队1rr2111211序号为1的B出队，同时访问其所有的邻接点：D,E并将D,E的下标按照次序依次入队f11rr34890123456visited[]1queue0ADBCEFG01324561211序号为2的C出队，同时访问其未被访问的邻接点：F并将F的下标按照次序依次入队f11r34f1r50123456visited[]1queue0ADBCEFG01324561211序号为3的D出队，D邻接点B已访问过，不执行入队操作1134f1r5f900123456visited[]1queue0ADBCEFG01324561211序号为4的E出队同时访问其未被访问的邻接点：G并将G的下标按照次序依次入队11341r5ff1r60123456visited[]1queue0ADBCEFG01324561211序号为5的F出队F邻接点C，G已访问过，不执行入队操作113415f1r6f910123456visited[]1queue0ADBCEFG01324561211序号为6的G出队G的邻接点E,F已访问过，不执行入队操作1134151r6ff此时，队列已空。搜索过程结束。根据访问的顺序，得到的BFS序列为A，B，C，D，E，F，G7.4生成树和最小生成树树：图论中的树是指一个没有回路的连通图。生成树：一个连通图G的生成树指的是一个包含了G的所有顶点的树，是一个具有n个顶点n-1条边的极小连通子图.92多——构成回路少——不连通含有n-1条边V0V1V2V3V4V0V1V2V3V4生成树7.4生成树和最小生成树构造无向图的生成树的方法：

给定一个无向连通图G，从G的任意顶点Vi出发，作一次深度优先或广度优先搜索遍历，遍历过程中所经历过的n-1条边就构成了G的生成树，顶点Vi是生成树的根。937.4生成树和最小生成树94

深度优先搜索生成树（DFS生成树）

广度优先搜索生成树（BFS生成树）生成树连通图的生成树不是唯一的，它取决于遍历算法和遍历的起始顶点。在遍历算法确定之后，从不同顶点出发进行遍历得到的生成树可能不同。对于非连通图，生成的是包含若干棵树的森林。95邻接矩阵作为图的存储结构，构造DFS生成树的算法intvisited[n];//定义visited为全局变量，n为顶点数

graph*g=(graph*)malloc((sizeof(graph));//产生图的存储空间voidDFSA(inti)//从vi出发，构造*g的DFS生成树{intj;printf(“node:%c\n”,g->vexs[i]);//访问出发点vi

visited[i]=1;//标记vi已被访问

for(j=0;j<n;j++)//按顶点序号从小到大依次搜索vi的某个邻接点

if((g->arcs[i][j]==1)&&(visited[j]==0)){printf(“(v%d,v%d)\n”,i,j);//输出边（vi，vj）

DFSA(j);}//若vi的邻接点vj未被访问过，则从vj出发进行深度优先搜索遍历}//DFSA96邻接矩阵作为图的存储结构，构造BFS生成树的算法voidBFSA(intk)//从vk出发广度优先搜索遍历图g，g用邻接矩阵表示{ int i,j;

SETNULL(*sq);//sq置为空队

printf(“%c\n”,g.vexs[k]);//访问出发点vk

visited[k]=1;//标记vk已被访问

ENQUEUE(*sq);//访问过的顶点序号入队,为访问它的邻接点作准备

while(!EMPTY(*sq))//队非空时执行下列操作

{i=DEQUEUE(*sq);//队头元素序号出队

for(j=0;j<n;j++)//if((g.arcs[i][j]==1)&&(visited[j]!=1))

{printf(“(v%d,v%d)\n”,i,j);//输出边（vi，vj）

printf(“%c\n”,g.vexs[j]);visited[j]=1;

ENQUEUE(sq,j);//访问过的顶点入队

}//按顶点序号从小到大的顺序，访问未曾访问的vi的邻接点vj

}}//BFSA例：从顶点A出发的DFS生成树和BFS生成树。977.4生成树和最小生成树ABDCEABDCEDFS生成树ABDCEBFS生成树98最小生成树的应用背景：例1：由于在n个居民点间构建通讯网只需架设n-1条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？

例2：n个城市之间铺设煤气管道问题等。类似此类的问题很多。这些问题均等价于，在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小的问题。7.4生成树和最小生成树最小生成树（MST）：对一个连通网络构造生成树，可以得到一棵带权的生成树。我们把生成树各边的权值总和作为生成树的权值，而具有最小权值的生成树就是连通网络的最小生成树。构造准则:尽可能用网络中权值最小的边；必须使用且仅使用n-1条边来连接网络中的n个顶点；不能使用产生回路的边。997.4生成树和最小生成树构造最小生成树的两种算法1.prim（普里姆）算法2.Kruskal(克鲁斯卡尔)算法1007.4生成树和最小生成树1017.4.2prim（普里姆）算法设G(V,E)是有n个顶点的连通网络，T=(U,TE)是要构造的生成树。初始时U={φ}，TE={φ}。首先从V中取出一个顶点u0放入生成树的顶点集U中作为第一个顶点(根结点），此时T=({u0},{φ})；然后从uU，vV-U的边(u,v)中找一条代价最小的边(u*,v*)放入TE中，且将v*放入U中，此时T=({u0,v*},{(u0,v*)})；重复（2），直到U=V为止。这时T的TE中必有n-1条边，构成所要构造的最小生成树。关键:是如何找到连接U和V-U的最短边。102在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。

一般情况下所添加的顶点应满足下列条件:UV-U103Prim算法构造最小生成树实例以下图为例说明构造过程，从顶点0开始801234510321117657V012345UV-U012345TE801234510321117657V012345U0V-U12345TE0,220104801234510321117657V012345U02V-U1345TE0,2801234510321117657V012345U024V-U135TE0,22,42,42,141105801234510321117657V012345U0241V-U35TE0,22,42,14,3801234510321117657V012345U02413V-U5TE0,22,42,14,33,535106801234510321117657V012345U024135V-UTE0,22,42,14,33,5012345321157107显然，prim算法的关键是如何找到连接U和V-U的最短边来扩充T。设当前生成树T中已有K个顶点，则U和V-U中可能存在的边数最多为K（n-K）条，在如此多的边总寻找一条代价最小的边是困难的。由于寻找过程具有可重复性，所以可通过将前一次所寻找得到的最小边存储起来，然后与新找到的边进行比较，如果新边短，则替换，否则不替换。7.4.2prim（普里姆）算法1087.4.2prim（普里姆）算法边的存储结构：typedefstruct{intfromvex,endvex;//边的起点和终点

floatlength;//边的权值}edge;edge

T[n-1];//最小生成树，有n-1条边图的存储结构：由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储。float

dist[n][n];//连通网络的带权邻接矩阵109算法7.7最小生成树的Prim算法。voidPrim(inti) //i表示最小生成树所选取的第一个顶点下标{intj,k,m,v,min,max=100000;

floatd;

edgee;v=i; //将选定顶点送入中间变量vfor(j=0;j<=n-2;j++) //构造第一个顶点

{T[j].fromvex=v;if(j>=v)

{T[j].endvex=j+1;T[j].length=dist[v][j+1];}else

{T[j].endvex=j;T[j].length=dist[v][j];}}7.4.2prim（普里姆）算法11001234500103∞∞∞1100586∞2350∞2∞3∞8∞07114∞6270175∞∞∞11170邻接矩阵dist[6][6];fromvexendvexlength01234T[5],n=60000012435103∞∞∞V=0;801234510321117657111for(k=0;k<n-1;k++)//求第k条边{

min=max;for(j=k;j<n-1;j++)//找出最短的边，并将最短边的下标记录在m中

{if(T[j].length<min)

{min=T[j].length;m=j;}}e=T[m];T[m]=T[k];T[k]=e;//将最短的边交换到T[k]单元中v=T[k].endvex;//存放新找到的最短边在V-U中的顶点

for(j=K+1;j<n-1;j++)//修改所存储的最小边集

{d=dist[v][T[j].endvex];

if(d<T[j].length)

{T[j].length=d;T[j].fromvex=v;}}}}fromvexendvexlength01234112T[5],n=60000012435103∞∞∞max=10000;min=max;min=T[j].length<min?T[j].length:min;k=0;m=j;V=T[k].endvex=2V=0;113fromvexendvexlength012340000021435310∞∞∞k=0;d=dist[v][T[j].endvex]j=K+1,K+2,…,n-2V=2if(d<T[j].length)

{T[j].length=d;T[j].fromvex=v;}25d[2][1]=5新起点可能的终点d[2][3]=∞d[2][4]=222d[2][5]=∞修改存储的最小边集T[5],n=6114fromvexendvexlength01234000214353∞∞k=1;2522T[5],n=6时间复杂度O(n2)，与网的边数无关。适合边稠密网络的最小生成树1157.4.3Kruskal(克鲁斯卡尔)算法克鲁斯卡尔算法的基本思想：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小。自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。1167.4.3Kruskal(克鲁斯卡尔)算法具体作法如下：首先构造一个只含n个顶点的森林V；然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去直至该森林变成一棵树为止这棵树便是连通网的最小生成树。

117

问题：由于生成树上不允许有回路，因此并非每一条当前权值最小的边都可选。那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通？从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树（连通分量）上即可。

7.4.3Kruskal(克鲁斯卡尔)算法118V012345TE21041321856101961451133041325初始连通分量T=（V,TE）0413255V012345TE加入（1,2）后的连通分量21041321856101961451133（1,2）119由于(2,3)和(1,3)的权值都是6，因此可以加入(2,3)或者(1,3)V012345TE（1,2）加入（2,3）后的连通分量2104132185610196145113304132556(2,3)V012345TE（1,2）（2,3）加入（0,5）后的连通分量210413218561019614511330413255610(0,5)120V012345TE（1,2）（2,3）（0,5）加入（1,5）后的连通分量21041321856101961451133041325561011V01234