文档章节

多叉树最短路径

酒逍遥
 酒逍遥
发布于 2017/02/13 14:31
字数 240
阅读 772
收藏 1
<?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

© 著作权归作者所有

共有 人打赏支持
酒逍遥

酒逍遥

粉丝 48
博文 40
码字总数 35454
作品 0
武汉
高级程序员
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0
树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker
2015/08/14
0
0
Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer
2017/12/20
0
0
JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名
05/31
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

咕泡-Factory设计模式笔记

个人感悟: 设计模式都是处理复杂问题的,如果问题本身很简单,使用设计模式反而累赘,增加了开发的复杂性 遇到最简单的情况,直接 new 如果创建对象的过程简单,但是需要匹配不同情况,返回...

职业搬砖20年
21分钟前
0
0
Java中的锁分类

在读很多并发文章中,会提及各种各样锁如公平锁,乐观锁等等,这篇文章介绍各种锁的分类。介绍的内容如下: 公平锁/非公平锁 可重入锁 独享锁/共享锁 互斥锁/读写锁 乐观锁/悲观锁 分段锁 偏...

Funcy1122
29分钟前
0
0
Ansible随机数

想为你的Ansible剧本取一个随机数?还想在接下来的运行中保持系统的等幂性?这里有一个答案。 假如,你要为一大批服务器设置cron任务,却不想让它们同时启动,你可以这样设置分钟数: minute...

大别阿郎
38分钟前
0
0
SpringCloud之服务注册中心Eureka

本系列介绍的配置均基于 Spring Boot 2.0.1.RELEASE 版本和 Spring Cloud Finchley.SR1 服务注册中心 Spring Cloud 已经帮我们实现了服务注册中心,我们只需要很简单的几个步骤就可以完成。 ...

熊小飞呀
今天
9
1
“Comparison method violates ...”异常的再现方法

前提条件:JDK8 代码: import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Test { public stat......

hunterli
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部