例では、Python がバックトラッキング メソッドのサブセット ツリー テンプレートに基づいてグラフ トラバーサル関数を実装する方法を説明します。

この記事では主にバックトラッキング手法サブセットツリーテンプレートに基づいたPythonのグラフトラバーサル機能を紹介し、グラフトラバース問題に対するバックトラッキング手法サブセットツリーテンプレートを使用したPythonの関連操作スキルと注意事項を例の形で分析します。以下を参照してください

この記事の例では、Python がバックトラッキング メソッドのサブセット ツリー テンプレートに基づいてグラフ トラバーサル関数を実装する方法を説明します。参考のためにみんなに共有してください:

質問

A 写真:

A --> B

A --> ; D
C --> D
D --> C
F --> D

グラフ内のノード E から始まり、他のすべてのノードを繰り返しなく通過し、開始ノード E に戻ることをパスと呼びます。考えられるすべてのパスを見つけてください。



分析

このグラフを次のように視覚化します:

この質問にはグラフが含まれるため、最初にグラフがどのような種類の記憶構造で表されるかを考慮する必要があります。隣接行列、隣接リストなどはあまり馴染みがありません。

前の記事 http://www.jb51.net/article/122927.htm には、最も単純な隣接リスト表現が記載されています。

次に、問題自体を分析します。

明らかに、問題の解の長さは固定されています。つまり、すべてのパスの長さは固定されています: n (開始ノードに戻らない) または n+1 (開始ノードに戻りません)開始ノード) ノード)

各ノードには独自の隣接ノードがあります。

ノードの場合、そのノードに隣接するすべてのノードは、このノードの状態空間と見なすことができます。その状態空間を走査し、プルーニングし、深さ優先で次のノードまで再帰します。終わり！

この時点で、バックトラッキングメソッドのサブセットツリーテンプレートを適用することは明らかです。

コード:

'''
图的遍历
从一个节点出发，不重复地经过所有其它节点后，回到出发节点。找出所有的路径
'''
# 用邻接表表示图
n = 6 # 节点数
a,b,c,d,e,f = range(n) # 节点名称
graph = [
  {b,c},
  {c,d,e},
  {a,d},
  {c},
  {f},
  {c,d}
]
x = [0]*(n+1) # 一个解（n+1元数组，长度固定）
X = []     # 一组解
# 冲突检测
def conflict(k):
  global n,graph,x
  # 第k个节点，是否前面已经走过
  if k < n and x[k] in x[:k]:
    return True
  # 回到出发节点
  if k == n and x[k] != x[0]:
    return True
  return False # 无冲突
# 图的遍历
def dfs(k): # 到达（解x的）第k个节点
  global n,a,b,c,d,e,f,graph,x,X
  if k > n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n）
    print(x)
    #X.append(x[:])
  else:
    for node in graph[x[k-1]]: # 遍历节点x[k]的邻接节点（x[k]的所有状态）
      x[k] = node
      if not conflict(k): # 剪枝
        dfs(k+1)
# 测试
x[0] = e # 出发节点
dfs(1)  # 开始处理解x中的第2个节点

レンダリング:

以上が例では、Python がバックトラッキング メソッドのサブセット ツリー テンプレートに基づいてグラフ トラバーサル関数を実装する方法を説明します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。