有向图中两个顶点之间的循环

Question

我知道在无向图中必须至少有三个顶点才能形成一个循环。我的问题是，在有向图中，如果两个顶点有两条边互相指向对方，是否被视为循环？

这是一个例子：

这是循环图吗？

相关问题：

• 无向图中，最简单的环必须有3个节点？
• 图的任意两个顶点之间存在环
• 无向图中的循环

Answer 1

如果存在从某个顶点开始并在同一顶点结束的非空路径，则图存在循环。在上图中，路径 上有一个循环A -> C -> A。同样，让我们​​想象一个有 2 个顶点A和B2 个边AB和BA（其中第一个字母是源顶点）的有向图。这意味着存在一个环A -> B -> A，因此在 2 个顶点的有向图中可以有一个环。