用 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

Arnab Chakraborty

更新時間：2021 年 10 月 6 日

476 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始