在Python中寻找星形图的中心的程序

假设我们有一个未定向的星形图，有n个从1到n标记的节点。我们知道，星形图是一个图，其中有一个中心节点和n-1条边，连接中心节点和每个其他节点。我们需要找到给定星形图的中心。

所以，如果输入是这样的：

那么输出将是3，因为3位于中心。

要解决这个问题，我们将按照以下步骤进行 –

• seen := 一个新集合

• 对于图中的每一条边（u，v），做如下操作

  • 如果u在seen中，则
    • 返回u
  • 如果v在seen中，则
    • 返回v
  • 将u插入seen中

  • 将v插入seen中

例子

我们看下面的实现，以便更好地理解 –

def solve(graph):
   seen = set()

   for u,v in graph:
      if u in seen:
         return u
      if v in seen:
         return v
      seen.add(u)
      seen.add(v)

graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))

输入

[(1,3),(2,3),(4,3),(5,3),(6,3)]

输出

3