我怎样才能从节点和边的集合得到 Root过的树? (我正在使用连接矩阵,每条边都有权重:graph[i][j],没有任何负边)。稍后我需要做 DFS 并在那棵树中找到 LCA,所以这对优化有好处。
最佳答案
我想你的矩阵代表子关系(即 M[i][j]
告诉 j
是 i
的 child ), 对于 directed graph G(V,E) .
你有两种不同的策略:
- 使用位向量,遍历矩阵的每个单元格,如果单元格的权重不为空,则标记向量中的子索引):根是向量中未设置的顶点,
- 查找单元格全部为空(无祖先)的列(或行,如果您的矩阵是列在前),
第二种解决方案更适用于密集矩阵。它最差的运行时间是当根节点是最后一个条目时 (O(V²))。在这种情况下,您可以在第一次点击时停止,或者运行到最后以获取所有根(如果您的图形有很多根)。
第一个更适合稀疏矩阵,因为您必须遍历所有单元格。它的运行时间在 O(E) 中。您还可以使用此算法获得所有根。
如果您确定您的图形只有一个根,则可以使用边向上行走技术,如其他答案中所述。
关于algorithm - 树根查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6962418/