Bagaimana untuk menulis algoritma carian mendalam-pertama dalam Python?

Bagaimana untuk menulis algoritma carian mendalam-pertama dalam Python?

Depth-First Search (DFS) ialah algoritma traversal graf yang biasa digunakan. Dalam carian mendalam-pertama, bermula dari nod permulaan, nod bersebelahan diterokai secara berterusan sehingga tiada lagi penerokaan boleh dilakukan, dan kemudian ia kembali ke nod sebelumnya dan terus melintasi nod bersebelahan yang belum diterokai sehingga semua nod dilawati.

Berikut ialah contoh algoritma carian pertama mendalam yang ditulis dalam Python:

# 定义图的类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 节点数量
        self.adj = [[] for _ in range(self.V)]  # 存储节点的邻接节点
        
    # 添加边
    def add_edge(self, u, v):
        self.adj[u].append(v)
        
    # DFS递归函数
    def dfs_util(self, u, visited):
        visited[u] = True  # 标记当前节点为已访问
        
        print(u, end=' ')  # 输出当前节点
        
        # 遍历当前节点的所有邻接节点
        for i in self.adj[u]:
            if not visited[i]:
                self.dfs_util(i, visited)
            
    # 对外接口，执行DFS
    def dfs(self, u):
        visited = [False] * self.V  # 标记所有节点均未访问
        
        self.dfs_util(u, visited)
        

# 测试代码
if __name__ == '__main__':
    # 创建一个具有4个节点的图
    g = Graph(4)
    
    # 添加图的边
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)
    g.add_edge(3, 3)
    
    print("深度优先遍历结果：")
    g.dfs(2)

Kod di atas melaksanakan kelas Graf untuk mewakili struktur graf, yang merangkumi bilangan awal nod dan takrifan nod bersebelahan. Kemudian fungsi untuk menambah tepi add_edge ditakrifkan. add_edge。

DFS算法在dfs_util递归函数的辅助下进行，函数接受两个参数：当前节点u和一个数组visited，用于标记节点是否已经访问。算法首先将当前节点标记为已访问，并输出该节点的值。然后遍历当前节点的所有邻接节点，如果邻接节点尚未被访问，则递归调用dfs_util函数。

最后，dfs函数作为对外接口，接受起始节点作为参数，并创建一个visited数组初始化为False。调用dfs_util

Algoritma DFS dilakukan dengan bantuan fungsi rekursif dfs_util Fungsi ini menerima dua parameter: nod semasa u dan tatasusunan dilawati. untuk Tandakan sama ada nod telah dilawati. Algoritma mula-mula menandakan nod semasa sebagai dilawati dan mengeluarkan nilai nod. Kemudian lintasi semua nod bersebelahan nod semasa Jika nod bersebelahan belum dilawati lagi, panggil fungsi dfs_util secara rekursif.

Akhir sekali, fungsi dfs berfungsi sebagai antara muka luaran, menerima nod permulaan sebagai parameter dan mencipta tatasusunan dilawati yang dimulakan kepada False. Panggil fungsi dfs_util untuk memulakan traversal DFS.

Dalam kod ujian, kami mencipta graf dengan 4 nod dan menambah beberapa tepi. Kemudian gunakan nod permulaan 2 untuk melakukan traversal DFS dan mengeluarkan hasilnya. 🎜🎜Semoga contoh kod ini membantu anda memahami cara menulis algoritma carian pertama mendalam dalam Python. Anda juga boleh mengubah suai dan mengoptimumkan kod mengikut keperluan anda sendiri. 🎜

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma carian mendalam-pertama dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!