Python中构建欧拉回路所需的最少边数

假设我们有一个具有b个节点和一定数量边的无向图；我们必须找到构建欧拉回路所需的最小边数。

因此，如果输入如下所示：

那么输出将是1。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数dfs()。它将接收g、visit、odd_vert、degree、comp、v。
  • visit[v] := 1
  • 如果degree[v] mod 2等于1，则
    • odd_vert[comp] := odd_vert[comp] + 1
  • 对于u in range 0 to size of g[v]，执行：
    • 如果visit[u]等于0，则
      • dfs(g, visit, odd_vert, degree, comp, u)
  • 在主方法中执行以下操作：
  • g := 一个包含n+1个空列表的列表
  • e := 一个新列表
  • o := 一个新列表
  • degree := 一个大小为(n + 1)并填充为0的新列表
  • visit := 一个大小为(n + 1)并填充为0的新列表
  • odd_vert := 一个大小为(n + 1)并填充
  • 为0的新列表
  • 对于i in range 0 to m，执行：
    • 将d[i]插入g[s[i]]的末尾
    • 将s[i]插入g[d[i]]的末尾
    • degree[s[i]] := degree[s[i]] + 1
    • degree[d[i]] := degree[d[i]] + 1
  • ans := 0, comp := 0
  • 对于i in range 1 to n + 1，执行：
    • 如果visit[i]等于0，则
      • comp := comp + 1
      • dfs(g, visit, odd_vert, degree, comp, i)
      • 如果odd_vert[comp]等于0，则
        • 将comp插入e的末尾
      • 否则，
        • 将comp插入o的末尾
  • 如果o的大小等于0且e的大小等于1，则
    • 返回0
  • 如果o的大小等于0，则
    • 返回e的大小
  • 如果e的大小不等于0，则
    • ans := ans + e的大小
  • 对于i in range 0 to o的大小，执行：
    • ans := ans + odd_vert[i] / 2（只取整数部分）
  • 返回ans

示例

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

 在线演示

def dfs(g, visit, odd_vert, degree, comp, v):
   visit[v] = 1
   if (degree[v] % 2 == 1):
      odd_vert[comp] += 1
   for u in range(len(g[v])):
      if (visit[u] == 0):
         dfs(g, visit, odd_vert, degree, comp, u)
def solve(n, m, s, d):
   g = [[] for i in range(n + 1)]
   e = []
   o = []
   degree = [0] * (n + 1)
   visit = [0] * (n + 1)
   odd_vert = [0] * (n + 1)
   for i in range(m):
      g[s[i]].append(d[i])
      g[d[i]].append(s[i])
      degree[s[i]] += 1
      degree[d[i]] += 1
   ans = 0
   comp = 0
   for i in range(1, n + 1):
      if (visit[i] == 0):
         comp += 1
         dfs(g, visit, odd_vert, degree, comp, i)
         if (odd_vert[comp] == 0):
            e.append(comp)
         else:
            o.append(comp)
   if (len(o) == 0 and len(e) == 1):
      return 0
   if (len(o) == 0):
      return len(e)
   if (len(e) != 0):
      ans += len(e)
   for i in range(len(o)):
      ans += odd_vert[i] // 2
   return ans
b = 3
a = 2
source = [ 1, 2 ]
destination = [ 2, 3]
print(solve(b, a, source, destination))

输入

b = 3 a = 2 source = [ 1, 2 ] destination = [ 2, 3]

输出

1

更新于：2020年8月27日

97 次查看

开启您的职业生涯

完成课程获得认证

开始学习
广告