16.图的深度搜索和广度搜索代码实现（JavaScript版）

佚名 5年前 (2020-07-02) 算法 801人围观抢沙发百度已收录

图的深度搜索和广度搜索

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        function Node(value){
            this.value = value;
            this.neighbor = [];
        }

        var nodeA = new Node("a");
        var nodeB = new Node("b");
        var nodeC = new Node("c");
        var nodeD = new Node("d");
        var nodeE = new Node("e");
        var nodeF = new Node("f");
        var nodeG = new Node("g");
        var nodeH = new Node("h");

        nodeA.neighbor.push(nodeB);
        nodeA.neighbor.push(nodeC);
        nodeB.neighbor.push(nodeA);
        nodeB.neighbor.push(nodeD);
        nodeB.neighbor.push(nodeF);
        nodeC.neighbor.push(nodeA);
        nodeC.neighbor.push(nodeD);
        nodeC.neighbor.push(nodeG);
        nodeD.neighbor.push(nodeB);
        nodeD.neighbor.push(nodeC);
        nodeD.neighbor.push(nodeE);
        nodeE.neighbor.push(nodeD);
        nodeE.neighbor.push(nodeF);
        nodeE.neighbor.push(nodeG);
        nodeF.neighbor.push(nodeB);
        nodeF.neighbor.push(nodeE);
        nodeF.neighbor.push(nodeH);
        nodeG.neighbor.push(nodeC);
        nodeG.neighbor.push(nodeE);
        nodeG.neighbor.push(nodeH);
        nodeH.neighbor.push(nodeF);
        nodeH.neighbor.push(nodeG);

        //图的深度优先搜索
        function deepSearch(node, target, path){
            if(node == null) return false;
            if(path.indexOf(node) > -1) return false;//若该节点已经搜索过，返回
            if(node.value == target) return true;
            path.push(node);//将该节点添加到已经遍历的节点中
            var result = false;//默认没有目标节点
            for(var i = 0; i < node.neighbor.length; i++){
                result |= deepSearch(node.neighbor[i], target, path);//在所有分支上寻找目标节点
            }

            return result ? true : false;
        }

        console.log(deepSearch(nodeB, "i", []));

        //图的广度优先搜索
        function breadthSearch(nodes, target, path){
            if(nodes == null || nodes.length == 0) return false;
            var neighbor = [];
            for(var i = 0; i < nodes.length; i++){//循环所有下一层节点
                if(path.indexOf(nodes[i]) > -1) continue;//该节点已遍历，返回
                if(nodes[i].value == target) return true;//找到了目标节点
                path.push(nodes[i]);//将该节点放入已遍历节点中
                neighbor = neighbor.concat(nodes[i].neighbor);//将该节点的邻居节点放入数组中
            }

            return breadthSearch(neighbor, target, path);//搜索下一层节点
        }

        console.log(breadthSearch([nodeA], "i", []));
    </script>
</body>
</html>