0

从斯基纳的书中，

设计一个线性时间算法，通过用边 (u,w) 替换边 (u,v) 和 (v,w) 从图中消除每个 2 次顶点 v。我们还试图通过用单个边缘替换它们来消除边缘的多个副本。请注意，删除一条边的多个副本可能会创建一个 2 度的新顶点，必须将其删除，而删除 2 度的顶点可能会创建多个边，也必须将其删除。

一般来说，我至少有一个办法，对于这个问题，我很无奈。这不是 Hw，而只是我自己为面试做的准备。

4

1 回答 1

3

这个问题有两个线索 - 线性时间要求和多副本洞察力。第一个建议不应该处理超过固定次数的顶点，第二个建议需要维护一个队列来决定接下来访问哪个顶点。

基于此，我的总体思路如下。我们维护一个需要处理的顶点队列。如果一个顶点的出度为 2，或者它与一个或多个其他顶点具有多条边，则必须对其进行处理。顶点在被发现时被放置在队列中。向顶点添加或删除边时会发现顶点。

处理一个顶点

从队列中删除顶点v 。如果它的度数为 2（即 2 个邻居），则删除其邻居 u 和 w 的边（ O ( 1 )）。如果这样的边不存在 (O(1))，则在u和w之间添加一条边。如果u现在的度数为 2 并且尚未在队列中，则添加到队列的前面。对w做同样的事情。（每个 O(1)）

Algorithm ProcessVertex(v, Q)
  Remove v from Q;
  IF Degree(v) == 2 and Seen(v) == False:
    Seen(v) = True
    u = Adj(v).first;
    RemoveEdge(u,v);
    w = Adj(v).first;
    RemoveEdge(u,w);
    IF !IsEdge(u,w)
      AddEdge(u,w);

算法

遍历顶点列表。对于每个顶点，如果度数为2，则将其加入队列；否则什么也不做。

当队列不为空时，处理前面的顶点。

Algorithm EliminateVertices(G)
  Q = empty queue;
  FOR v in G
    IF Degree(v) == 2
      EnqueueFront(v,Q);

  WHILE !IsEmpty(Q)
    ProcessVertex(Front(Q), Q);

线性复杂度的证明

  • 我们可以在 O(1) 时间内检查两个顶点i和j之间是否已经存在一条边。这是使用邻接矩阵表示来实现的。在 O(1) 时间内跟踪每个节点的度数也很容易 - 只需在分别向节点添加/删除边时增加或减少计数。因此，每个 ProcessVertex 调用都需要 O(1) 时间。
  • 每个顶点最多处理一次。证明：一个顶点一旦从队列中移除就不再存在。我们还可以有效地（O(1)）确保一个顶点不能多次添加到队列中（在每个顶点中标记它是否已经在队列中，如果是则不添加）。因此，最多有 O(n) 个 ProcessVertex 调用。
于 2013-04-21T00:24:44.047 回答