Ein Beispiel erklärt, wie Python die Graph-Traversal-Funktion basierend auf der Subset-Tree-Vorlage der Backtracking-Methode implementiert

In diesem Artikel wird hauptsächlich die Graph-Traversal-Funktion von Python basierend auf der Backtracking-Methoden-Subset-Tree-Vorlage vorgestellt und die zugehörigen Bedienfähigkeiten und Vorsichtsmaßnahmen von Python anhand der Backtracking-Methode-Subset-Tree-Vorlage für Graph-Traversal-Probleme in Form von Beispielen analysiert Wer es braucht, kann es Als Referenz:

Dieser Artikel beschreibt das Beispiel der Implementierung der Graph-Traversal-Funktion in Python basierend auf der Teilmengenbaumvorlage der Backtracking-Methode. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Frage

Ein Bild:

A - -> B
A --> C
B --> 🎜>C -->D
E --> Aus dem Bild: Ausgehend von einem Knoten E kehrt es nach dem Durchlaufen aller anderen Knoten ohne Wiederholung zum Startknoten E zurück, der als Pfad bezeichnet wird. Bitte finden Sie alle möglichen Pfade.



Analyse

Visualisieren Sie dieses Diagramm wie folgt:

Diese Frage bezieht sich auf Diagramm, dann müssen wir zunächst überlegen, durch welche Art von Speicherstruktur das Diagramm dargestellt wird. Adjazenzmatrizen, Adjazenzlisten usw. sind nicht sehr bekannt. Der vorherige Artikel http://www.jb51.net/article/122927.htm hat die einfachste Adjazenzlistendarstellung.

Analysieren Sie als Nächstes das Problem selbst:

Offensichtlich ist die Länge der Lösung des Problems festgelegt, dh alle Pfadlängen sind festgelegt: n (ohne zum Startknoten zurückzukehren) Oder n+1 (zurück zum Startknoten)

Jeder Knoten hat seine eigenen Nachbarknoten.

Für einen Knoten können alle benachbarten Knoten als Zustandsraum dieses Knotens betrachtet werden. Durchlaufen Sie seinen Zustandsraum, bereinigen Sie ihn und rekursieren Sie mit der Tiefe zuerst zum nächsten Knoten. Erledigt!

An diesem Punkt ist es offensichtlich, die Backtracking-Teilmengenbaumvorlage anzuwenden.

Code:

Rendering:

'''
图的遍历
从一个节点出发，不重复地经过所有其它节点后，回到出发节点。找出所有的路径
'''
# 用邻接表表示图
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个节点

Das obige ist der detaillierte Inhalt vonEin Beispiel erklärt, wie Python die Graph-Traversal-Funktion basierend auf der Subset-Tree-Vorlage der Backtracking-Methode implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!