这篇文章主要介绍了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!

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 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.

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 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.

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 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.

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 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.


Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

SublimeText3 Linux versi baharu
SublimeText3 Linux versi terkini

Muat turun versi mac editor Atom
Editor sumber terbuka yang paling popular

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

VSCode Windows 64-bit Muat Turun
Editor IDE percuma dan berkuasa yang dilancarkan oleh Microsoft