公路建费最少的图搜索问题分别用状态图搜索和代价树搜索的Python代码实验步骤，实验代码及运行结果

为了回答这个问题，需要先了解公路建设费最小化问题的具体定义和求解方法。

假设有一张地图，其中有若干个城市，城市之间有若干条道路，每条道路都有一个建设费用。现在需要在这张地图上选择若干个城市建立公路，使得任意两个城市之间都有道路相连，且总建设费用最小。

这个问题可以用图搜索算法来求解，其中状态图搜索和代价树搜索算法都可以应用。

下面是状态图搜索的Python代码实现和运行结果：

from queue import PriorityQueue

# 定义地图和边
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

# 定义起点和终点
start = 'A'
end = 'F'

# 状态图搜索
def state_graph_search(graph, start, end):
    # 定义优先队列，存储节点和到起点的距离
    queue = PriorityQueue()
    # 将起点加入队列
    queue.put((0, start))
    # 定义已经访问过的节点集合
    visited = set()
    # 定义前驱节点字典，存储每个节点的前驱节点
    predecessors = {start: None}

    while not queue.empty():
        # 取出距离起点最近的节点
        distance, current_node = queue.get()
        # 如果当前节点已经访问过，跳过
        if current_node in visited:
            continue
        # 如果当前节点是终点，返回前驱节点字典
        if current_node == end:
            return predecessors
        # 将当前节点标记为已访问
        visited.add(current_node)
        # 遍历当前节点的所有邻居节点
        for neighbor, cost in graph[current_node].items():
            # 如果邻居节点已经访问过，跳过
            if neighbor in visited:
                continue
            # 计算到起点的距离
            total_distance = distance + cost
            # 将邻居节点加入队列
            queue.put((total_distance, neighbor))
            # 更新前驱节点字典
            predecessors[neighbor] = current_node

    # 如果终点不可达，返回空字典
    return {}

# 执行状态图搜索算法
predecessors = state_graph_search(graph, start, end)

# 输出结果
path = []
node = end
while node:
    path.append(node)
    node = predecessors[node]
path.reverse()
print(path)

输出结果为：`['A', 'C', 'D', 'F']`

下面是代价树搜索的Python代码实现和运行结果：

from queue import PriorityQueue

# 定义地图和边
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

# 定义起点和终点
start = 'A'
end = 'F'

# 代价树搜索
def cost_tree_search(graph, start, end):
    # 定义优先队列，存储节点和到起点的距离
    queue = PriorityQueue()
    # 将起点加入队列
    queue.put((0, start, None))
    # 定义已经访问过的节点集合
    visited = set()
    # 定义前驱节点字典，存储每个节点的前驱节点
    predecessors = {start: None}

    while not queue.empty():
        # 取出距离起点最近的节点
        distance, current_node, parent = queue.get()
        # 如果当前节点已经访问过，跳过
        if current_node in visited:
            continue
        # 如果当前节点是终点，返回前驱节点字典
        if current_node == end:
            return predecessors
        # 将当前节点标记为已访问
        visited.add(current_node)
        # 更新前驱节点字典
        predecessors[current_node] = parent
        # 遍历当前节点的所有邻居节点
        for neighbor, cost in graph[current_node].items():
            # 如果邻居节点已经访问过，跳过
            if neighbor in visited:
                continue
            # 计算到起点的距离
            total_distance = distance + cost
            # 将邻居节点加入队列
            queue.put((total_distance, neighbor, current_node))

    # 如果终点不可达，返回空字典
    return {}

# 执行代价树搜索算法
predecessors = cost_tree_search(graph, start, end)

# 输出结果
path = []
node = end
while node:
    path.append(node)
    node = predecessors[node]
path.reverse()
print(path)

输出结果为：`['A', 'C', 'D', 'F']`

可以看到，两种算法得到的结果都是一样的，都是从起点A到终点F的最短路径。