如何在线性时间找到超级巨星？

cs.stackexchange https://cs.stackexchange.com/questions/411

  •  16-10-2019
  •  | 
  •  

题

考虑定向图。我们称节点$ v $ 超级明星 如果并且只有从中无法从中获得其他节点，但是所有其他节点都具有优势到$ v $。正式：

美元

$ n $图中的节点数量。例如，在下图中，未填充的节点是超级巨星（其他节点不是）。

A Superstar
[资源]

您如何在$ Mathcal {o}（n）$时间中识别有向图中的所有超级巨星？可以从 通常的候选人;请不要使用将问题的复杂性进行预处理的表示形式。

没有关于密度的假设。我们不认为该图包含超级巨星。如果没有，则该算法应该识别它。

符号: ：$ mathrm {Outdeg} $是节点的传出边缘数，$ mathrm {indeg} $对于传入边缘类似。

有帮助吗？

解决方案

我们可以通过检查$ N-1 $边缘的存在来消除除一个顶点以外的所有顶点，因为我们可以消除检查每个边缘的一种可能性。特别是，如果有一个从$ x $到$ y $的边缘，我们消除了$ x $，并转移到$ y $（可以从中达到另一个顶点）；如果没有，我们将消除$ y $（因为它无法从$ x $达到）。一旦我们到达最后一个顶点，应与彼此的顶点进行比较（确保维持超级巨星条件：有一个边缘，但不会传出），直到被消除或确认为超级巨星。一些伪代码：

vertex superstar(graph g)
    current vertex = first
    # Go through each vertex
    for each subsequent vertex in g ("next")
        # If there's an edge from this to the next, we eliminate this one [move to the new one].
        # If not, we just stay here.
        if edge exists from current to next
            candidate = next
        end if
    end for
    # Now we are on the final remaining candidate, check whether it satisfies the requirements.
    # just a rename for clarity
    candidate = current
    for each other vertex in g
        if edge from current to other exists
            return null 
        else if no edge from other to current
            return null
        end if
    end for
    return candidate
end superstar

让我们浏览一个示例以说明方法。以此数组为单位，顶部和目的地的源顶点在侧面。 1表示边缘：

$$ begin {array} {r | cccc | r}＆1＆2＆3＆4 hline 1＆ - ＆1＆0＆1＆1＆1 2＆1＆ - ＆ - ＆0＆1＆1 3＆3＆ 1＆1＆ - ＆1 4＆1＆1＆1＆0＆ - end {array} $$

我将把我们排除在潜在超级巨星中排除的顶点。我将使用绿色和红色来指示我们在这样做时正在寻找的边缘，并且不包含我们想要的边缘，蓝色以指示我们已经在哪里寻找的边缘。

我们首先查看顶点1和2。

$$ begin {array} {r | cccc}＆1＆2＆3＆4 hline 1＆ - ＆ color {green} {1} {1}＆0＆1 2＆1＆ - ＆ - ＆0＆0 1 3＆1＆1＆ - ＆1 4＆1＆1＆1＆0＆ - end {array} $$绿色数字显示有2到1的边缘，因此我们消除了2和2寻找3到1的边缘：

$$ begin {array} {r | cccc}＆ color {灰色} {2} {2}＆3＆4 hline 1＆ - ＆ color {blue} {1} {1}＆ color {red {red} 0}＆1 color {灰色} {2}＆1＆ - ＆ - ＆1 3＆1＆1＆1＆1＆1＆1 4＆1＆1＆1＆0＆ - end end {array {array {array } $$

我们看到没有这样的边缘，因此我们消除了1，并将3作为当前顶点。回想一下我们已经消除了2，所以看看是否有4到3的优势：

$$ begin {array} {r | cccc}＆ color {灰色} {1} {1}＆ color {灰色} {2} {2}＆3＆4 hline hline color {灰色} {1} {1} {1}颜色{blue} {1}＆ color {blue} {0}＆1 color {灰色} {2} {2}＆1＆ - ＆ - ＆0＆1 3＆1＆1＆1＆ - ＆ color {green {green {green } {1} 4＆1＆1＆1＆0＆ - end {array} $$

有4到3的优势，因此我们消除了4。在这一点上，我们已经消除了除一个顶点（3）以外的所有东西，因此请查看其边缘，看看它是否符合：

$ begin {array} {r | cccc}＆ color {灰色} {1}＆ color {灰色} {2} {2}＆ color {灰色} {4} {4} {4} {1}＆ - ＆ color {blue} {1}＆ color {red} {0}＆1 color {灰色} {2} {2}＆1＆ - ＆ - ＆0＆1 3＆ 3＆ color {绿色} {1}＆1＆ - ＆ color {blue} {1} {1} color {灰色} {4}＆1＆1＆1＆0＆0＆ - end end {array} $$

从1到3的边缘，但反向不相反，因此3仍然是候选人。

$ begin {array} {r | cccc}＆ color {灰色} {1}＆ color {灰色} {2} {2}＆ color {灰色} {4} {4} {4} {1}＆ - ＆ color {blue} {1}＆ color {blue} {0}＆1 color {灰色} {2} {2}＆1＆ - ＆ - ＆ - ＆ color {red} {0} {0} {0}＆1 3＆ color {blue} {1}＆ color {green} {1} {1}＆ - ＆＆ color {blue} {1} color {灰色} {4} {4}＆1＆1＆1＆0＆ - end {array} $$

还有一个从2到3到3的边缘，但不相反，因此3仍然是候选人。

$ begin {array} {r | cccc}＆ color {灰色} {1}＆ color {灰色} {2} {2}＆ color {灰色} {4} {4} {4} {1}＆ - ＆ color {blue} {1}＆ color {blue} {0}＆1 color {灰色} {2} {2}＆1＆ - ＆ - ＆＆ color {blue} {0} {0} {0}＆1 3＆ color {blue} {1}＆ color {blue} {1} {1}＆ - ＆ color {green} {1} {1} color {灰色} {4} {4}＆1＆1＆ color {红色} {0}＆ - end {array} $$

有4到3的边缘，但没有3到4；这完成了我们对3个边缘的检查，我们发现它实际上是一位超级巨星。

由于我们在第一个$ n-1 $ edge Checks中的每个$ n-1 $ edge检查中都取消了一个顶点，因此最好的情况是，$ n $ th检查消除了最终顶点的复杂性。在最坏的情况下（最后一个或倒数第二个顶点是超级巨星，或者最终支票不合格），在第一个$ n-1 $比较之后，我们将候选人与$ 2 times（N-1）$进行比较。顶点，最坏情况的复杂性为$ 3n-3 $（$ o（n）$）。因此，该算法是$ theta（n）$。

其他提示

不是这 名人问题?

如果有一个，只有一位超级巨星（名人）。

我们使用邻接矩阵表示，其中$ a [i，j] = 1 $如果有指向边缘从$ i $到$ j $，否则为$ 0 $。 （我猜这是允许的）。

通过查看$ a [i，j] $（可以在$ mathcal {o}（1）$ time中完成，我们可以至少消除其中一个作为名人的候选人：如果$ a [i， j] = 1 $，然后您可以消除$ i $。如果$ a [i，j] = 0 $，我们可以消除$ j $。

保持当前候选人的清单，消除一一。链接列表就足够了。

最后，您可以验证您的候选人是否确实是超级巨星。

该算法将为$ MATHCAL {O}（n）$。

该答案解决了任何可能的图表表示的问题，而不是问题的当前版本。

  • 将图形存储为一对邻接列表和反向邻接列表，其中每个列表还包含列表的长度，因此分别是数字外和边缘。

  • 预处理：计算反向邻接列表（即边缘列表）。成本$ Mathcal {O}（| e |）$。

  • 遍历列表，然后选择任何节点，而额外编号数为$ 0 $，并且边缘的数量为$ n-1 $。成本$ Mathcal {O}（| n |）$。

仅供参考，这是凯文发布的递归版本的伪代码。

superstar(V, E) {
  if ( |V| == 1 ) {
    return V.pop
  }

  a = V.pop
  b = V.pop
  if ( (a,b) ∈ E ) {
    no_ss = a
    keep  = b
  }
  else {
    no_ss = b
    keep = a
  }

  s = superstar(V ++ keep)

  return ( s != null && (no_ss, s) ∈ E && !(s, no_ss) ∈ E ) ? s : null
}

hasSuperstar(V, E) = superstar(V, E) != null
许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top