javascript - 递归累积从 Javascript 对象到数组的路径

Question

我试图在以下 Javascript 对象中查找节点的所有子元素。

var graphObj = {

        a : {
            'true' : ['e', 'i'],
            'false' : ['u'],
            'blah' : 'extra key'
        },
        e : {
            'true' : ['o'],
            'false' : ['v'],
            'blah' : 'extra key'
        },
        f : {
            'true' : [],
            'false' : [],
            'blah' : 'extra key'
        },
        i : {
            'true' : [],
            'false' : ['f'],
            'blah' : 'extra key'
        },
        o : {
            'true' : [],
            'false' : [],
            'blah' : 'extra key'
        },
        u: {
            'true': [],
            'false': [],
            'blah' : 'extra key'
        },
        v: {
            'true': [],
            'false': [],
            'blah' : 'extra key'
        },
        z: {
            'true': [],
            'false': [],
            'blah' : 'extra key'
        },

    };

此方法将返回给定节点的子节点

var getChilds = function (opId) {


            var r;

            if (graphObj.hasOwnProperty(opId)) {

                var t = graphObj[opId].true.slice();
                var f = graphObj[opId].false.slice();

                r = t.concat(f);


            } else {
                console.log('No node found with the ID');
            }

            return r;

        }

        console.log(getChilds('a'));

current [output] => ['e', 'i', 'u']

但我需要一种通过递归遍历图形来累积所有子节点的方法。

required output => ['e', 'i', 'u', 'o', 'v', 'f']

有人可以帮助我吗？

注意:这是一个有向图。没有循环。此外，true 和 false 是存储边类型的节点上的唯一键。

Answer 1

我考虑了您的“顺序无关紧要”评论，并确保仅包含 ['true', 'false'] 作为要遍历的边缘类型键。

var graphObj = {

        a : {
            'true' : ['e', 'i'],
            'false' : ['u']
        },
        e : {
            'true' : ['o'],
            'false' : ['v']
        },
        f : {
            'true' : [],
            'false' : []
        },
        i : {
            'true' : [],
            'false' : ['f']
        },
        o : {
            'true' : [],
            'false' : []
        },
        u: {
            'true': [],
            'false': []
        },
        v: {
            'true': [],
            'false': []
        }
    };
console.log(getChildren('a')); // [ 'e', 'o', 'v', 'i', 'f', 'u' ]


function getChildren(entry) {
    var visited = {};
    var children = {};
    traverse(entry);
    return Object.keys(children);
    function traverse (entry) {
        if (visited[entry]) {
            return;
        }
        if (!graphObj[entry]) {
            throw new Error('Node "' + entry + '" does not exist in graph!');
        }
        var edgeTypes = ['true', 'false'];
        // USE THIS LINE FOR ARBITRARY EDGE TYPES
        // var edgeTypes = Object.keys(graphObj[entry]);
        visited[entry] = true;
        edgeTypes.forEach(function(edgeType) {
            var nodeList = graphObj[entry][edgeType] || [];
            nodeList.forEach(function(nodeLetter) {
                children[nodeLetter] = true;
                traverse(nodeLetter);
            });
        });
    }
}