首页 文章

从图中消除顶点[关闭]

提问于
浏览 次
1

来自Skiena的书，

设计线性时间算法，通过用边（u，w）替换边（u，v）和（v，w），从图中消除2阶的每个顶点v . 我们还试图通过用单个边缘替换它们来消除多个边缘副本 . 请注意，删除边的多个副本可能会创建一个2级的新顶点，必须将其删除，并且删除2级顶点可能会创建多个边，这些边也必须被删除 .

一般来说，我至少有一种方法，对于这个问题，我很无奈 . 这不是新闻，而只是我自己准备面试 .

algorithm graph graph-algorithm depth-first-search breadth-first-search

1 回答

  • 3

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

    基于此，我的总体思路如下 . 我们维护一个需要处理的顶点队列 . 如果顶点具有2的outdegree，或者它具有一个或多个其他顶点的多个边，则必须处理该顶点 . 顶点在发现时放置在队列中 . 当边缘被添加到其中或从中移除时，会发现顶点 .

    处理顶点

    从队列中删除顶点v . 如果它具有2级（即2个邻居），则删除其邻居u和w（O（1））的边缘 to . 如果此边不存在，则在u和w之间添加边（O（1）） . 如果你现在的度数为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调用 .

    回复于

相关问题