Hierholzer尋找歐拉循環的算法Python

我是Graph理論的初學者。自從5天以來，我一直試圖使用Python將Hierholzer的算法實現爲代碼。迄今爲止，我對圖論的經驗也是5天。我的代碼如下：Hierholzer尋找歐拉循環的算法Python

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的長度。我很高興看到您的建議。

來源

2016-02-19 Yousuf

末添加此功能：

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-19 18:26:01 Yousuf

Hierholzer尋找歐拉循環的算法Python

回答

相關問題