大二上学期学习第

第五章

图基本概念图的存储结构图的遍历拓扑排序关键路径最短路径最小支撑树图的应用5.5.1基本概念边表示活动(Activity)边的权值表示活动的持续时间(Duration)顶点表示入边的活动已完成，出边的活动可以开始的状态，也称为事件(Event)这样的有向无环的带权图叫做AOE

(Activity

On

Edges)网。[例]某工程源点：表示整个工程的开始（入度为零）。汇点：表示整个工程的结束（出度为零）。完成整个工程至少需要多少时间？为缩短工程的时间，应当加快哪些活动？23

5140867a6=2a2=4汇点源点从源点到各顶点的路径可能不止一条，路径长度也可能不同。只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。路径长度：指路径上的各边权值之和。关键活动：关键路径上的活动。4081

676a

=2a2=4

23

5汇点源点关键活动有关的量：①事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。②事件vj的最迟发生时间vl(j):保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟发生时间，等于ve(n-1)减去从vj到vn-1最长路径长度。54081

67a6=2a2=4

23汇点源点ve(0)=0ve(1)=

6ve(2)=

4ve(3)=

5ve(4)=

7ve(5)=

7ve(6)=

16ve(7)=

14ve(8)=

18vl(8)=

18vl(7)=

14vl(6)=

16vl(5)=

10vl(4)=

7vl(3)=

8vl(2)=

6vl(1)=

6vl(0)=

0关键活动有关的量：③活动ai的最早开始时间e(i):设活动ai在有向边<vj

,vk

>上，则e(i)=ve(j)；④活动ai的最迟开始时间l(i):l(i)

是在不会引起时间延误的前提下，该活动允许的最迟开,vk

>上,

则

l(i)=vl(k)-50867a6=2a2=4

23汇点始时间。设活动ai

在有向边<

vjweight(<j,

k>)1源点4aia1a2a3a4a5a6a7a8a9a10a11e(i)0006457771614l(i)02366877101614关键活动：l(i)＝

e(i)表示活动ak是没有时间余量的关键活 动。23

54081

67a6=2a2=4汇点源点为找出关键活动,需要求各个活动的e(i)

与l(i)，以判别是否l(i)＝

e(i)为求得e(i)

与l(i)，需要先求得从源点V0到各个顶点Vj的ve(j)和vl(j)。5.5.2

求关键活动算法求关键活动的基本步骤：①对AOE网进行拓扑排序，按拓扑次序求出各顶点事件的最早发生时间ve，若网中有回路，则终止算法；②按拓扑序列的逆序求各顶点事件的最迟发生时间vl;③根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则i是关键活动。[例]

求关键活动

––

第1步ve(k)max{ve(j)+

weight(<j

,

k>)}<vj

,

vk>∈E(G),

k=1,2,

…,n-15140867a6=2汇点源点a2=4

23按拓扑正序递推:ve(0)＝0

k=0ve(0)=0ve(1)=

ve(0)+weight(<0,1>)=0+6=6ve(2)=

ve(0)+weight(<0,2>)=0+4=4ve(3)=

ve(0)+weight(<0,3>)=0+5=5ve(4)=

max{ve(1)+

weight(<1

,4>)，ve(2)+

weight(<2

,4>)}=max{6+1,4+1}=7ve(5)=

ve(3)+weight(<3,5>)=5+2=7ve(6)=

ve(4)+weight(<4,6>)=7+9=16ve(7)=

max{ve(4)+

weight(<4,7>)，ve(5)+

weight(<5,7>)}=max{7+7,7+4}=14ve(8)=

max{ve(6)+

weight(<6,8>)，ve(7)+

weight(<7,8>)}=max{16+2,14+4}=18[例]

求关键活动––

第2步vl(j)min{vl(k)-

weight(<j,

k>)}<vj

,

vk>∈E(G), j=n-2,n-3,…,0325140867a6=2a2=4汇点源点按拓扑逆序递推:ve(n-1) j=n-1vl(8)=

ve(8)=18vl(7)=

vl(8)-weight(<7,8>)=18-4=14vl(6)=

vl(8)-weight(<6,8>)=18-2=16vl(5)=

vl(7)-weight(<5,7>)=14-4=10vl(4)=

min{vl(7)-

weight(<4

,7>)，vl(6)-

weight(<4

,6>)}

=min{14-7,16-9}=7vl(3)=

vl(5)-weight(<3,5>)=10-2=8vl(2)=

vl(4)-weight(<2,4>)=7-1=6vl(1)=

vl(4)-weight(<1,4>)=7-1=6vl(0)=

min{vl(1)-

weight(<0

,1>)，vl(2)-

weight(<0

,2>),vl(3)-

weight(<0

,3>)}

=

min{6-6,6-4,8-5}=0aia1a2a3a4a5a6a7a8a9a10a11e(i)0006457771614l(i)02366877101614li-ei02302300300[例]求关键活动––第3步：e(i)=ve(j),l(i)=vl(k)-weight(<j,k>)23

5140867a6=2a2=4汇点源点算法CriticalPath()/*

图的关键路径算法*/CPath1[计算事件的最早发生时间]FOR

i

=

1

TO

n

DOve

[i]

‹

0.FOR

i

=1

TO

n–1

DO

/*1)按顶点的拓扑序列计算各事件的最早发生时间*/(

p‹

adjacent(Head

[i])

.WHILE

p

DO(

k

‹VerAdj(p).

//依次考察每条边

IF(ve[i]+cost

(p)>ve[k])THENve[k]

‹

ve[i]

+

cost

(p)

.p‹

link(p)

. )

)/*

2)

按拓扑逆序计算CPath2[计算事件的最迟发生时间]FOR

i

=

1

TO

n

DOvl[i]

‹

ve[n]

.FOR

i

=

n–1

TO

1

STEP

–1

DO事件的最迟发生时间*/(

p‹

adjacent

(Head[i])

.WHILE

p

DO(

k‹

VerAdj(p)

.IF

(vl[k]

–

cost

(p)

<

vl[i]

)

THENvl[i]

‹

vl[k]

–

cost(p).p‹

link(p)

.

)

)CPath3[求诸活动的最早开始时间和最迟开始时间]FOR

i

=

1

TO

n

DO(

p‹

adjacent

(Head

[i]).WHILE

p

DO(

k‹

VerAdj

(p).e‹

ve[i]

.l‹

vl[k]

–

cost(p).IF

l

=

e

THENPRINT

"<

i,

k>

is

Critical

Activity!

"p‹

link(p)))

▐时间复杂性：对定点进行拓扑排序的时间复杂性为O(n+e),

以拓扑排序求ve[i]和以拓扑逆序求vl[i]时,

所需时间为均为O(e),

求各个活动的e[k]和l[k]的时间复杂度为O(e),

整个算法的时间复杂性是O(n+e)。第五章

图基本概念图的存储结构图的遍历拓扑排序关键路径最短路径最小支撑树图的应用5.6

最短路径问题两顶点间可能存在多条路径，各路径的长度不一定相同。从一个指定的顶点到达另一指定顶点的路径上各边权值之和最小的路径被称为最短路径，这类问题亦称为最短路径问题。最短路径问题可分为：单源(由一个指定顶点到其他顶点)最短路径无权最短路径正权最短路径负权最短路径2）每对顶点之间的最短路径问题5.6.1

无权最短路径问题无权——所有边的权值都为1源点到各顶点的路径所经历的边的数目就是路径的长度相对于源点由近及远依次求各顶点的最短路径算法思想：设Di为源点S到顶点i

的最短路径长度V1V63V51①访问初始顶点S，即令DS=0。②从S出发，找最短路径为1的顶点，即S的所有邻接顶点w，令Dw=DS+1③从上步访问的顶点w出发，找最短路径为2的顶点，即w未被访问的邻接顶点v，令Dv=Dw+1④继续上述过程，直至处理完所有顶点。1

22V3V430V2SV0[例]1v0v5v60v2S2v12v33v431V6V5V4V212V12V3330S1V0上述过程中，访问顶点的次序与对图进行广度优先遍历的次序是一致的;初始时，令Dw=-1，当Dw由-1变成一个正整数时，表示从源点到w的最短路径已求完，Dw值就是最短路径长度,实现时使用数组dist[]存储，其涵盖visited[]数组的功能;为了找到最短路径，使用path[]数组，path[i]记录从源点到顶点i的最短路径上最后一个经历的顶点，即顶点i的前驱顶点。Path[V0]=V2Path[V1]=V0Path[V2]=-1Path[V3]=V0Path[V4]=V1Path[V5]=V2Path[V6]=V3算法ShortestPath(v,n)/*

计算从顶点v到其他各顶点的最短路径*/SPath1[初始化]CREATQ(Q). /*

创建一个队列*/FOR

i

=

1

TO

n

DO(path[i]

‹

-1.dist[i]

‹

-1.)dist[v]

‹

0

.Q

v.SPath2[求从顶点v到其他各顶点的最短路径]WHILE

NOT(ISEMTQ(Q))DO(u Q

. /*

队头顶点u出队*/p

‹adjacent(Head[u]). /*

p为u的边链表的头指针*/WHILE

p„L

DO(

k

‹

VerAdj

(p)

.IF

(dist[k]

=

-1)

THEN(

Q

k.

//将u的未访问的邻接顶点入队dist[k]

‹

dist[u]

+

1.path[k]

‹

u)p

‹

link(p)

.

))

▐V1V63V51//修改其p1ath[]值和dis2t[]值2V3V430V2SV0在最短路径的计算中，一个顶点入队出队各一次，时间复杂性为O(n)，而对每个顶点，都要对它的边链表进行遍历，其遍历邻接表的开销为O(e)，于是整个算法的时间复杂性为O(n+e)。5.6.2

正权最短路径问题给定一个带权图D与源点v，求从v到D中其它顶点的最短路径,限定各边的权值为正实数。正权最短路径问题不能采用无权最短路径算法。v0v1v2283Dijkstra算法思想按路径长度非递减的次序，逐步产生最短路径的算法，解决正权单源最短路径问题。首先求出从源点v出发，长度最短的一条最短路径；再参照它求出长度次短的一条最短路径；依此类推，直到求出从顶点

v到其它各顶点的最短路径为止。把图中所有顶点分成两组，第一组：已求完最短路径的顶点；第二组：未求完最短路径的顶点。按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中。为了求最短路径，引入辅助数组dist，dist[i]表示当前找到的源点v0到vi的最短路径长度。初始时：S

={}，dist[0]=0，dist[i]=+¥SV-S设S是已求得最短路径的顶点集合，则：下一条最短路径必然是从源点v0

出发，中间只经过S中的顶点便可到达的那些顶点vx(vx˛

V-S

)的路径中的一条。每次求最短路径，也就是在V-S中找具有最小dist值的顶点vk，将vk加入集合S，然后对vi˛

V-S，修改dist[i]值。经第一次操作，S={v0}，若从源点v0到vi有边，则dist[i]为该边上的权值；若从v0到vi

无边，则dist[i]仍为+¥

。SV-SDijkstra算法描述初始时（S为初始顶点）,Ds=0且"i≠

S，有Di

=＋∞。①在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。②依次考察v的邻接顶点w，若Dv+weight(<v,w>)<

Dw

，则改变Dw的值，使Dw

=Dv

+weight(<v,w>)

。③重复①②，直至所有顶点被访问。为了找到最短路径，使用path[]存储从S到i

的最短路径上最后一个经历的顶点。[例]3104530020125

8234120

01

12

23

34

4∧4

30

∧3

8∧1

32

254

10

∧0

200

52

44

12

∧sdistpath01000000∞∞∞∞3104530020125

823412①在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。②依次考察v的邻接顶点w，若Dv+weight(<v,

w>)<

Dw

，则改变Dw的值，使Dw

=Dv

+weight(<v,w>)。③重复①②，直至所有顶点被访问。2

3

40133043310530020125

823412sdistpath40∞334∞2211000003∞∞30v0v0sdistpath034211100003281130v0v1v1v03258133002343028113104530020125

8234123421sdistpath1101003281130v0v1v1v031040530020125

82341230481315

2323412113421sdistpath1101003151123v0v3v1v331040530020125

82341230481315

232341211048315

2323412113

13104530020125

823412sdistpath1101003151123v0v3v1v3sdistpath411111103151123v0v3v1v3Dijkstra算法:按照非递减顺序依次得到各顶点的最小路径长度。048315

223323412113

131040530020125

823412定理5.4

Dijkstra算法可以按照非递减次序依次得到各顶点的最小路径长度。证明：归纳法算法得到的路径值是各顶点的最小路径长度。算法得到的路径值是按非递减次序得到的。算法DShortestPath(n,

v)/*

计算v到其他各顶点的最短路径*/DSPath1[初始化]FOR

i

=1

TO

nDO(

path[i]‹

-1.dist[i]

‹

max.s[i]‹0.) //数组s[i]表示结点i的最短路径是否已求完dist[v]

‹

0.s[v]

‹

1.u‹v.

//u为刚刚求完最短路径的顶点

p

‹adjacent(Head[u]).DSPath2[求从初始顶点v到其他各顶点的最短路径]FORj

=1TO

n-1

DO(WHILE

p„L

DO

//修改u邻接顶点的path[]值和dist[]值(k‹VerAdj(p).IF

(

s[k]

„1

AND

dist[u]

+

cost(p)

<

dist[k]

)

THEN(

dist[k]

‹

dist[u]

+

cost(p)

.path[k]

‹

u.)p

‹

link(p)

)//在非集合S中，找具有最小dist值的顶点uldist

‹max.FOR

i

=1

TO

nDOIF

(

dist[i]

>

0AND

dist[i]

<

ldist

AND

s[i]

=0

)THEN(

ldist

‹

dist[i]

.

u‹

i.

)s[u]

‹

1.p

‹

adjacent

(Head[u])

)▐//访问u//p为u的边链表的头指针该算法的时间复杂性为O(n2+e)，也可认为是O(n2)5.6.3

每对顶点间的最短路径问题：已知一个各边权值均大于0的带权有向图，对每一对顶点vi

„vj，求vi

与vj间的最短路径和最短路径长度。可依次把每个顶点作为源点，执行n次Dijkstra算法。Floyd算法：定义一个n阶方阵序列：A(-1),

A(0),

…,

A(n-1).Floyd算法的基本思想：设邻接矩阵存储图，定义初始矩阵A(-1)

[i][j]=Edge[i][j]；1、求A(0),即从vi到vj

经由顶点可以是{v0}的最短路径长度；2、求A(1),即从vi

到vj

经由顶点可以是{v0,v1}的最短路径长度；…n、求A(n-1),即从vi

到vj

经由顶点可以是{v0,v1,…,vn-1}的最短路径长度；其中A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][k]

+

A(k-1)[k][j]

},

k

=

0,1,…,

n-1A(0)A(1)A(2)A(3)012

3012

3012

3012301¥

40110

30110

30193¥09

2¥09

21209

211082340

7340

6340

63406¥¥6

0¥¥6

09106

091060Path(0)Path(1)Path(2)Path(3)A(-1)0123001¥41¥092235083¥¥60Path(-1)0123000-101-1011222023-1-130012301230123012300-10001100110031-1011-1011201120312000200120012001-1-130-1A(3)

知，顶点1

到0

的最短路径长度为a[1][0]=11,其最短路径

path[1][0]=2，path[1][2]=3，path

[1][3]=1,表示顶点0‹顶点2

‹顶点3

‹顶点1;从顶点1到顶点0最短路径为<1,

3>,<3,

2>,<2,0>。A(-1)A(0)A(1)A(2)A(3)01230123012301230123001¥401¥4011030110301931¥092¥092¥09212092110822350834073406340634063¥¥60¥¥60¥¥609106091060Path(-1)Path(0)Path(1)Path(2)Path(3)01230123012301230123000000000001100110031100110011001120112031222022000200120012001300300030003022302030//矩阵A和path初始化算法AllLength

(n

)/*

求每对顶点间的最短路径*/ALength1[初始化]FOR

i=0

TO

n-1

DOFOR

j=0

TO

n-1

DO(A[i][j]

‹edge[i][j].//初始化的A即A(-1)IF

(

i„j

AND

A[i][j]

<

max

)

THENpath[i][j]‹

i

.ELSEpath[i][j]

‹

-1.)ALength2[求图中任意两顶点的最短路径]FOR

k=0

TO

n-1

DO

//从A(-1)开始针对每个k逐步构造A(n-1)FOR

i=0

TO

n-1

DOIF

(i„k)

THENFOR

j=0

TO

n-1

DOIF(j

„

k

AND

j

„

i

AND

A[i][k]<max

AND

A[k][j]<maxAND

A[i][k]+A[k][j]<A[i][j])

THEN(

A[i][j]

‹

A[i][k]

+

A[k][j].path[i][j]‹

path[k][j]

.)

▐Floyd算法的时间复杂度为O(n3)，与调用n次Dijkstra算法求每对顶点的最短路径的时间复杂度相同。但Dijkstra算法仅针对正权图，而Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路；且Floyd算法更适用于邻接矩阵存储的图；其更简单易于理解。本章给出的求解最短路径的算法，不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图。第五章

图基本概念图的存储结构图的遍历拓扑排序关键路径最短路径最小支撑树图的应用5.7

最小支撑树1、基本概念2、生成最小支撑树算法

Prim算法

Kruskar算法最小支撑树——基本概念对于一个无向网络——无向加权连通图N=(V,E,C)(C表示该图为权图)，其顶点个数为|V|=n，图中边的个数为|E|，我们可以从它的|E|条边中选出n-1条边，使之满足：这n-1条边和图的n个顶点构成一个连通图。该连通图的代价在满足条件(1)的所有连通图中代价最小。这样的连通图被称为网络的最小支撑树(

Minimum-costSpanning

Tree

)。最小支撑树的性质最小支撑树中没有回路——若MST

的边集中有回路，显然可通过去掉回路中某条边而得到花销更小的MST最小支撑树是一棵有|V|-1条边的树最小支撑树的边集支撑起了图中所有顶点，且边集的代价最小最小支撑树的应用使连接电路板上一系列接头所需焊接的线路最短在n个城市间建立造价最低的通讯网络等。5.7

最小支撑树1、基本概念2、生成最小支撑树算法谱里姆(Prim)算法克鲁斯卡尔(Kruskar)算法定理5.5N

=(V,E,C

)是一个连通网，U是V

的一个非空子集，若(u,v)(u˛

U，v˛

V-U

)满足weight(u,

v)

=

min{

weight(u0,

v0)

|

u0˛

U,

v0˛

V-U}则N

必存在一棵包括边(u,v)的最小支撑树.UV-Uuv581、普里姆(Prim)算法(逐点加入)设N=(V,E,C

)为连通网，TE

是N

的最小支撑树MST的边集，U

为MST

的顶点集.①

U={uo}

(uo˛

V

),

TE=˘

；②找满足//u˛

U,v˛

V-Uweight(u,

v)=min{weight(u1,v1)|u1˛

U,

v1˛

V-U

}的边，把它并入TE，同时v

并入U；③反复执行②，直至V=U.59136455563224157UV-U[例]1360455563224157021136045556032241571360455563224157UV-U024150210532241024151360455563224157UV-U1055322411360455563224157UV-U0532241105532241UV-U136045556322415713045532241假设图用邻接矩阵存储。普里姆算法的实现需要两个辅助数组closedge[n]和TE[n-1]

.closedge[]之元素包括Lowcost和Vex两个域，定义如下:若vˇU,则closedge[v].Lowcost=min{weight(u,v)|u˛

U},closedge[v].Vex=u

,u˛

U.若v˛

U，则closedge[v].Lowcost

=0，closedge[v].Vex

=-1.closedge[]数组存储各点与集合U关联的最小边。数组TE[n-1]是最小支撑树的边集合，每个数组元素TE[i]表示一条边,TE[i]由head、tail

和cost

三个域构成,分别存放边的始点、终点和权值.653215645234132651564556234171311341616423412164523413265156455623417Vclosedge123456UV-UVexLowcost-101611151max1max{1}{2

,3

,4

,5,6}436

552UV-UPrim算法：/*初始1

化*/FOR

i

=

1

TO

n

DO1(

Lowc2ost

(c5losedge7[i])‹4

edge[1][i]

.Vex

(closedg3e[i])

‹

1)Vex

(closedge[1])

‹

-1.count

‹51.//TE6边计6数器Vclosedge123456UV-UVexLowcost-101611151max1max{1}{2

,3

,4

,5

,6}v‹0.

//求当前权值最小的边和该边的终点vmin‹

max.FOR

j

=

1

TO

n

DOIF

(vex

(closedge[j])

≠

-1

ANDLowcost(closedge[j])

<

min

)(

v

‹

j.min

‹

Lowcost

(closedge[j])

)Vclosedge123456UV-UVexLowcost-1016-10151max1max{1,3}{2,

4

,5

,6}If

v„0

THEN

//v加入U中(

head(TE[count])

‹tail

(TE[count])

‹cost

(TE[count])

‹count

‹

count

+1.Vex

(closedge[v]).v.Lowcost(closedge[v])

.//计数器加1Lowcost

(closedge[v])‹0.

//修改域值Vex(closedge[v])‹-1.//顶点v进入集合UVclosedge123456UV-UVexLowcost-1035-10153534{1,3}{2,4

,5,6

}3265156455623417UV-UFOR

j

=1

TO

nDO

//修改某些顶点的值IF(Vex(closedge[j])

„

-1

ANDedge[v][j]

<

Lowcost(closedge[j]))

THEN(

Lowcost(closedge[j])

‹

edge[v][j]

.Vex(closedge[j])

‹

v.)))

)算法Prim()/*无向正权图G包括n个顶点，Prim算法求G的最小支撑树，顶点1

为始点，G用邻接矩阵表示，Prim使用两个数组

closedge[]和TE[]，…*/Prim1[初始化]FOR

i

=

1

TO

n

DO(

Lowcost

(closedge[i])‹

edge[1][i]

.Vex

(closedge[i])

‹

1)Vex

(closedge[1])

‹

-1. //

顶点1进入集合Ucount

‹

1. //

支撑树的边记数器countPrim2[构造图的最小支撑树]FORi

=2

TOnDO//循环n-1次，即TE中共加入n-1条边

(v‹0.

min‹max.//求当前权值最小的边和该边的终点vFOR

j

=1

TO

nDOIF

(vex

(closedge[j])

„

-1

AND

Lowcost(closedge[j])

<

min

)

THENLowcost

(closedge[j])

.

)(

v

‹

j.

min

‹IF

v„0

THEN//若找到权值最小的边，则该边加入TE，点v加入集合Utail

(TE[count])

‹

v.(

head(TE[count])

‹

Vex

(closedge[v])

.cost

(TE[count])

‹count

‹

count

+1.Lowcost(closedge[v])

.//计数器加1Lowcost

(closedge[v])

‹0.

//修改域值Vex(closedge[v])‹-1.

//顶点v进入集合U//修改v的邻接顶点的closedge值FOR

j

=1

TO

nDOIF(Vex(closedge[j])

„

-1

AND

edge[v][j]

<

Lowcost(closedge[j]))

THEN(

Lowcost(closedge[j])

‹

edge[v][j]

.Vex(closedge[j])

‹

v.

))

)▐普里姆算法时间复杂性O(n2)，适用于求边稠密网的最小支撑树。2.

克鲁斯卡尔(Kruskar)算法（逐边加入）设连通网N=(V,E,C

),T

为N

的最小支撑树.初始时TE

=˘

,

T

中无边，即T={V,˘

}只有n

个顶点，可看成n

个连通分量.重复执行如下步骤直至T

中仅剩一个连通分量：①

在E

中选择权值最小的边，并将此边从E

中删除；②

若此边的两个顶点在T

的不同连通分量中,则将此边加入T

中;(导致T

减少一个连通分量)否则本步骤无操作.7311045321045213213045322101345322411304553224140[例]61345563225157普里姆(Prim)算法的时间复杂性为O(n2)，算法适于求边稠密网的最小支撑树。正好相反，克鲁斯卡尔(Kruskar)算法适于求边稀疏网的最小支撑树,其时间复杂性为O(elog2

e).75第五章

图