cari
Rumahpembangunan bahagian belakangTutorial Python实例讲解Python基于回溯法子集树模板实现图的遍历功能

实例讲解Python基于回溯法子集树模板实现图的遍历功能

Sep 07, 2017 am 10:14 AM
pythonJejak belakangberdasarkan

这篇文章主要介绍了Python基于回溯法子集树模板实现图的遍历功能,结合实例形式分析了Python使用回溯法子集树模板针对图形遍历问题的相关操作技巧与注意事项,需要的朋友可以参考下

本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能。分享给大家供大家参考,具体如下:

问题

一个图:

A --> B
A --> C
B --> C
B --> D
B --> E
C --> A
C --> D
D --> C
E --> F
F --> 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个节点

效果图:

Atas ialah kandungan terperinci 实例讲解Python基于回溯法子集树模板实现图的遍历功能. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tujuan utama python: fleksibiliti dan kemudahan penggunaanTujuan utama python: fleksibiliti dan kemudahan penggunaanApr 17, 2025 am 12:14 AM

Fleksibiliti Python dicerminkan dalam sokongan multi-paradigma dan sistem jenis dinamik, sementara kemudahan penggunaan berasal dari sintaks mudah dan perpustakaan standard yang kaya. 1. Fleksibiliti: Menyokong pengaturcaraan berorientasikan objek, fungsional dan prosedur, dan sistem jenis dinamik meningkatkan kecekapan pembangunan. 2. Kemudahan Penggunaan: Tatabahasa adalah dekat dengan bahasa semulajadi, perpustakaan standard merangkumi pelbagai fungsi, dan memudahkan proses pembangunan.

Python: Kekuatan pengaturcaraan serba bolehPython: Kekuatan pengaturcaraan serba bolehApr 17, 2025 am 12:09 AM

Python sangat disukai kerana kesederhanaan dan kuasa, sesuai untuk semua keperluan dari pemula hingga pemaju canggih. Kepelbagaiannya dicerminkan dalam: 1) mudah dipelajari dan digunakan, sintaks mudah; 2) perpustakaan dan kerangka yang kaya, seperti numpy, panda, dan sebagainya; 3) sokongan silang platform, yang boleh dijalankan pada pelbagai sistem operasi; 4) Sesuai untuk tugas skrip dan automasi untuk meningkatkan kecekapan kerja.

Belajar python dalam 2 jam sehari: panduan praktikalBelajar python dalam 2 jam sehari: panduan praktikalApr 17, 2025 am 12:05 AM

Ya, pelajari Python dalam masa dua jam sehari. 1. Membangunkan pelan kajian yang munasabah, 2. Pilih sumber pembelajaran yang betul, 3 menyatukan pengetahuan yang dipelajari melalui amalan. Langkah -langkah ini dapat membantu anda menguasai Python dalam masa yang singkat.

Python vs C: Pro and Cons untuk PemajuPython vs C: Pro and Cons untuk PemajuApr 17, 2025 am 12:04 AM

Python sesuai untuk pembangunan pesat dan pemprosesan data, manakala C sesuai untuk prestasi tinggi dan kawalan asas. 1) Python mudah digunakan, dengan sintaks ringkas, dan sesuai untuk sains data dan pembangunan web. 2) C mempunyai prestasi tinggi dan kawalan yang tepat, dan sering digunakan dalam pengaturcaraan permainan dan sistem.

Python: komitmen masa dan kadar pembelajaranPython: komitmen masa dan kadar pembelajaranApr 17, 2025 am 12:03 AM

Masa yang diperlukan untuk belajar python berbeza dari orang ke orang, terutamanya dipengaruhi oleh pengalaman pengaturcaraan sebelumnya, motivasi pembelajaran, sumber pembelajaran dan kaedah, dan irama pembelajaran. Tetapkan matlamat pembelajaran yang realistik dan pelajari terbaik melalui projek praktikal.

Python: Automasi, skrip, dan pengurusan tugasPython: Automasi, skrip, dan pengurusan tugasApr 16, 2025 am 12:14 AM

Python cemerlang dalam automasi, skrip, dan pengurusan tugas. 1) Automasi: Sandaran fail direalisasikan melalui perpustakaan standard seperti OS dan Shutil. 2) Penulisan Skrip: Gunakan Perpustakaan Psutil untuk memantau sumber sistem. 3) Pengurusan Tugas: Gunakan perpustakaan jadual untuk menjadualkan tugas. Kemudahan penggunaan Python dan sokongan perpustakaan yang kaya menjadikannya alat pilihan di kawasan ini.

Python dan Masa: Memanfaatkan masa belajar andaPython dan Masa: Memanfaatkan masa belajar andaApr 14, 2025 am 12:02 AM

Untuk memaksimumkan kecekapan pembelajaran Python dalam masa yang terhad, anda boleh menggunakan modul, masa, dan modul Python. 1. Modul DateTime digunakan untuk merakam dan merancang masa pembelajaran. 2. Modul Masa membantu menetapkan kajian dan masa rehat. 3. Modul Jadual secara automatik mengatur tugas pembelajaran mingguan.

Python: Permainan, GUI, dan banyak lagiPython: Permainan, GUI, dan banyak lagiApr 13, 2025 am 12:14 AM

Python cemerlang dalam permainan dan pembangunan GUI. 1) Pembangunan permainan menggunakan pygame, menyediakan lukisan, audio dan fungsi lain, yang sesuai untuk membuat permainan 2D. 2) Pembangunan GUI boleh memilih tkinter atau pyqt. TKInter adalah mudah dan mudah digunakan, PYQT mempunyai fungsi yang kaya dan sesuai untuk pembangunan profesional.

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Tetapan grafik terbaik
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Arahan sembang dan cara menggunakannya
1 bulan yang laluBy尊渡假赌尊渡假赌尊渡假赌

Alat panas

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

SublimeText3 Linux versi baharu

SublimeText3 Linux versi baharu

SublimeText3 Linux versi terkini

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

VSCode Windows 64-bit Muat Turun

VSCode Windows 64-bit Muat Turun

Editor IDE percuma dan berkuasa yang dilancarkan oleh Microsoft