algorithm - JavaScript Depth-first search - Stack Overflow

admin管理员组

文章数量:1290258

I am trying to implement DFS in JavaScript but I am having a little problem. Here is my Algorithm class:

"use strict";

define([], function () {

    return function () {

        var that = this;

        this.search = function (searchFor, node) {
            if (searchFor === node.getValue()) {
                return node;
            }
            var i, children = node.getChildren(), child, found;
            for (i = 0; i < children.length; i += 1) {
                child = children[i];
                found = that.search(searchFor, child);
                if (found) {
                    return found;
                }
            }
        };

    };

});

My Node class which represents a single node in the graph:

"use strict";

define([], function () {

    return function (theValue) {
        var value = theValue,
            children = [];

        this.addChild = function (theChild) {
            children.push(theChild);
        };

        this.hasChildren = function () {
            return children.length > 0;
        };

        this.getChildren = function () {
            return children;
        };

        this.getValue = function () {
            return value;
        };
    };

});

I create a tree like this:

"use strict";

define(["DFS/Node", "DFS/Algorithm"], function (Node, Algorithm) {

    return function () {

        this.run = function () {
            var node1 = new Node(1),
                node2 = new Node(2),
                node3 = new Node(3),
                node4 = new Node(4),
                node5 = new Node(5),
                node6 = new Node(6),
                node7 = new Node(7),
                node8 = new Node(8),
                node9 = new Node(9),
                node10 = new Node(10),
                node11 = new Node(11),
                node12 = new Node(12),
                dfs = new Algorithm();

            node1.addChild(node2, node7, node8);
            node2.addChild(node3, node6);
            node3.addChild(node4, node5);
            node8.addChild(node9, node12);
            node9.addChild(node10, node11);

            console.log(dfs.search(5, node1));
        };

    };

});

I see undefined in the logs. I am not sure why my code is stopping at 4 and not continuing.

I am trying to implement DFS in JavaScript but I am having a little problem. Here is my Algorithm class:

"use strict";

define([], function () {

    return function () {

        var that = this;

        this.search = function (searchFor, node) {
            if (searchFor === node.getValue()) {
                return node;
            }
            var i, children = node.getChildren(), child, found;
            for (i = 0; i < children.length; i += 1) {
                child = children[i];
                found = that.search(searchFor, child);
                if (found) {
                    return found;
                }
            }
        };

    };

});

My Node class which represents a single node in the graph:

"use strict";

define([], function () {

    return function (theValue) {
        var value = theValue,
            children = [];

        this.addChild = function (theChild) {
            children.push(theChild);
        };

        this.hasChildren = function () {
            return children.length > 0;
        };

        this.getChildren = function () {
            return children;
        };

        this.getValue = function () {
            return value;
        };
    };

});

I create a tree like this:

"use strict";

define(["DFS/Node", "DFS/Algorithm"], function (Node, Algorithm) {

    return function () {

        this.run = function () {
            var node1 = new Node(1),
                node2 = new Node(2),
                node3 = new Node(3),
                node4 = new Node(4),
                node5 = new Node(5),
                node6 = new Node(6),
                node7 = new Node(7),
                node8 = new Node(8),
                node9 = new Node(9),
                node10 = new Node(10),
                node11 = new Node(11),
                node12 = new Node(12),
                dfs = new Algorithm();

            node1.addChild(node2, node7, node8);
            node2.addChild(node3, node6);
            node3.addChild(node4, node5);
            node8.addChild(node9, node12);
            node9.addChild(node10, node11);

            console.log(dfs.search(5, node1));
        };

    };

});

I see undefined in the logs. I am not sure why my code is stopping at 4 and not continuing.

• javascript
• algorithm
• depth-first-search

Share Improve this question Follow asked Oct 12, 2013 at 20:39 Richard KnopRichard Knop 83.8k154154 gold badges398398 silver badges560560 bronze badges 4

• Where is the define() function ing from ? – Ibrahim Najjar Commented Oct 12, 2013 at 21:08
• @Sniffer define is just to wrap the function as an AMD module. That's how you structure your JavaScript code (one way). – Richard Knop Commented Oct 12, 2013 at 22:13
• I see, but where is it ing from ? an external library ? – Ibrahim Najjar Commented Oct 12, 2013 at 22:14
• @Sniffer requirejs ... anyways the problem was I was calling addChild function and passing multiple arguments.... how stupid of me :) – Richard Knop Commented Oct 12, 2013 at 22:33

Add a ment  | 

1 Answer 1

Sorted by: Reset to default 6

The problem is your addChild() method only expects one parameter, but you are passing in multiple nodes to it.

Change your calling code to:

node1.addChild(node2);
node1.addChild(node7);
node1.addChild(node8);

node2.addChild(node3);
node2.addChild(node6);

node3.addChild(node4);
node3.addChild(node5);

node8.addChild(node9);
node8.addChild(node12);

node9.addChild(node10);
node9.addChild(node11);

Or you can change addChild to accept multiple children (probably want to change the name too):

this.addChildren = function () {
    for (var i = 0; i < arguments.length; i++) {
        children.push(arguments[i]);
    }
};

本文标签： algorithmJavaScript Depthfirst searchStack Overflow