图的两种遍历方法及对应的生成树。 自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。

在图论中，有两种常用的遍历方法：深度优先搜索（Depth First Search, DFS）和广度优先搜索（Breadth First Search, BFS）。这两种方法不仅可以用于查找路径，还可以用来发现连通分量并生成相应的生成树。

**深度优先遍历 (DFS)生成树**：
- 概念：从一个起点开始，尽可能深地探索分支，直到到达叶子节点，然后回溯到上一层继续探索其他未访问的节点。
- 实现时，通常我们会选择第一个遇到的可达节点作为边，这样形成的子树就是一棵从起点出发的树，这棵树被称为DFS生成树。

**广度优先遍历 (BFS)生成树**：
- 概念：首先访问所有相邻节点，再逐层访问它们的邻居，形成类似层次结构的搜索过程。
- 在BFS生成树中，根节点的所有邻接点会先加入树中，接着是第二层的节点，如此逐级添加，所以得到的是最短路径树，也称为Prim生成树。

下面是一个简单的Python示例，假设我们有一个无向图表示为邻接列表：

def dfs_tree(graph, start):
    visited = [False] * len(graph)
    stack = [start]
    tree = [(start, None)]  # 初始化生成树

    while stack:
        vertex = stack.pop()
        if not visited[vertex]:
            visited[vertex] = True
            for neighbor in graph[vertex]:
                if not visited[neighbor]:
                    tree.append((vertex, neighbor))
                    stack.append(neighbor)

    return tree

# 使用广度优先搜索生成Prim生成树
def bfs_tree(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [start]

    while queue:
        current_vertex = queue.pop(0)
        for neighbor, weight in graph[current_vertex].items():
            new_distance = distances[current_vertex] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                if neighbor not in queue:
                    queue.append(neighbor)

    tree = []
    for node, distance in distances.items():
        if distance == 0:
            parent = None
            while node != start:
                parent = node
                node = distances.get(node, None)
                if node is not None:
                    tree.append((parent, node))
    
    return tree

这里假设`graph`是一个二维列表，表示无向图的邻接表，其中`graph[i][j]`表示节点i和节点j之间是否有边。你可以根据实际数据结构调整代码。