檢查給定的頂點度是否在 Python 中表示一個圖或樹

假設我們有一個頂點度列表。我們必須檢查它形成的是圖還是樹。

所以，如果輸入是 deg = [2,2,3,1,1,1]，那麼輸出將是樹

為了解決此問題，我們將按照以下步驟操作 −

• vert := 頂點數
• deg_sum := 所有頂點的所有度值的和
• 如果 2*(vert-1) 等於 deg_sum，則
  • 返回 '樹'
• 返回 '圖'

讓我們看看以下實現以獲得更好的理解 −

示例程式碼

線上演示

def solve(deg):
   vert = len(deg)
   deg_sum = sum(deg)
     
   if 2*(vert-1) == deg_sum:
      return 'Tree'
   return 'Graph'

deg = [2,2,3,1,1,1]
print(solve(deg))

輸入

[2,2,3,1,1,1]

輸出

Tree

Arnab Chakraborty

更新於：2021-1-16

164 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始