多叉树最短路径
多叉树最短路径
酒逍遥 发表于1年前
多叉树最短路径
  • 发表于 1年前
  • 阅读 700
  • 收藏 1
  • 点赞 1
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

<?php
$arr =array('A'=>array('value'=>1,'child_list'=>array('B','C','D')),
'B'=>array('value'=>1,'child_list'=>array('E','F','G')),
'F'=>array('value'=>1,'child_list'=>array('K','L','N')),
'N'=>array('value'=>1,'child_list'=>array('R','S','T')),
'D'=>array('value'=>1,'child_list'=>array('H','I','J')),
'H'=>array('value'=>1,'child_list'=>array('O','P','Q')),
'C'=>array('value'=>1,'child_list'=>array()),
'E'=>array('value'=>1,'child_list'=>array()),
'K'=>array('value'=>1,'child_list'=>array()),
'L'=>array('value'=>1,'child_list'=>array()),
'G'=>array('value'=>1,'child_list'=>array()),
'R'=>array('value'=>1,'child_list'=>array()),
'S'=>array('value'=>1,'child_list'=>array()),
'T'=>array('value'=>1,'child_list'=>array()),
'I'=>array('value'=>1,'child_list'=>array()),
'J'=>array('value'=>1,'child_list'=>array()),
'O'=>array('value'=>1,'child_list'=>array()),
'P'=>array('value'=>1,'child_list'=>array()),
'Q'=>array('value'=>1,'child_list'=>array()),
);

function find_path($nodeA,$nodeB){
	global $arr;
	$rootA = find_root($nodeA);
	$rootB = find_root($nodeB);
	if(!$rootA) $rootA[]=$nodeA;
	else $outA[] = $nodeA;
	if(!$rootB) $rootB[]=$nodeB;
	else $outB[] = $nodeB;
	foreach($rootA as $v){
		$outA[] = $v;
		if(in_array($v,$rootB)){
			foreach($rootB as $va){
				if($va == $v) break;
				else $outB[] =$va;
			}
			if($outB) $outB = array_reverse($outB);
			break;
		}
	}
	if($outA) echo implode('=>',$outA);
	if($outB) echo '=>'.implode('=>',$outB);
}

function find_root($node,$root=array()){
	global $arr;
	foreach($arr as $k=>$v){
		if(in_array($node,$v['child_list'])){
			$root[]=$k;
			return find_root($k,$root);
		}
	}
	return $root;
}
find_path('G','R');
?>

输出 G=>B=>F=>N=>R

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
酒逍遥
粉丝 49
博文 39
码字总数 34924
×
酒逍遥
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: