圖的深度搜索和廣度搜索
<!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 =https://www.cnblogs.com/lanshanxiao/p/ 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 =https://www.cnblogs.com/lanshanxiao/p/= 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 =https://www.cnblogs.com/lanshanxiao/p/= 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>
圖的深度和廣度優先搜索
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31062.html
標籤：其他