≥ 弓一 6
西 j 纺 织 工 学 院 学 报
Journal uf Northwest In~tRute of Textile Science and Technology
第 【0卷第 3期(邑3g期) 1996年 9月 Vol·】0，No·3(Sum No·39)
用宽度优先搜索求网络图的最短路径
． 杭省策’ 张选平
／1 摘要 在对珥络瞳变换的基础上引入了简单连通tlt的准生成根树的概念t并由此给出
了求网络圉最短路径的一神新算法．馈算法与以往算法的区别在于它改变了网络图的拓扑
结构，从而使搜索能够在结构非常简单的树状 图上进行．谊算法用最多不超过 lI，l一1层的
关键词 最短路径、准生成根树 、宽度优先搜 索
中图分类号 0 229
0 引言
网
在计算机连同、运输同络的勘察设计、车辆行车路线安排、公用事业和石化工业中各种
管线的铺设、有线通信和有线广播电视网的设计施工等实际问题中，往往需要计算阿络中扶
某 卜漂点(称为中心)出发到其余各点或任意两点同的晟短路径．这类网路优化问题有直接
的经济意 义．
关于单源点最短路径的算法 ，以 E．W．Dijks∞ [959年提 出的算法最为常用，它的时同
复杂性是 O(1 l z)El：．1974年 Wanger采用桶分类法得出的算法，虽然其时j可复杂性 为 0
(1 1)，但仅适用于罔中边的权值是较小整数的情况[I]．而在求网络图中任意两点阐最短路
径的诸多算法中，Floyd】982年提出的算法是一个较好的算法 ，其时I珂复杂性为 0(1 {’)[“+
本文把宽度优先搜索技 术(BFS)应用于网络罔最短路径的寻找，使求单源点最短路径
算法和求任意两点问最短路径算法共甩一个过程实现，且其时同复杂性分别与Dijksrta算法
和 Floyd算法相同．
1 定义
本文所讨论的图均指简单连通罔．由于宽度优先搜索仅适用于树状结构的问题，因此必
须首先对网络图进行变换．
定义 l 设 =( ，西)是图0= ( ， )的子图，如果 包含了G的所有顶点，即若
= ，B c ，则称 为 G的生成子图．
． 锺大学管理学院，71 0049．前安市成宁两路 28号．杭酋策，男． 亨 博 七生
” 西安交通大学计算系．
收祷口期 1096—0{一lg ．
、
＼ 、
，卜
维普资讯
).S三 -).s6 ω
B 北纺织工学院学报
Jnurnal ùf Northwes[ Institute of Texrite Science and TechnoJogy
第 10 卷菇 3 跻4 总 :19 题 1996 年 9 月 γ' Q, No. 3(Sum No. 39)
用宽度优先搜索求网络图的最垣路径
A 主主主且主
摘要 在玲网络11!变换的基础土 s!入 T 简羊迄逗驾始准立或 ill椅给镜念，并由此串岳出
?术网络图采握路泣的一种精算法‘该再法与.:.主算法约 ~B'l在于它~交 τ 鸡络 3自传.ú;~争
结构，从吉尼使搜索能筝在结构非常简单约椅斗是图牛草1: It. 边界法用最F 不超过1V 1-1 层传
扩展，即可找出困苦r从源立出发.f'J 其余顶点或任意离点j司传最短~.{ι
关檀词主主主主、在生成4草树、主主主芝主 司在各段
中国分类号 o 229-'J
o ~I 言
在汁算就连同萄运输;写络的勘察设汁、车辆行李路线安排、公尼事业秘石化工业中各种
音线的铺设、有线通信和有线广播电攫冽的设计施工等实际问题中，往往需要汁算网络中从
某?漂点〈称为中，乙、3 忠发jilJ其余各杰或任建两点肉的最短路径.这类两路优先问题有豆三卖
出经济意义.
关于单漂点最短路径的算法.以 E. W. Dijkstra 1959 年提串的算法最为常用，它的时间
复杂性是叫 I V i ')[C. 19H 年 W四草er 采沼桶分类法得出的算法，虽然其时何复杂性为 O
(1 B 1) ，但汉适用于商中边的权值是绞小整整量的情况∞a 而在求网络阁中任意到或如j最短路
径的诸多算法中 .Floyd 1962 年提串的算法是一个较好的算法，宾时间复杂性为例 IVIη[l'} •
本文把宽度优先搜索技求{密吉〉应用于网络南最短路径的寻找，使求单吉I(~史最短路径
算法和求任意勇点向最短路径赛法共用一个过程实王军，且其时向复聋性分别与Dijkstra 算法
和 Floyd 算法相向.
1 定义
本文所讨论的照均指简单透湿鸡.由于宽度优先搜索仅适沼子树状结构的问题，ffiJ比必
须首先对网络密进行交换.
定义 1 设 G， = (V.; ， Es) 是衔。 = iV .Ei 钩子圃，如果G. 包含了 G 的所有Iiìî杰，即若 V.
= V ，EsCE ， 贝~称 G. 为 G 的生成子回.
• :'='Þj墨大学管理学驼 .71∞49. 间安市咸?两路 28 号.梳官司臣，男. ..亨搏主宝
"两安妇罩大学计1年系.
收豁口蜿， 1Q96-(H一回 '吨'
‘ ..
254 西 北 纺 织 工 学 院 学 报 第 10卷
定义 2 不台回路的连温罔称为树．
如果 是 的生成于同同时义是一棵树，则称 是罔 0的一棵生成树．
可以证明，如果罔 是造坷的．则必存在生成树[c．
定义 3 在有向罔中，对旺一顶点 ”．称以 为终点的弧为 的引入弧．引 入弧的条数称
为 的引入次数，记为 id( ．韵：以 为眙点的弧为 的引出弧，弓l出弧的条教称为 的 引出
攻 数 ，记 为 od( )，
定义 4 在一棵 仃向树中．如果肯一十顶点的引入次数为 0，而其它所 fj顶点的引八次
数都为 1，则称该有向树为根树．引人次数为 0的顶点称为树根．引出次数为 0的顶点称为
树叶．其它顶点称为分支顶点
在图 】所示的根树中， o是树根 ， ， 和 是分支顶点，其余顶点是树叶．
定义 5 在根树 中，{；5=从顶点 出发经过一条弧可以到达的顶点为 的子结点，而称
为每一个子结点的父结点．称有同一个父结点的所有结点为兄弟结点．称从顶点 。出发可
以到达的每一个顶点为 的后裔结点，而称 为每一个后裔结点的先辈结点．
下面介绍将网络围变换为准生成根树的方法．
图 1 根树图 图2 网络图
2 准生成根树的生成
设有如图 2所示的网络罔．从起始结点 开始，把与 。o相邻的结点。 ，。z作为它的子结
点．然后，对 进行扩展，与付1邻接的结点有口o，。2 共3个，但 己作为。1的先辈结点而
存在于准生成根树中，这样付1的子结点就只有 。：和 了．对其它结点也作相同处理，
}冬i 3 树牧结构
维普资讯
254 雷北纺织工学院学报
定义 2 不含因药的泣i亟罔称为树.
如果 T 是 E 的生h'i子黑同对又是一棵树，到弱;T 是陀]G 部一棵生成树，
可以证明，如果i宅。是这退的.略必存在生成树EE.
第 10 卷
2主义 3 在在向寞;中，对任-1胃 Q Ï$~:..t .为终点的班为恒的引人缀，引人强的条数称
为包豹引入次数 .1己为 id(u).科;VJ. 布为始点的事E为宵的引血事， .引出躯的条载耗，为 M 约引出
次数，iC为0<1(的.
定义 4 在一棵 fíl与树中，如1果在一个1'(.1立的引入次数为 O. 而其它研手iJ理杰的引人次
数都为 1 ，则称该有向转为丰霍梅，引人欢载为 G 的顶点称为树根-引出次数为 B 的1高点哥哥、为
树 pt. j吉它顶点称为分支票点E
在m 1 S写示的根树中.在a 是挎根，町，也需尚在1 u‘是分支m点，其余顶点是树叶
定义 5 在很树 T 中，称从1贾杰 11 ， 出发经过一条宽可以JlJ达的获成为民的子结点，而称
良为每一个子结点的父结点.称有同一个父结点的所有结点为兄弟结点.事靠从1'(点缸，出发可
以到达的每一个顶点为也髦的后畜结点，而称也为每一个后裔结点的先辈结点.
下百介绍将网络图变换为准生成根树的方法.
第.
Vl ":1.
., .雹 句
回- "z IP ..
.. 筐' ...
回 1 根树m 图 z 凋络部
2 准生~根树约生成
设有如德 2S毫示的同结罚，从起蛤结点问开始，把与同相邻的结戎 D1 .Ii:z 作为立的子给
点.然后，对屿，电进行扩展.与叫邻援的结点有旬，吨 ， V，共 3个，但吨己作为町的先辈结点ïliî
存在于准生Jt根树中，这祥叫鸽子结点就只有电和电了.对其它结点也fF相同处理.
"
在"，.
tt-U !
..{!l
~3 争夺状结构
iL'." E
..，"飞
第 期 用宽度优先搜索求罔络囝的最琏路径 255
在准生成根树中．除起始结点 №外 ．其它结点都可能出现 多玖 ，为了区分起 见·分别用
上标(1)、(2 、(3 J等标出 ，其窦它 们是网络罔中的同一结点．例如，准：生成根树中的结点
““’ ， 】 1“ ，就是同络 中的结点
通过 以 变换 网络阿 2转 成了具有罔 3开；状的树状结构．可以看出．罔 3是一棵根
树H包含了原网络冈的全部结点．但 义 同于生成树．我们把具肯网 3形状的根树称为阿 2
的准生成狠树
显然 ，对于简单连洒罔，准生成根树是存在的，且同一 1、根的准生成根树『 柑．但不同根
的准生成根树不同构 翻此 ．简单适通罔的准生成根树的 ，r数等于 lrj．
3 搜索算法
在应用BES求也赋权阿络罔的最短路径时，要 用到两／r数据结构 (OPEN裘和 CLOSED
丧)，一个最优路径存储衷(OJ~VPATH,袁)．
OPEN表用于存放本层扩展剐生成的结点．对于 BFS，结点按生成的顾序排列，先生成的
结点排在前面，后生成的排在后面．
CLOSED表用于存放将要扩展或_弃已经扩展的结点．这里扩展的涵义是甩合适 的算子
对结点逆行操作，生成一纽子结点．
OPTPATH袭尼于存放刊目前为止搜索到的 目标结点 ．并且最优值总是放在 0P：_PA丁K
袭的最前面．
搜索过程如下 ：
Step] 把初始结直 放 八OPEN丧 ，并建立 只包含 的 G．
Step2 如果 OPEN表为空，卿搜索完毕 ，退出．
Step3 把 OPEN袁的第一个结点(记为结点 )取出放入 CLOSED表．
S~ep4 考 察结点 是 否为 目标结点．若是 ，则把该结点送入 OPTPATH裘，并 与 OPT
PATH袭中的其它 目标结点的代价值进行比较，并把代阶值最小并排在 OPTPATH表的摄前
端 ．
Step5 若结点 n不可扩展 ，则转第 2步．
Step6 扩展结点 ．将其先辈结点从该结点的邻接表中删除，其余结点(记作糗台 )作
为结点 的子结点放 入 OPEN表中．把集合 M加入图 0中，并计算从起始结点 咖到各子结
点的代价，按各结点的代价值对 OPEN表中的垒部结点按从小到大的顺序进行排序，然后转
第 2步．
在搜索算法中，可能要 用到几个 OPTPATH表 ，视从 。起始的所要到达的目标结点的 个
数决定，
在生成同络图的准生成根树时，随着网络图的复杂程度的增加，准生成根树将变得非常
露大·僵应用 BPS时，实际上并不需要画出同络图的准生成根树 ，只需把陌络罔的邻接矩阵
存起来即可．
4 结论
(1) 由于 BFS算菠的完备性和准生成根树的存在性，采用宽腰优先搜索拄术，可以求
出陶维翻 从起始站点聱I锰一绐 臼勺景短路弪值，并虽在求出最短路弪值后 ，不 ．爨 Dijk
维普资讯
第 7 草草 用宽度优先:搜索求网络网的是在路仨 255
在雄主nY;恕树中‘除起古1ì~"士，布阿外.其它主言点都可能出现多次.为了区分远见.分别用
t:机 (lí..{:)~ (:}) 1辛辛丁、出.1t亨?它们是网络用中的同一结点.院i如.If[生成很树中的结点
乙 j \"t f • V j (::, ， t'j 酌 .tljU 就是陀络附中始结窍 TJj •
.iilì:过以 k变换.网络传r 2 泣变成了具有罔 3 形状的纣状结构.可以:ç;出. r军I 3 是一棵很
幸哥儿包含了原网珞熙的主前才皮. j但又不同于生)J\(flt. 我们把具有罔 2 形状约权树称为何 2
部?主生 út权将
iL然，对于简单迄.ìiiì ffi 咽月E生 1;飞宁在树运存在的 .1主同一个根的准生成很拷问t'-I .债不同中臣
的I!t生iA: 根树不同构.15] 1吃 .1百守1注 1边用的F在生 JJ~根树的卡敦竿子11' 1 •
. ) 搜索算法
在应用 BFS 才二注赋校网络陀的最短路径时.要用到两个数据结构 10PEN 去手U CLOSED
表L 一个最t!:;/t径存储安'O!寸PATH 卖?
OPEN 表忠于存放本层扩展部;生JN.约法点.:H子 BFS.运点tJ<生成的颜序排列.先生成的
二点摔在前峦.后生成的排在后面E
E工OSED 表后子存放将要扩展或亲已经扩展的结点，这里扩展的涵义是用合适的算子
对结点过疗操作，生成一毯子法点.
J用'PA'好王表 ffl子存放到13 1îtr为止搜索j~è'; 吕栋结点空并且最1t值，二是民在 OPτ于ATH
表的最前离.
按当E过程如下
Stepl 把初始结点 Tε 放入 OPEK 衷，并建立L 只包含内的罚。‘
Step2 如果。陀N 表为空雹则搜索完毕，退出.
Step3 范 OPEI'专隶的第一个结点 :iE为结京的取出放入 CLOSED 袭，
S,ep4 考察结点篇是否为目狂结点.若是，则把该结应送人。凹'PA'πf 哀，并与 OPT
PA口f 裴中韵其它吕幸卫生吉杰的代1ft筐进行比较，并把代价信是小汗排在 OPTPATH 袤的最lÏ!f
端.
Step5 若结点刽不可扩展，哇y转第 2 步.
Step6 扩展综杰 h将其先辈结杰)J，、该结点前邻接表中部除，其余结点(iè作主是合 M)作
为结点 m 公子结点放人 OPEN 表中a 把集合 M 加入图。中，并计算从起始结点时3jlJ各子结
点的代价，按各结点的代价瘟对 OPTh表中的全部结点tJ<从小草J犬的烦序进行排序，然后传
第 2 步.
在投索算法中，可能要甩到几个 0凹'PATH 表.视}}，、叫起始的所要到达的吕标结点约 7、
数决定.
在生 L立网络图的准生J.;!::根树时，随着网络图约复杂程度的增加，准生或根享曾将变得非常
æ女-但应用 BFS 时‘实际仨并不需要E出网络图的1fE生成根树，只需把网络 ffi豹邻接矩阵
存起来E扫盲J.
4 结 if:
U) 出子 BFS tJ-泛的完备性辛!l l运生成根树的存在性，采lf1宽度优先控交技术，可以求
吕 I í"吗?吾罚;中卫拉格注♂~，~吨任 -1t; l，ι 执安短路径毡雹并立在求EE 录J[ '4.在经边后，不""‘幸~ Dljk.-
255 西 北 纺 织 工 学 院 学 报 第 ’0卷
stra算法那样有一个从 目标结点到起始结点的回湖过程
路径值和最短路径一次生成．
(2) 在求 同络罔中往意两 结点J可的最短路径时
点 ，另外一个作为目标结点 ，然后调用搜索过程即可，
即从起始结点到 目标结点的最短
只要把其中任意一个作为起始结
(3) 由于扩展任一结点时所要搜索的空间不超过 lrl一 1，1 扩展最多不超过 川 一 1
层，故算法的时问复杂性为 f f：1．在求汪意两点同的屉短路径时，涸』1了搜索过程的次数
不超过 1 1一 1次，故时间复杂性 淘fJflr1 )．分割与 Dijkstra算{圭和 Flo,a：l算法招同．
用本文介绍的算法米编写计算机程序，其结构非常紧凑，但当网络规模变大时，例如
≥ I5，求解时同会增加．
参考文献
肖位枢．图论及其莽法．北京：航空工业出版社，1993
王朝瑞．用论．北京：北京下业学院出版社，1987
傅京孙，蔡自兴，徐光佑．人工智能及其应用．北京；清华大学出版社，1981
段盯 荧千最短路径的 SPFA懊速掉法 西南交通大学学报，1994
Doo Nar~inBh，Pang~dyin． ㈨ Path Algorithms：Ta．xonc~ny and Annotation．Network3．1984
The Breadth—First Search for the Shortest Path
Ila~9 。e Z X P哪
(靶hooi of Mana自cmcnc，Jiao~ong Univcraicy，Ⅺ arI，7l 0049)
A矗t妇 d The~xmcept of quasi—soanniag root嗽 b 州 upon 抽e transformation for simply
oanncctc~l networks is introduced，and a new algorithm for short~st path is provided． 廿le alge-
rittun．tho topologiea l coofigXu'~ttion of the sim ply connectc,d network~has b∞n permuted．which is
the m C distinction of tho algorithm from othe~ ，SO the search for the shortest path can be conduc~-
ed on ~lrborescen[graph． Using this algurithm ．tho shortest path from origin to other vercic8 or arbl—
tr~"y paiL'S of vertices can befoundiniuotmorothe1 l J～J sceps．
Key’岫 tho shortest path，quasi—spanning root ，breadth-first search
维普资讯
255 西北结织工学院学报 萃 'G 卷
stra 主主法那样存-个从 5杯结 Q 3'lJ 扭亏古吃点的监H踏过程， I!~从边始注点~J 13 坏主主点的最短
路径筐恭1录垣路径一次生成.
(2) 在求网络用中任意两争结交间的录短路径时.只雯把骂中任意一个作为起治结
点，另外-1、作为自标结点，然后i黯用搜索过程邱吉T.
(3) 由于护展侄一结·点时所要搜索的空间不超过 |γI-J.ífú扩展录多不超过 P-I 一 l
层，放算洼的时向复杂性为由 W/'J. 在求{圭意两点问你没垣路径M.ì药用搜索过程的次数
不超过 IVI - 11.灾，放时间麦杂性为()( I ~'I'). 分知与 Díj坦tra ~浩如 Floy币 2草法沼同缸
用本文介绍的算法来编写ìt弃苦1程序，其结构非常紧 R壁，但当网络就苍苍变犬时，锅饭 n
》店，求解时间会增加.
参考文章在
1 离佳框b 望自论及其隽话.北京，航空T.!l且出版社.1993
2 王朝琦.理论"北京主.lt束专业学院出起泣.1987
3 傅京孙.蒙自兴，徐光佑.人士智程及其rilll. :l白毛清华女学出!连栓 .1987
4 段凡了在关于最短路径协 SPFA快速养法、夜雨交远大学学报> 1994
5 D国 Narsíngb，. Pang Cbiy!n. 5bort菌f pa也 Algar:i t趾黯言 T跑。音回可 and Anno恤.tion. Networks ..1984
τhe Breadth-First S锦rch for the Shortest Pa也
Jlang S},engce Zlumg X，谜面P"'!I
(Scboolωf 岛也na胆回拙. J坦国回g Urú暗自:ity ，芷i' an ,71(049)
Th.∞由自pt of -sp由ming root tr，出国集剖d upon Ilte 挂在nsform时ion for simply
∞nn旺达:e<1 ne!W叮ks is introduced.. and .a new algori出皿 for sho扰。且阳ttt i. provided. By 出. all!;<>-
d吐田， Úle t<:申ologï，值1 ∞n fìguratìon of the 垂血抖y ∞nnected networ bas 恒en pennut'叫 ， whic副总
在h. m世td坦白1Ction of 副，@.orjthm from othe悟民o the search for t short国t patn ..::an be conduc t.-
ed on graptt. Using ,his aJguríth皿， the 居t path from orígin to other verrices or arbj.
trary pairs of verti咽 can be fou nd in not more 白血 íV l-l 白声·
Keywords the sh叮描tpø出 quasi-spanning r∞ttr缸， br明白h-fi目.t ，国.reh
