广度优先搜索算法(java和php对比)

java实现:

public class BFS {
    
        public static void main(String[] args){
            //初始化先建立起各个节点信息，以及对应的直接子节点列表
            HashMap<String,String[]> map = new HashMap<>();
            map.put("A", new String[] {"B","C"});
            map.put("B", new String[] {"E"});
            map.put("C", new String[] {"D","F"});
            map.put("D", new String[] {"E"});
            map.put("E", new String[] {"H"});
            map.put("F", new String[] {"E","G"});
            map.put("G", new String[] {"H"});
            map.put("H", new String[] {});
            //获取从A到H的最短路径节点链表
            Node target = findTarget("A","H",map);
            //打印出最短路径的各个节点信息
            printSearPath(target);
    
        }
    
        /**
         * 打印出到达节点target所经过的各个节点信息
         * @param target
         */
        static void printSearPath(Node target) {
            if (target != null) {
                System.out.print("找到了目标节点:" + target.id + "\n");
                
                List<Node> searchPath = new ArrayList<Node>();
                searchPath.add(target);
                Node node = target.parent;
                while(node!=null) {
                    searchPath.add(node);
                    node = node.parent;
                }
                String path = "";
                for(int i=searchPath.size()-1;i>=0;i--) {
                    path += searchPath.get(i).id;
                    if(i!=0) {
                        path += "-->";
                    }
                }
                System.out.print("步数最短："+path);
            } else {
                System.out.print("未找到了目标节点");
            }
        }
        
        /**
         * 从指定的开始节点 startId ，查询到目标节点targetId 的最短路径
         * @param startId
         * @param targetId
         * @param map
         * @return
         */
        static Node findTarget(String startId,String targetId,HashMap<String,String[]> map) {
            List<String> hasSearchList = new ArrayList<String>();
            LinkedList<Node> queue = new LinkedList<Node>();
            queue.offer(new Node(startId,null));
            while(!queue.isEmpty()) {
                Node node = queue.poll();
                
                if(hasSearchList.contains(node.id)) {
                    //跳过已经搜索过的，避免重复或者死循环
                    continue;
                }
                System.out.print("判断节点:" + node.id +"\n");
                if (targetId.equals(node.id)) {
                    return node;
                }
                hasSearchList.add(node.id);
                if (map.get(node.id) != null && map.get(node.id).length > 0) {
                    for (String childId : map.get(node.id)) {
                        queue.offer(new Node(childId,node));
                    }
                }
            }
    
            return null;
        }
        
        /**
         * 节点对象
         * @author Administrator
         *
         */
        static class Node{
            //节点唯一id
            public String id;
            //该节点的直接父节点
            public Node parent;
            //该节点的直接子节点
            public List<Node> childs = new ArrayList<Node>();
            public Node(String id,Node parent) {
                this.id = id;
                this.parent = parent;
            }
        }
    
    }

执行结果:

判断节点:A
    判断节点:B
    判断节点:C
    判断节点:E
    判断节点:D
    判断节点:F
    判断节点:H
    找到了目标节点:H
    步数最短：A-->B-->E-->H

php实现:

$arr = [
    'A' => ['B','C'],
    'B' => ['E'],
    'C' => ['D','F'],
    'D' => ['E'],
    'E' => ['H'],
    'F' => ['E,G']
];
//求 A -> F的最短路径
function BFS($arr,$start,$target){
    $queue = $arr[$start];   //节点队列
    $path = [];              //记录最短路径
    foreach($arr[$start] as $val){
        $path[$val] = $start;
    }      
    $searched = [];          //标记已经访问过的节点
    while(!empty($queue)){
        $head = array_shift($queue);
        if($head == $target){    //找到目标
            break;
        }         
        if(in_array($head,$searched)){  //已经访问过，直接跳过 
            continue;     
        }
        $searched[] = $head;
        foreach($arr[$head] as $val){
            $path[$val] = $head;
        }
        $queue = array_merge($queue,$arr[$head]);
    }
   
    $pathto = [];
    while(!empty($path[$target])){
        $pathto[] = $target;
        $target = $path[$target];
    }
    $pathto[] = $target;
    $pathstr = "";
    for($i = count($pathto) -1 ;$i >=0;$i--){
        $pathstr .= $pathto[$i]."->";
    }
    $pathstr = substr($pathstr,0,strlen($pathstr)-2);
    echo "min path:".$pathstr;
}


BFS($arr,'A','F');

min path:A->C->D