如何执行符合我需求的Javascript对象递归搜索？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了如何执行符合我需求的Javascript对象递归搜索？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3706字，纯文字阅读大概需要6分钟。

内容图文

美好的一天,

我正在研究用Javascript编写的基于文本的游戏.我有变量命名映射,它是一个关联对象,包含每个房间的另一个对象.我在某个地方找到了一个小算法,我不知道如何根据我的具体任务修改它.

我的变量：

/**
 *       [003]-[004]
 *         |     |
 * [001]-[002] [007]
 *         |     |
 *       [005]-[006]
 **/     
var map = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "N" : "",
            "S" : "",
            "E" : "002",
            "W" : ""
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "E" : "",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "N" : "",
            "S" : "002",
            "E" : "004",
            "W" : ""
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "N" : "",
            "S" : "007",
            "E" : "",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "S" : "",
            "E" : "006",
            "W" : ""
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "S" : "",
            "E" : "",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006",
            "E" : "",
            "W" : ""
        }
    }
};


function findSteps( id, map, array ) {
    if ( ! ( map && "object" === typeof map ) ) { return; }
    if ( map.Id === id ) { return map; }

    for ( var x in map ) {
        if ( Object.hasOwnProperty.call( map, x ) ) {
            map.Id && array.push( map.Id ); //used to exclude undefined
            var result = findSteps( id, map[ x ], array );

            if ( result !== undefined ) {
                return [ result, array ];
            }
        }
    }
}

console.dir( findSteps( "004", map, [] ) );
// Actually returns [objectObject],001,001,001,002,002,002,003,003,003

我希望该函数返回一个包含所有可能路径的数组数组,稍后我将迭代这些路径以找到最接近的可用路径.

期望的结果将是这样的：

output = [
    [ "001", "002", "003", "004" ],
    [ "001", "002", "005", "006", "007", "004" ]
]

该函数还应该接受启动ID.如果在“map.length”n次迭代之前没有找到任何内容,我正在考虑停止递归的事情.

也许有点暗示也会受到赞赏.

谢谢！

http://jsfiddle.net/GxZYX/

PS：我已经看过关于递归对象搜索的一些Q / A创建,这正是我找到我正在使用的函数的地方.

编辑：

经过多次思考,希望我不会错.我相信我只需要最短路径.

编辑：

http://jsfiddle.net/GxZYX/1/这是我对实现广度优先搜索的测试. (窃听)

解决方法:

要在像你这样的非直观图中找到两个节点之间的最短路径,你只需要做一个Breadth-first-search.

function linkedPathToList(next, node){
    var path = [];
    while(true){
        path.push(node);
        if(node == next[node]) break;
        node = next[node];
    }
    return path;
}       

var breadthFirstSearch = function( map, startRoomId, endRoomId ) {

    var next = {};
    next[endRoomId] = endRoomId;

    var currentLevel = [ map[endRoomId] ];

    //(the traditional version of the algorithm uses a queue instead of the
    // complicated two-array thing though)

    while( currentLevel.length ) {

        //if curr level is nodes at distance d from the end
        //next level is d+1
        var nextLevel = [];

        for(var i=0; i<currentLevel.length; i++) {
            var node = currentLevel[i];

            if ( node.Id == startRoomId ) {
                return linkedPathToList(next, startRoomId);
            }

            for( var direction in node.Directions ) {
                var neighbor = node.Directions[direction]; 
                if( !next[neighbor] ) {
                    next[neighbor] = node.Id;
                    nextLevel.push( map[neighbor] );
                }
            }
        }

        currentLevel = nextLevel;
    }

    return null;
};

var map = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "E" : "002"
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "S" : "002",
            "E" : "004"
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "S" : "007",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "E" : "006"
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006"
        }
    }
};

console.log('shortest path',  breadthFirstSearch( map, "001", "004" ) );

内容总结

以上是互联网集市为您收集整理的如何执行符合我需求的Javascript对象递归搜索？全部内容，希望文章能够帮你解决如何执行符合我需求的Javascript对象递归搜索？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端