图的深度优先遍历算法的时空分析

图的深度优先遍历算法（DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度遍历树的节点，直到找到目标节点或遍历完整棵树。DFS算法的时间复杂度为O(V+E)，其中V表示节点数，E表示边数。空间复杂度取决于递归深度，最坏情况下为O(V)。

以下是一个使用DFS算法遍历图的Python代码示例：

# 定义一个图类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 节点数
        self.adj = [[] for i in range(vertices)]  # 邻接表

    # 添加边
    def add_edge(self, u, v):
        self.adj[u].append(v)

    # DFS遍历
    def DFS(self, v, visited):
        visited[v] = True
        print(v, end=' ')
        for i in self.adj[v]:
            if not visited[i]:
                self.DFS(i, visited)

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

# 创建一个图并添加边
g = Graph(5)
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)

# 对图进行DFS遍历
print("DFS遍历结果：")
g.DFS_traversal()