检查有向图是否完整的算法

Question

是否有用于检查图是否为完整有向图的已知算法？

理想情况下，我想从JGraphT Java 库中找到一个现成的方法。

或者，我找到了以下关于无向图完整性检查的答案。以下修改是否适用于检查有向图的完整性？

1. 检查图中有向边的数量是n(n-1)

2. 检查每个顶点是否直接连接到完全n-1不同的顶点

如果我没有遗漏任何东西并且这些条件足够，我可以自己实施这些检查，但如果可能的话我更愿意使用库中的现有实施。

Answer 1

你能试试这个 JGraphT 方法吗？GraphTests#isComplete它说它也检查有向图。测试图形是否完整。完全无向图是一个简单的图，其中每对不同的顶点都由唯一的边连接。完全有向图是这样一种有向图，其中每对不同的顶点都由一对唯一的边（每个方向一条）连接。

Answer 2

如果您的图表没有超过一条边往返于相同的节点，这是最简单的方法。你不能有一个不完整的图形，并且有那么多边而没有重复的(n*(n-1))边。