检查给定的顶点度是否在 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 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始