一种从有向图计算线有向图的有效算法

Question

有谁知道从有向图计算线有向图的有效算法？ 请参阅 http://en.wikipedia.org/wiki/Line_graph （维基百科文章提到底部附近的有向图情况（在“概括”部分中）理想情况下，我想在线性时间内完成此

操作：

• 如果 G 是有向图，则其有向线图或线有向图 G 的每条边都有一个顶点。
• 向边的两个顶点通过线图中从 uv 到 wx 的边连接。

当 v = w 时，表示 G 中从 u 到 v 和从 w 到 x 的有 设 L(G) 为有向线图

给定 G 时，我可以想出生成 L(G) 的算法是：

• 迭代 G 的所有边以生成 L(G) 的节点
• 迭代所有节点对 (uv , wx) 在 L(G) 中并在 v = w 时连接

这是一个 O(n^2) 算法。

似乎应该有一种方法可以将其降低到 O(n) 时间。 我要去考虑这个，但我想我会问堆栈溢出，以防万一有一些我不知道的著名（或不那么著名）算法来执行此操作。

Answer 1

你不能逃避 O(n^2)，因为有一些图具有线性图，其边的基数等于原始图的顶点基数的平方：例如，想一想，在具有 n+1 个顶点的图，其中一个顶点连接到其他所有顶点：然后您必须构建一个具有 n 个顶点的团，因此具有 (n-1)^2 条边。

算法的复杂性自下而上受其产生的输出大小的限制。

当然，这并不意味着我们不必寻找智能算法。 我曾经这样想过：

LG(LN,LE) getLinearGraph(G(N,E)) {
  LN = EmptySet();
  LE = EmptySet();
  for (Vertex v : N) {
    verticesToAdd = EmptySet()
    for (Vertex i : out-degree(v) {
      toAdd += textual-rep((v,i));
    }
    LN += toAdd;
    LE += make-clique(toAdd);
  }
}

Answer 2

嗯...我认为经过一番思考后可能会有一种更省时的算法...但它需要大量的簿记和大量的额外内存才能做到这一点。

我的基本想法是循环 G 中的所有节点，并从连接到每个节点的边创建连接的节点。 通过额外的链接来跟踪 G（边）到 L（G）（节点），您可能只需通过 G 上的节点进行一次循环即可摆脱困境。