用JavaScript在图中创建一个距离查找表

Question

我有带有id的对象和包含元素a的id和元素b的id的连接对象。

function Item(){
   this.id = id;
}

function Line(startId, targetId){
   this.startId = startId;
   this.targetId = targetId;
}


const lines = [
    new Line(1, 2),
    new Line(2, 3),
    new Line(2, 4),
    new Line(2, 7),
    new Line(3, 5),
    new Line(4, 6),
    new Line(5, 2),
    new Line(7, 3),
    new Line(7, 4),
];

我想为项目X创建一个查找表，这意味着我想要计算从当前项目到项目X的距离。

​

​

itemId 1的结果应该如下所示

项目深度

1%-0

2/2-1

3/2

4/2

5/3

6-3

7/3

我开始创建这个算法

getLookUpTable(targetId){
    const lookUpTable = [];
    let openList = this.lines;

    this.checkTableItems(openList, targetId, 0, lookUpTable);

    return lookUpTable;
}

checkTableItems(openList, currentTargetId, currentLevel, lookUpTable){
    while (openList.length > 0) {
        currentLevel++;

        const targetLines = this.getLinesByTargetId(currentTargetId, openList);

        targetLines.forEach(line => {
            this.addLineToTable(line, currentTargetId, lookUpTable, currentLevel, openList);
        });
    }
}

addLineToTable(line, currentTargetId, lookUpTable, currentLevel, openList){
    const itemId = line.targetId == currentTargetId ? line.startId : activity.toId;
    this.addTableItem(lookUpTable, itemId, currentLevel);
    this.checkTableItems(openList, itemId, currentLevel, lookUpTable);
}

getLinesByTargetId(currentTargetId, openList){
    const targetLines = this.getTargetLines(currentTargetId, openList);
    openList = this.removeTargetLines(currentTargetId, openList);
    return targetLines;
}

getTargetLines(currentTargetId, openList){
    return openList.filter(x => x.startId == currentTargetId || x.targetId == currentTargetId);
}

removeTargetLines(currentTargetId, openList){
    return openList.filter(x => x.startId != currentTargetId && x.targetId != currentTargetId);
}

addTableItem(lookUpTable, id, cost){
    lookUpTable.push({
        id: id,
        cost: cost
    });
}

但是我遇到了堆栈溢出，因为查找表越来越大。

如何使循环递归，以便正确检查所有元素相对于目标项的深度？

Answer 1

下面是另一种方法:将行列表转换为相互引用的节点树。然后递归地下行该树，如果尚未访问该节点，则添加该节点的深度，否则在此结束以防止无限循环：

// Build the tree:

const items = {};

for(const {startId, targetId} of lines) {
  if(!items[startId]) items[startId] = { id: startId, next: [] };
  if(!items[targetId]) items[targetId] = { id: targetId, next: [] };
  items[startId].next.push(items[targetId]);
}

// Get the depth:
function addDepth(node, depth) {
  if(node.depth) return;
  node.depth = depth;
  node.next.forEach(node => addDepth(node, depth + 1));
}
addDepth(items[1], 1)