algorithm - 树根查找

Question

我怎样才能从节点和边的集合得到 Root过的树？(我正在使用连接矩阵，每条边都有权重:graph[i][j]，没有任何负边)。稍后我需要做 DFS 并在那棵树中找到 LCA，所以这对优化有好处。

Answer 1

我想你的矩阵代表子关系(即 M[i][j] 告诉 j 是 i 的 child ), 对于 directed graph G(V,E) .

你有两种不同的策略:

• 使用位向量，遍历矩阵的每个单元格，如果单元格的权重不为空，则标记向量中的子索引):根是向量中未设置的顶点，
• 查找单元格全部为空(无祖先)的列(或行，如果您的矩阵是列在前)，

第二种解决方案更适用于密集矩阵。它最差的运行时间是当根节点是最后一个条目时 (O(V²))。在这种情况下，您可以在第一次点击时停止，或者运行到最后以获取所有根(如果您的图形有很多根)。

第一个更适合稀疏矩阵，因为您必须遍历所有单元格。它的运行时间在 O(E) 中。您还可以使用此算法获得所有根。

如果您确定您的图形只有一个根，则可以使用边向上行走技术，如其他答案中所述。