邻接表的深度遍历算法

邻接表是一种表示图形的数据结构，其中每个顶点的所有相邻顶点都存储在该顶点的链表中。深度优先搜索是一种遍历或搜索图形或树数据结构的算法，其中从根节点或任何其他起始节点开始，首先访问尽可能深的节点，然后回溯到更浅的节点。下面是邻接表的深度遍历算法的Python实现：

# 定义一个邻接表类
class AdjNode:
    def __init__(self, data):
        self.vertex = data
        self.next = None

# 定义一个图类
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [None] * self.V

    # 添加边
    def add_edge(self, src, dest):
        node = AdjNode(dest)
        node.next = self.graph[src]
        self.graph[src] = node

    # 深度优先遍历
    def DFS(self, v, visited):
        visited[v] = True
        print(v, end=' ')

        # 递归访问所有相邻节点
        temp = self.graph[v]
        while temp:
            if not visited[temp.vertex]:
                self.DFS(temp.vertex, visited)
            temp = temp.next

    # 对每个未被访问的节点调用DFS
    def DFS_traversal(self):
        visited = [False] * self.V
        for i in range(self.V):
            if not visited[i]:
                self.DFS(i, visited)

在这个实现中，我们首先定义了一个邻接表类和一个图类。然后，我们添加了一个add_edge方法来添加边。最后，我们定义了一个DFS方法来执行深度优先遍历，并定义了一个DFS_traversal方法来对每个未被访问的节点调用DFS。