廣度優(yōu)先搜索算法在互連網(wǎng)絡(luò)通信中的應(yīng)用.pdf

1、 在互連網(wǎng)絡(luò)中進(jìn)行通信，由網(wǎng)絡(luò)拓?fù)錄Q定的網(wǎng)絡(luò)延遲是一個靜態(tài)量，直接受到網(wǎng)絡(luò)直徑的影響。在網(wǎng)絡(luò)有故障發(fā)生的情況下，故障直徑反映了網(wǎng)絡(luò)的容錯能力，而故障直徑的求解本身比較困難。網(wǎng)絡(luò)尋徑是網(wǎng)絡(luò)通信必須考慮的一個重要方面。本文針對以上情況研究了廣度優(yōu)先搜索算法在這些方面的應(yīng)用。作者作出的研究成果主要體現(xiàn)在以下三個方面： 首先利用廣度優(yōu)先生成樹的樹高不會高于其他任何同根生成樹樹高的特點，對不同的網(wǎng)絡(luò)進(jìn)行了廣度優(yōu)先搜索分析，給出了超

2、立方體，交叉立方體，螺旋立方體等網(wǎng)絡(luò)的直徑與故障直徑。并且進(jìn)一步給出了BC互連網(wǎng)絡(luò)直徑的一個界限。 其次考慮了至多可以刪除多少個頂點才能保證網(wǎng)絡(luò)的連通，給出了網(wǎng)絡(luò)的容錯能力。由Menger定理可以得到BC互連網(wǎng)絡(luò)之間至少存在n條內(nèi)部節(jié)點互不相交的路徑。利用廣度優(yōu)先搜索的思想，本文給出了求任意兩個節(jié)點之間的n條內(nèi)部節(jié)點互不相交，且在兩點間所有路徑中是最短的n條路徑的算法。該算法為網(wǎng)絡(luò)故障直徑的提供了依據(jù)。而且，在故障存在但是網(wǎng)絡(luò)連