예는 Python이 역추적 방법 하위 집합 트리 템플릿을 기반으로 그래프 순회 기능을 구현하는 방법을 설명합니다.

이 글에서는 역추적 방법 부분 집합 트리 템플릿을 기반으로 Python의 그래프 순회 기능을 주로 소개하고, 그래프 순회 문제에 대한 역추적 방법 부분 집합 트리 템플릿을 사용하여 Python의 관련 조작 기술과 주의 사항을 예제 형식으로 분석합니다. 다음을 참조할 수 있습니다.

이 문서의 예에서는 Python이 역추적 방법 하위 집합 트리 템플릿을 기반으로 그래프 순회 기능을 구현하는 방법을 설명합니다. 다음과 같이 참조용으로 모든 사람과 공유하세요.

A 사진: A --> C

B --> ; D

B --> E

C --> D

D --> F
F --> D

그래프의 노드 E에서 시작하여 다른 모든 노드를 반복 없이 통과하고 시작 노드 E로 돌아오는 것을 경로라고 합니다. 가능한 모든 경로를 찾아보십시오.



Analytics

이 그래프를 다음과 같이 시각화하세요.

이 질문은 그래프와 관련되므로 먼저 그래프가 어떤 종류의 저장 구조로 표현되는지 고려해야 합니다. 인접 행렬, 인접 목록 등은 나에게 익숙하지 않습니다. 이전 기사인 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!