0

给定一个有向图，找到图的根，即具有最大输出节点的节点。

这样可以将图划分为最大的个体子树。

4

2 回答 2

-1

假设该图是一个邻接矩阵，您可以扫描每一行以计算相应节点的出边，最后扫描每个节点的这些值以获得最大出度的节点。这将花费 O(n^2) 时间。

于 2013-09-17T07:05:26.607 回答
-1

一张一张地扫描图并将出边的数量存储在排序列表中，然后最大数量与根节点匹配

于 2013-09-17T07:09:43.510 回答