1

我是图论的初学者。自 5 天以来，我一直在尝试使用 Python 将 Hierholzer 的算法实现到代码中。到目前为止，我的图论经验也是 5 天。我的代码如下：

def cycle(D1):
    import random
    key = list(D1.keys())
    ran_k = random.choice(key)
    tmp_stk = []
    tmp_stk += [ran_k]
    r_stack = []
    if len(D1[ran_k]) > 1:
        tmp_stk += [D1[ran_k][0]]
        del D1[ran_k][0]
    else:
        tmp_stk += D1[ran_k]
        del D1[ran_k]
   flag = True
   while flag:
       try:
           if len(D1[tmp_stk[-1]]) > 1:
              tmp_stk += [D1[tmp_stk[-1]][0]]
              del D1[tmp_stk[-2]][0]
           else:
              tmp_stk += D1[tmp_stk[-1]]
              del D1[tmp_stk[-2]]
       except (KeyError):
            flag = False
            return D1,tmp_stk

def stack(tmp_stk,D1):
    r_stack = []
    if len(D1):
        for i in tmp_stk[::-1]:
            if i in D1.keys():
                 r_stack += tmp_stk[tmp_stk.index(i)+1:][::-1]
                 tmp_stk = tmp_stk[:tmp_stk.index(i)+1]
        return tmp_stk,r_stack
    else:
        r_stack += [tmp_stk[::-1]]
        return tmp_stk,r_stack

def cycle2(D1,tmp_stk):
    flag = True
    while flag:
        try:
           if len(D1[tmp_stk[-1]]) > 1:
              tmp_stk += [D1[tmp_stk[-1]][0]]
              del D1[tmp_stk[-2]][0]
           else:
              tmp_stk += D1[tmp_stk[-1]]
              del D1[tmp_stk[-2]]
        except (KeyError):
             flag = False
      return D1,tmp_stk

D2 = {0:[3],1:[0],2:[1,6],3:[2],4:[2],5:[4],6:[5,8]
     , 7:[9],8:[7],9:[6]}

D2图是连通的，每个节点的度数是偶数。当 ran_k 选择 6 作为起始节点且欧拉回路为 [6, 5, 4, 2, 1, 0, 3, 2, 6, 8, 7, 9, 6] 时，我的代码（循环函数）工作正常。任何起始节点都有欧拉回路，因为 D2 图是强连通的，所有节点的度数都是偶数。

当ran_k选择0作为起始节点时，我的循环函数返回如下：剩余图：{2：[6]，4：[2]，5：[4]，6：[5,8]，7：[9]， 8: [7], 9: [6]} 和临时堆栈为：[0, 3, 2, 1, 0]。这也没关系，因为我知道我必须在循环函数的这些输出上运行 cycle2 和 stack 函数。我可以在我的论文上解决这个问题，但我不知道如何使用 while 循环检查 D2 的长度为零或 tmp_stk 的长度为 0 来使用这些函数。我很高兴看到你的建议。

4

1 回答 1

0

在最后添加这个函数：

def main(D):
d,ts = cycle(D)
if len(d):
    #flag = True
    r_s = []
    while len(d):
          #r_s = []
          ts,rs1,d = stack(ts,d)
          r_s += rs1
          d,ts = cycle2(d,ts)
    circle =  r_s+ts[::-1]
    return circle[::-1]
else:
    return ts
于 2016-02-19T18:26:01.800 回答