Wie schreibe ich einen Tiefensuchalgorithmus in Python?

Wie schreibe ich einen Tiefensuchalgorithmus in Python?

Depth-First Search (DFS) ist ein häufig verwendeter Graph-Traversal-Algorithmus. Bei der Tiefensuche werden benachbarte Knoten ausgehend vom Startknoten kontinuierlich erkundet, bis keine Erkundung mehr möglich ist. Anschließend wird auf den vorherigen Knoten zurückgegriffen und unerforschte benachbarte Knoten werden weiter durchquert, bis alle Knoten besucht sind.

Das Folgende ist ein Beispiel für einen in Python geschriebenen Tiefensuchalgorithmus:

# 定义图的类
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)

Der obige Code implementiert eine Graph-Klasse, um die Struktur des Diagramms darzustellen, die die anfängliche Anzahl von Knoten und die Definition benachbarter Knoten enthält. Dann wird die Funktion zum Hinzufügen einer Kante add_edge definiert. add_edge。

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

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

Der DFS-Algorithmus wird mit Hilfe der rekursiven Funktion dfs_util ausgeführt. Die Funktion akzeptiert zwei Parameter: den aktuellen Knoten u und ein Array visited zum Markieren, ob der Knoten besucht wurde. Der Algorithmus markiert zunächst den aktuellen Knoten als besucht und gibt den Wert des Knotens aus. Durchlaufen Sie dann alle benachbarten Knoten des aktuellen Knotens. Wenn die benachbarten Knoten noch nicht besucht wurden, rufen Sie die Funktion dfs_util rekursiv auf.

Schließlich dient die Funktion dfs als externe Schnittstelle, akzeptiert den Startknoten als Parameter und erstellt ein mit False initialisiertes visited-Array. Rufen Sie die Funktion dfs_util auf, um die DFS-Traversierung zu starten.

Im Testcode haben wir ein Diagramm mit 4 Knoten erstellt und einige Kanten hinzugefügt. Verwenden Sie dann Startknoten 2, um eine DFS-Durchquerung durchzuführen und die Ergebnisse auszugeben. 🎜🎜Ich hoffe, dieses Codebeispiel hilft Ihnen zu verstehen, wie man einen Tiefensuchalgorithmus in Python schreibt. Sie können den Code auch nach Ihren eigenen Bedürfnissen modifizieren und optimieren. 🎜

Das obige ist der detaillierte Inhalt vonWie schreibe ich einen Tiefensuchalgorithmus in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!