图的邻接矩阵转换为树

将图的邻接矩阵转换为树，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法。以下是使用DFS的方法：

1. 选取一个起点，将其标记为已访问。
2. 遍历该点的所有邻居节点，若邻居节点未被访问，则将其加入到树中，并将其标记为已访问。
3. 对于每个邻居节点，重复步骤2，直到所有节点都被访问过。

在遍历过程中，我们可以使用一个父节点数组来记录每个节点的父节点，以便最后构建出树形结构。

以下是具体实现：

def adjacency_matrix_to_tree(adj_matrix):
    n = len(adj_matrix)
    visited = [False] * n
    parent = [-1] * n # 初始化父节点数组
    tree = [[] for _ in range(n)] # 初始化树
    
    def dfs(node):
        visited[node] = True
        for neighbor, weight in enumerate(adj_matrix[node]):
            if weight != 0 and not visited[neighbor]:
                parent[neighbor] = node
                tree[node].append(neighbor)
                dfs(neighbor)
    
    dfs(0) # 从起点0开始遍历
    
    return tree, parent

调用函数`adjacency_matrix_to_tree(adj_matrix)`即可将邻接矩阵`adj_matrix`转换为树形结构。其中返回值`tree`为树的邻接表，`parent`为每个节点的父节点数组。