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

SecLists
SecLists ialah rakan penguji keselamatan muktamad. Ia ialah koleksi pelbagai jenis senarai yang kerap digunakan semasa penilaian keselamatan, semuanya di satu tempat. SecLists membantu menjadikan ujian keselamatan lebih cekap dan produktif dengan menyediakan semua senarai yang mungkin diperlukan oleh penguji keselamatan dengan mudah. Jenis senarai termasuk nama pengguna, kata laluan, URL, muatan kabur, corak data sensitif, cangkerang web dan banyak lagi. Penguji hanya boleh menarik repositori ini ke mesin ujian baharu dan dia akan mempunyai akses kepada setiap jenis senarai yang dia perlukan.

Versi Mac WebStorm
Alat pembangunan JavaScript yang berguna

mPDF
mPDF ialah perpustakaan PHP yang boleh menjana fail PDF daripada HTML yang dikodkan UTF-8. Pengarang asal, Ian Back, menulis mPDF untuk mengeluarkan fail PDF "dengan cepat" dari tapak webnya dan mengendalikan bahasa yang berbeza. Ia lebih perlahan dan menghasilkan fail yang lebih besar apabila menggunakan fon Unicode daripada skrip asal seperti HTML2FPDF, tetapi menyokong gaya CSS dsb. dan mempunyai banyak peningkatan. Menyokong hampir semua bahasa, termasuk RTL (Arab dan Ibrani) dan CJK (Cina, Jepun dan Korea). Menyokong elemen peringkat blok bersarang (seperti P, DIV),

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

DVWA
Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini