本文實(shí)例講述了PHP實(shí)現(xiàn)圖的鄰接矩陣表示及幾種簡單遍歷算法。分享給大家供大家參考，具體如下：
在web開發(fā)中圖這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用比樹要少很多,但在一些業(yè)務(wù)中也常有出現(xiàn),下面介紹幾種圖的尋徑算法,并用PHP加以實(shí)現(xiàn).
佛洛依德算法,主要是在頂點(diǎn)集內(nèi),按點(diǎn)與點(diǎn)相鄰邊的權(quán)重做遍歷,如果兩點(diǎn)不相連則權(quán)重?zé)o窮大,這樣通過多次遍歷可以得到點(diǎn)到點(diǎn)的最短路徑,邏輯上最好理解,實(shí)現(xiàn)也較為簡單,時(shí)間復(fù)雜度為O(n^3);
迪杰斯特拉算法,OSPF中實(shí)現(xiàn)最短路由所用到的經(jīng)典算法,djisktra算法的本質(zhì)是貪心算法,不斷的遍歷擴(kuò)充頂點(diǎn)路徑集合S,一旦發(fā)現(xiàn)更短的點(diǎn)到點(diǎn)路徑就替換S中原有的最短路徑,完成所有遍歷后S便是所有頂點(diǎn)的最短路徑集合了.迪杰斯特拉算法的時(shí)間復(fù)雜度為O(n^2);
克魯斯卡爾算法,在圖內(nèi)構(gòu)造最小生成樹,達(dá)到圖中所有頂點(diǎn)聯(lián)通.從而得到最短路徑.時(shí)間復(fù)雜度為O(N*logN);
?php
/**
* PHP 實(shí)現(xiàn)圖鄰接矩陣
*/
class MGraph{
private $vexs; //頂點(diǎn)數(shù)組
private $arc; //邊鄰接矩陣,即二維數(shù)組
private $arcData; //邊的數(shù)組信息
private $direct; //圖的類型(無向或有向)
private $hasList; //嘗試遍歷時(shí)存儲(chǔ)遍歷過的結(jié)點(diǎn)
private $queue; //廣度優(yōu)先遍歷時(shí)存儲(chǔ)孩子結(jié)點(diǎn)的隊(duì)列,用數(shù)組模仿
private $infinity = 65535;//代表無窮,即兩點(diǎn)無連接,建帶權(quán)值的圖時(shí)用,本示例不帶權(quán)值
private $primVexs; //prim算法時(shí)保存頂點(diǎn)
private $primArc; //prim算法時(shí)保存邊
private $krus;//kruscal算法時(shí)保存邊的信息
public function MGraph($vexs, $arc, $direct = 0){
$this->vexs = $vexs;
$this->arcData = $arc;
$this->direct = $direct;
$this->initalizeArc();
$this->createArc();
}
private function initalizeArc(){
foreach($this->vexs as $value){
foreach($this->vexs as $cValue){
$this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity);
}
}
}
//創(chuàng)建圖 $direct:0表示無向圖,1表示有向圖
private function createArc(){
foreach($this->arcData as $key=>$value){
$strArr = str_split($key);
$first = $strArr[0];
$last = $strArr[1];
$this->arc[$first][$last] = $value;
if(!$this->direct){
$this->arc[$last][$first] = $value;
}
}
}
//floyd算法
public function floyd(){
$path = array();//路徑數(shù)組
$distance = array();//距離數(shù)組
foreach($this->arc as $key=>$value){
foreach($value as $k=>$v){
$path[$key][$k] = $k;
$distance[$key][$k] = $v;
}
}
for($j = 0; $j count($this->vexs); $j ++){
for($i = 0; $i count($this->vexs); $i ++){
for($k = 0; $k count($this->vexs); $k ++){
if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){
$path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]];
$distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]];
}
}
}
}
return array($path, $distance);
}
//djikstra算法
public function dijkstra(){
$final = array();
$pre = array();//要查找的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)數(shù)組
$weight = array();//權(quán)值和數(shù)組
foreach($this->arc[$this->vexs[0]] as $k=>$v){
$final[$k] = 0;
$pre[$k] = $this->vexs[0];
$weight[$k] = $v;
}
$final[$this->vexs[0]] = 1;
for($i = 0; $i count($this->vexs); $i ++){
$key = 0;
$min = $this->infinity;
for($j = 1; $j count($this->vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 $weight[$temp] $min){
$key = $temp;
$min = $weight[$temp];
}
}
$final[$key] = 1;
for($j = 0; $j count($this->vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 ($min + $this->arc[$key][$temp]) $weight[$temp]){
$pre[$temp] = $key;
$weight[$temp] = $min + $this->arc[$key][$temp];
}
}
}
return $pre;
}
//kruscal算法
private function kruscal(){
$this->krus = array();
foreach($this->vexs as $value){
$krus[$value] = 0;
}
foreach($this->arc as $key=>$value){
$begin = $this->findRoot($key);
foreach($value as $k=>$v){
$end = $this->findRoot($k);
if($begin != $end){
$this->krus[$begin] = $end;
}
}
}
}
//查找子樹的尾結(jié)點(diǎn)
private function findRoot($node){
while($this->krus[$node] > 0){
$node = $this->krus[$node];
}
return $node;
}
//prim算法,生成最小生成樹
public function prim(){
$this->primVexs = array();
$this->primArc = array($this->vexs[0]=>0);
for($i = 1; $i count($this->vexs); $i ++){
$this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]];
$this->primVexs[$this->vexs[$i]] = $this->vexs[0];
}
for($i = 0; $i count($this->vexs); $i ++){
$min = $this->infinity;
$key;
foreach($this->vexs as $k=>$v){
if($this->primArc[$v] != 0 $this->primArc[$v] $min){
$key = $v;
$min = $this->primArc[$v];
}
}
$this->primArc[$key] = 0;
foreach($this->arc[$key] as $k=>$v){
if($this->primArc[$k] != 0 $v $this->primArc[$k]){
$this->primArc[$k] = $v;
$this->primVexs[$k] = $key;
}
}
}
return $this->primVexs;
}
//一般算法,生成最小生成樹
public function bst(){
$this->primVexs = array($this->vexs[0]);
$this->primArc = array();
next($this->arc[key($this->arc)]);
$key = NULL;
$current = NULL;
while(count($this->primVexs) count($this->vexs)){
foreach($this->primVexs as $value){
foreach($this->arc[$value] as $k=>$v){
if(!in_array($k, $this->primVexs) $v != 0 $v != $this->infinity){
if($key == NULL || $v current($current)){
$key = $k;
$current = array($value . $k=>$v);
}
}
}
}
$this->primVexs[] = $key;
$this->primArc[key($current)] = current($current);
$key = NULL;
$current = NULL;
}
return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc);
}
//一般遍歷
public function reserve(){
$this->hasList = array();
foreach($this->arc as $key=>$value){
if(!in_array($key, $this->hasList)){
$this->hasList[] = $key;
}
foreach($value as $k=>$v){
if($v == 1 !in_array($k, $this->hasList)){
$this->hasList[] = $k;
}
}
}
foreach($this->vexs as $v){
if(!in_array($v, $this->hasList))
$this->hasList[] = $v;
}
return implode($this->hasList);
}
//廣度優(yōu)先遍歷
public function bfs(){
$this->hasList = array();
$this->queue = array();
foreach($this->arc as $key=>$value){
if(!in_array($key, $this->hasList)){
$this->hasList[] = $key;
$this->queue[] = $value;
while(!empty($this->queue)){
$child = array_shift($this->queue);
foreach($child as $k=>$v){
if($v == 1 !in_array($k, $this->hasList)){
$this->hasList[] = $k;
$this->queue[] = $this->arc[$k];
}
}
}
}
}
return implode($this->hasList);
}
//執(zhí)行深度優(yōu)先遍歷
public function excuteDfs($key){
$this->hasList[] = $key;
foreach($this->arc[$key] as $k=>$v){
if($v == 1 !in_array($k, $this->hasList))
$this->excuteDfs($k);
}
}
//深度優(yōu)先遍歷
public function dfs(){
$this->hasList = array();
foreach($this->vexs as $key){
if(!in_array($key, $this->hasList))
$this->excuteDfs($key);
}
return implode($this->hasList);
}
//返回圖的二維數(shù)組表示
public function getArc(){
return $this->arc;
}
//返回結(jié)點(diǎn)個(gè)數(shù)
public function getVexCount(){
return count($this->vexs);
}
}
$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');//鍵為邊,值權(quán)值
$test = new MGraph($a, $b);
print_r($test->bst());
運(yùn)行結(jié)果：
Array
(
[vexs] => Array
(
[0] => a
[1] => b
[2] => f
[3] => i
[4] => c
[5] => g
[6] => h
[7] => e
[8] => d
)
[arc] => Array
(
[ab] => 10
[af] => 11
[bi] => 12
[ic] => 8
[bg] => 16
[gh] => 19
[he] => 7
[hd] => 16
)
)
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》
希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:- PHP簡單實(shí)現(xiàn)二維數(shù)組的矩陣轉(zhuǎn)置操作示例
- PHP使用數(shù)組實(shí)現(xiàn)矩陣數(shù)學(xué)運(yùn)算的方法示例
- PHP實(shí)現(xiàn)蛇形矩陣,回環(huán)矩陣及數(shù)字螺旋矩陣的方法分析
- PHP 數(shù)組和字符串互相轉(zhuǎn)換實(shí)現(xiàn)方法
- PHP中數(shù)組合并的兩種方法及區(qū)別介紹
- PHP遍歷數(shù)組的方法匯總
- PHP遍歷數(shù)組的幾種方法
- php數(shù)組函數(shù)序列之a(chǎn)rray_keys() - 獲取數(shù)組鍵名
- php獲取數(shù)組中重復(fù)數(shù)據(jù)的兩種方法
- PHP實(shí)現(xiàn)順時(shí)針打印矩陣(螺旋矩陣)的方法示例
