比赛图

Question

锦标赛是通过为无向完全图中的每条边指定方向而获得的有向图（有向图）。也就是说，它是一个有向图，其中每对顶点都由一条有向边连接。

数据结构是邻接矩阵。

什么是确定该图是否为锦标赛图的算法？

Answer 1

邻接矩阵中有 n^2 个条目，您需要所有条目中的信息来解决问题。（您需要使用 1 来检查是否存在正确的边，使用 0 来检查后边是否不存在。）因此，由于您必须从矩阵中读取至少 N^2 个条目，因此整个问题必须至少 O(N^2) 时间。

关于 BFS 搜索尝试：如果您的遍历需要 O(n^2) - 由于需要在邻接矩阵中查找边缘 - 那么如果后边缘检查是恒定时间，则无关紧要，整体算法仍然是 O(n^2)。

看待这个问题的另一种方式：由于边的数量等于可能的顶点对的数量，所以将有 n*(n-1)/2 条边，即 O(n^2)。您的遍历是 O(V+E)，因此是 O(n+n^2)，因此是 O(n^2)。

由于此算法的最佳情况时间为 O(n^2)，您不妨简单地遍历矩阵的右上半部分（对角线上方）并检查每个条目是否 a) 是1, 或 b) 它的转置等效值为 1。