User Tools

Site Tools


λ Breadth-first search

======= Algorithm ======= <syntax js> function breadthFirstSearch(root) { var q = new Queue(); q.enqueue(root); while (q.length() > 0) { var node = q.dequeue(); // add all the children to the back of the queue for (var i=0, c=node.children.length; i<c; i++) { q.enqueue(node.children[i]); } } } </syntax> ======= Support ======= <syntax js> // a very simple queue function Queue() { var queue = []; this.enqueue = function(x) { queue.push(x); }; this.dequeue = function() { return queue.shift(); }; this.length = function() { return queue.length; } } function run(root) { return breadthFirstSearch(root); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title": "Breadth-first search", "height":"260px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g.node { font-family: Verdana, Helvetica; font-size: 12px; font-weight: bold; } circle.node-dot { fill: lightsalmon; stroke: red; stroke-width: 1px; } g.selected circle.node-dot { fill: #6495ED; stroke: blue; } g.current circle.node-dot { fill: #FFF; stroke: blue; } path.link { fill: none; stroke: gray; } body {margin:0px} </style> <script src="http://d3js.org/d3.v2.js"></script> <script> var maxNodes = 10; var treeData; function newTree() { treeData = {data:Math.floor(Math.random()*20), children:[]}; var allNodes = [treeData]; // generate a random tree for (var i=0; i<maxNodes; i++) { var child = {data:Math.floor(Math.random()*20), children:[]}; var parent = allNodes[Math.floor(allNodes.length*Math.random())]; parent.children.push(child); allNodes.push(child); } buildTree("#tree-container"); reset(); } var layoutRoot = null; function buildTree(containerName) { // size of the diagram var size = { width:300, height: 250}; var tree = d3.layout.tree() .sort(null) .size([size.width, size.height-40]) .children(function(d) { return d.children; }); var nodes = tree.nodes(treeData); var links = tree.links(nodes); // root if (!layoutRoot) { layoutRoot = d3.select(containerName) .append("svg:svg").attr("width", size.width).attr("height", size.height) .append("svg:g") .attr("class", "container") .attr("transform", "translate(0,20)"); } else { layoutRoot.selectAll("path.link").remove(); layoutRoot.selectAll("g.node").remove(); } // Edges between nodes as a <path class="link" /> var link = d3.svg.diagonal(); layoutRoot.selectAll("path.link") .data(links) .enter() .append("svg:path") .attr("class", "link") .attr("d", link); layoutRoot.selectAll("path.link").each(function(d) {d.link = this;}); // nodes var nodeGroup = layoutRoot.selectAll("g.node") .data(nodes) .enter() .append("svg:g") .attr("class", "node") .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); nodeGroup.append("svg:circle") .attr("class", "node-dot") .attr("r", 15); nodeGroup.append("svg:text") .attr("dy", 4) .text(function(d) { return d.data; }) .attr("text-anchor", "middle"); } window.onload = function() { newTree(); }; function update(n, x, isRunning, duration, $prev) { if (x.stack.length < 1 && !x.hasOwnProperty('returnedValue')) { d3.selectAll("g.node").classed("selected", false); } var newPrev = $prev; var node = x.lookupInScope("node"); var d3Node = node? d3.selectAll("g.node").filter(function(d) {return d===node;}) : null; if (node && d3Node) { var unselectedNode = d3Node.filter(":not(.selected)"); unselectedNode.classed("selected", true); newPrev = function(prev) { unselectedNode.classed("selected", false); prev(); }.bind(undefined, newPrev); } d3.selectAll("g.node").classed("current", function(d) {return d===node;}); return newPrev; } function args() { return treeData; } </script> </head> <body> <div id="tree-container" style="position:relative"> <button onclick="newTree()" style="position:absolute;left:0px;top:0px">New Tree</button> </div> </body> </html></syntax>

algorithm/breadth-first_search.txt · Last modified: 2015/02/02 08:28 (external edit)