algorithm - 修剪 Octopus - 删除不属于 O(N) 中循环的有向图的所有分支

Question

_{预备知识 - 可以跳过:这个问题与 Longest Path for Directed Cyclic Graph 有关.现在，那里有一点争议，关于仅隔离有向图中的循环、迭代或递归等是多么微不足道或不微不足道，所以我决定将其作为一个问题打开——我想会有是其他非 CS 毕业生(像我一样)，他们将来可能会从清晰且解释清楚的答案中受益。}

现在的问题可以说是“学术性的”——目的是获得尽可能多的答案:

Given a totally connected graph obeying the "exactly one child node for every node" rule (therefore exactly one cycle must exist) remove all nodes not part of the cycle in O(N).

The algo should minimally answer to the question of "what is the length of the cycle", the identity/indexes of the node a bonus. Considerations about complexity (why is O(N)) will be welcomed.

A bonus if the algo can deal with non-totally connected graphs and identify all the cycles (not only the nodes belonging to any cycle, but also separating/tagging them with a cycle identifier).

清晰且解释清楚的解决方案越多，对 future 的答案寻求者越好

这就是为什么我悬赏(以 SO gold 形式)并放宽语言要求的原因。

下图中的一个例子

节点沿线从低到高连接。

如果我没记错的话，邻接向量(索引指定节点，值指定node.next)将显示为

   [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 80,
     11, 12, 13, 14, 15, 16, 17, 18, 19, 81,
     21, 22, 23, 24, 25, 26, 27, 28, 29, 82,
     31, 32, 33, 34, 35, 36, 37, 38, 39, 83,
     41, 42, 43, 44, 45, 46, 47, 48, 49, 84,
     51, 52, 53, 54, 55, 56, 57, 58, 59, 85,
     61, 62, 63, 64, 65, 66, 67, 68, 69, 86,
     71, 72, 73, 74, 75, 76, 77, 78, 79, 87,
     81, 82, 83, 84, 85, 86, 87, 80 ]

其他测试数据:

• 奇点 - [0] 单个节点“ curl ”到自身(就像“弦论”中的额外维度？)
• 活跃的黑洞 - [1,2,2,2] - 索引为 2 的奇点，左右都落在其中
• 倒置套索 - [1,0,1,2,3] - 从循环开始，尾部朝向它

Answer 1

我的回答在原始问题中被接受，所以这里是我的 原始问题的解决方案 作为 JS 片段。运行时间 O(n)，空间 O(n)。

var data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 80,
  11, 12, 13, 14, 15, 16, 17, 18, 19, 81,
  21, 22, 23, 24, 25, 26, 27, 28, 29, 82,
  31, 32, 33, 34, 35, 36, 37, 38, 39, 83,
  41, 42, 43, 44, 45, 46, 47, 48, 49, 84,
  51, 52, 53, 54, 55, 56, 57, 58, 57, 85,
  61, 62, 63, 64, 65, 66, 67, 68, 69, 86,
  71, 72, 73, 74, 75, 76, 77, 78, 79, 87,
  81, 82, 83, 84, 85, 86, 87, 80
];

var visited = new Array(data.length);

var chains = [];

for (var i = 0; i < data.length; i++) {
  if (!visited[i]) {
    var current = {
      chain: chains.length
    }
    var j = i;
    var len = 0;
    do {
      len++;
      visited[j] = current;
      j = data[j];
    } while (!visited[j]);
    if (visited[j].chain === current.chain) {
      chains.push(len);
    } else {
      current.chain = visited[j].chain;
      chains[current.chain] += len;
    }
  }
}

//the visited array now contains information about which chain each node belongs to
document.write("<table><tr>");
for (var i = 0; i < visited.length; i++) {
  document.write("<td>"+i + "=>" + visited[i].chain + "</td>");
  if (i % 10 == 9) {
    document.write("<tr/><tr>");
  }
}
document.write("</table></tr>");
document.write("<p>Chain lengths: " + chains+"</p>");

请注意，发布的数据集在 Octopus 中确实存在“错误”； 57 => 58 => 57 使它成为一个与“ Octopus ”分开的“套索”。

这里是问题的解决方案:

运行时 O(n)，空间 O(n)，导致数组“访问”了循环的 true 部分，false 不是循环的一部分。

var data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 80,
  11, 12, 13, 14, 15, 16, 17, 18, 19, 81,
  21, 22, 23, 24, 25, 26, 27, 28, 29, 82,
  31, 32, 33, 34, 35, 36, 37, 38, 39, 83,
  41, 42, 43, 44, 45, 46, 47, 48, 49, 84,
  51, 52, 53, 54, 55, 56, 57, 58, 59, 85,
  61, 62, 63, 64, 65, 66, 67, 68, 69, 86,
  71, 72, 73, 74, 75, 76, 77, 78, 79, 87,
  81, 82, 83, 84, 85, 86, 87, 80
];

var visited = new Array(data.length);

// Pass 1: mark
for (var i = 0; i < data.length; i++) {
  if (visited[i] == null) {
    var k;
    var j = i;
    do {
      visited[j] = false;
      k = j;
      j = data[j];
    } while (visited[j] == null);
    visited[k] = i == 0;
  }
}
// Pass 2: propagate
var cnt = 0;
for (var i = 0; i < visited.length; i++) {
  if (visited[i]) {
    var j = i;
    do {
      cnt ++;
      visited[j] = true;
      j = data[j];
    } while (j != i);
    break;
  }
}

//the visited array now contains information about nodes belonging to loop
document.write("Count: "+cnt);
document.write("<table><tr>");
for (var i = 0; i < visited.length; i++) {
  document.write("<td>" + i + "=>" + visited[i] + "</td>");
  if (i % 10 == 9) {
    document.write("<tr/><tr>");
  }
}

编辑:如果数据结构中始终只有一个循环，则可以进一步简化过程:

var data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 80,
  11, 12, 13, 14, 15, 16, 17, 18, 19, 81,
  21, 22, 23, 24, 25, 26, 27, 28, 29, 82,
  31, 32, 33, 34, 35, 36, 37, 38, 39, 83,
  41, 42, 43, 44, 45, 46, 47, 48, 49, 84,
  51, 52, 53, 54, 55, 56, 57, 58, 59, 85,
  61, 62, 63, 64, 65, 66, 67, 68, 69, 86,
  71, 72, 73, 74, 75, 76, 77, 78, 79, 87,
  81, 82, 83, 84, 85, 86, 87, 80
];

var visited = new Array(data.length);

// Pass 1: find one item which must be in cycle, max runtime O(n)
var j = 0;
do {
  visited[j] = false;
  j = data[j];
} while (visited[j] == null);
// Pass 2: follow cycle, max runtime O(n)
var cnt = 1;
for (var i = data[j]; i != j; i = data[i]) {
  cnt ++;
  // you could store the cycle nodes here to identify the non-cycle ones
}

//the visited array now contains information about nodes belonging to loop
document.write("Count: "+cnt);

再次编辑:实现了对多周期的支持；将输出所有循环长度和最长循环的节点。复杂度仍然为 O(n)。 :)

var data=[5,4,4,1,3,0];

var visited = new Array(data.length);

var chains = [];

// Pass 1: find all chains - complexity O(n)
for (var i = 0; i < data.length; i++) {
  if (!visited[i]) {
    var current = {
      chain: chains.length
    }
    var j = i;
    var len = 0;
    do {
      len++;
      visited[j] = current;
      j = data[j];
    } while (!visited[j]);
    if (visited[j].chain === current.chain) {
      chains.push(j); // this index is part of a cycle
    } else {
      current.chain = visited[j].chain;
    }
  }
}

// Pass 2: count elements, max complexity O(n) because no node is visited twice and only nodes which are part of a cycle will be visited
var lengths = new Array(chains.length);
var best = [];
for (var i = 0; i < chains.length; i++) {
  var curr = [];
  var j = chains[i];
  do {
    curr.push(j);
    j = data[j];
  } while (j != chains[i]);
  lengths[i] = curr.length;
  if (curr.length > best.length) {
    best = curr;
  }
}

// Output result:
document.write("<p>Identified cycle lengths: "+lengths.join(", ")+"</p>");
document.write("<p>IDs of longest cycle: "+best.join(", ")+"</p>");