代价树的广度优先搜索算法python 代码

以下是代价树的广度优先搜索算法的 Python 代码实现，其中 `graph` 为代价树的邻接矩阵，`start` 和 `goal` 分别为起始节点和目标节点：

from queue import Queue

def cost_bfs(graph, start, goal):
    n = len(graph)
    visited = [False] * n
    costs = [float('inf')] * n
    parents = [-1] * n
    queue = Queue()

    visited[start] = True
    costs[start] = 0
    queue.put(start)

    while not queue.empty():
        curr = queue.get()

        if curr == goal:
            path = []
            while curr != -1:
                path.append(curr)
                curr = parents[curr]
            return list(reversed(path))

        for neighbor in range(n):
            if graph[curr][neighbor] != 0 and not visited[neighbor]:
                visited[neighbor] = True
                parents[neighbor] = curr
                costs[neighbor] = costs[curr] + graph[curr][neighbor]
                queue.put(neighbor)
            elif graph[curr][neighbor] != 0 and visited[neighbor] and costs[neighbor] > costs[curr] + graph[curr][neighbor]:
                costs[neighbor] = costs[curr] + graph[curr][neighbor]
                parents[neighbor] = curr

    return None

该算法使用了广度优先搜索的基本思路，但在扩展节点时需要计算代价值，并将其保存在 `costs` 数组中。同时，还使用了 `parents` 数组来记录每个节点的前一个节点，以便最终回溯路径。