PHP實現廣度優先搜索算法(BFS,Broad First Search)詳解

更新:2017-10-25    編輯:夏柳    來源:不詳    人氣:加載中...    字號:|

標簽:實現  搜索  詳解  算法  search  優先  百度搜索

本文實例講述了PHP實現廣度優先搜索算法。分享給大家供大家參考,具體如下:

廣度優先搜索算法思想 Breadth-FirstTraversal

廣度優先遍歷是連通圖的一種遍歷策略。因為它的思想是從一個頂點V0開始,輻射狀地優先遍歷其周圍較廣的區域,故得名。

廣度優先搜索遍歷類似于樹的按層次遍歷。對于無向連通圖,廣度優先搜索是從圖的某個頂點v0起程,在造訪v0之后,依次搜索造訪v0的各個未被造訪過的鄰接點w1,w2,…。然后順序搜索造訪w1的各未被造訪過的鄰接點,w2的各未被造訪過的鄰接點,…。即從v0開始,由近至遠,按層次依次造訪與v0有路徑相通且路徑長度分辨為1,2,…的頂點,直至連通圖中所有頂點都被造訪一次。

只要按一定的次序造訪各層頂點,方便程序實現,廣度優先搜索的整體層次順序一定,各層造訪順序不是唯一的。

具體描述如下:

設圖G的初態是所有頂點均未造訪,在G 中任選一頂點i作為初始點,則廣度優先搜索的基本思想是:

(1)從圖中的某個頂點V起程造訪并記載。
(2)依次造訪V的所有鄰接頂點;
(3)分辨從這些鄰接點起程,依次造訪它們的未被造訪過的鄰接點,直到圖中所有已被造訪過的頂點的鄰接點都被造訪到。
(4)第(3)步。

依詞攀類推,直到圖中所有頂點都被造訪完為止 。

廣度優先搜索在搜索造訪一層時,需要記住已被造訪的頂點,以便在造訪下層頂點時,從已被造訪的頂點起程搜索造訪其鄰接點。所以在廣度優先搜索中需要設置一個隊列Queue,使已被造訪的頂點順序由隊尾進入隊列。在搜索造訪下層頂點時,先從隊首取出一個已被造訪的上層頂點,再從該頂點起程搜索造訪它的各個鄰接點。

SearchInterface.php:

<?php abstract class SearchInterface { protected $G;//圖 protected $s;//圖的首節點 function __construct($_G,$_s){$this->G = $_G;$this->s = $_s;} public abstract function search(); } ?>

bfs.php:

<?php include_once('SearchInterface.php'); class bfs extends SearchInterface { private $d = array();//源點s和頂點u之間的距離 private $tt = array();//結點u的父母存于變量 private $visit = array();//已造訪節點 function __construct($_G,$_s) { parent::__construct($_G,$_s); //初始化$d/$tt,初始值為無窮大/NULL for($i=0;$i<9;$i++) { $this->d[$i] = 20000; $this->tt[$i] = NULL; $this->visit[$i] = 0; } } public function search() { //造訪所有節點 $queue = array(); for($i=0;$i<9;$i++) { if($this->visit[$i]==0) { array_push($queue,$i); while(!empty($queue)) { $_s = array_shift($queue); $this->visit[$_s] = 1; echo ($_s+1).'<br>'; $link_s = $this->G->get_links($_s); //獲取和s直接相連的頂點u foreach($link_s as $j => $u) { if($this->visit[$u]==0) { array_push($queue,$u); $this->visit[$u] = 2; } } } } } } } ?>

應用法子:

$G = new Graphic; $search = new bfs($G,1); $search->search();


,
評論列表(網友評論僅供網友表達個人看法,并不表明本站同意其觀點或證實其描述)

站點導航

您可能在找這些
四川快乐12电视软件 九游游戏大厅 北京pk10预测 海南飞鱼游戏 股票怎么玩呢 天才麻将少女全国篇 三肖期期期免费准 江西多乐彩走势图 怎样买平特肖稳赢 哈灵麻将最新版app官网 最全的足球直播app