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 を実行し、cycle 関数のこれらの出力に対して関数をスタックする必要があることがわかっているからです。私は自分の論文でこれを解決できますが、D2 の長さがゼロまたは tmp_stk 0 の長さをチェックする while ループを使用してこれらの関数を使用する方法がわかりません。

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 に答える