1

我想从图中获得最长的路径，其中每个对象可能相互连接。甚至每个对象都可以连接到自身。我想计算从 id 为 1 的元素到其他每个元素的最长路径。

由于所有连接都是可能的，我必须注意循环，因为代码可能会陷入无限循环。

我创建了以下对象

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

function Connection(startElementId, targetElementId) { // Connection between element A and B
  this.startElementId = startElementId;
  this.targetElementId = targetElementId;
}

function Connector(id, predecessor) { // Object within a full path of connections with a predecessor and successors
  this.id = id;
  this.predecessor = predecessor;
  this.successors = [];
}

并从一些随机数据开始

const elements = [
  new Element(1),
  new Element(2),
  new Element(3),
  new Element(4),
  new Element(5),
  new Element(6),
  new Element(7),
  new Element(8),
  new Element(9),
  new Element(10)
];

const connections = [
  new Connection(7, 5),
  new Connection(9, 2),
  new Connection(4, 6),
  new Connection(3, 6),
  new Connection(8, 2),
  new Connection(1, 8),
  new Connection(7, 9),
  new Connection(2, 5),
  new Connection(4, 7),
  new Connection(9, 6),
  new Connection(3, 4),
  new Connection(1, 7),
  new Connection(5, 3),
  new Connection(9, 4)
];

因此，我创建了一个算法，该算法应该返回这些连接可能的最长路径。

   elements.forEach(element => {
      const maxLevel = getElementMaxLevel(element);
      // maxLevel is the result of this element
    });


  getElementMaxLevel(element){
    const elementId = element.id;

    const rootConnector = new StageConnector(1, null);  // always start with the first id without a predecessor
    const examinedIds = []; // Push all visited IDs here
    examinedIds.push(rootConnector.id); // add the first connector
    this.setupConnectionPaths(rootConnector, elementId, examinedIds); // start recursion

    return getHighestLevelFromConnector(rootConnector, elementId); // get the longest path from the first connector
  }

  setupConnectionPaths(currentConnector, targetId, examinedIds){
    const connectorId = currentConnector.id;

    if(connectorId != targetId){ // Element is connected to itself?

      const tempConnections = connections.filter(x => x.startElementId == connectorId); // Just take the connections that have the startElementId of the current connector

      tempConnections.forEach(connection => { // Examine all connections

        const toId = connection.targetElementId; // current targetElementId of this connection
        const idExamined = examinedIds.some(x => x == toId); // targetElementId visited before?

        if(!idExamined){

          const idIsTargetId = toId == targetId; // targetElementId is targetId
          const successorConnectionsExist = connections.some(x => x.startElementId == toId); // Are there more connections at one connection?

          if(idIsTargetId || successorConnectionsExist){

            const subConnector = new StageConnector(toId, connectorId); // create a new sub connection for the path
            currentConnector.successors.push(subConnector); // append the sub connector to the current connector

            examinedIds.push(subConnector.id); // mark the id as visited

            if(successorConnectionsExist){ // recursive search for the next connections
              this.setupConnectionPaths(subConnector, targetId, examinedIds);
            }
          }
        }
      });
    }
  }

  getHighestLevelFromConnector(connector, stageId){

    // remove all paths that don't finish with the stageId as their last connector id
    // get the length of the longest path

    return 0;
  }

不知何故，我没有陷入无限循环，也没有得到任何错误，但算法没有返回正确的路径。

当前元素的起始连接器没有以当前目标 id 结尾的正确路径。

4

0 回答 0