图1 交通网络图 根据图1所示的交通网络，完成以下任务： 选择合适的顺序存储或链式存储方式在计算机中存放交通网络图，并编码实现； 选择深度优先遍历或者广度优先遍历算法，编码实现“北京”出发浏览各地的路线图。 各个城市之间的距离如图1边上的权值所示，如果现在需要在四个城市之间修路，请找出能够连接所有城市的总距离最短的道路规划图。

针对第一个任务，我们可以选择使用邻接矩阵进行顺序存储。邻接矩阵是一个二维数组，其中每个元素表示两个顶点之间是否有边相连。代码实现如下：

# 定义交通网络图邻接矩阵
graph = [[0, 1, 3, 65535, 65535],
         [1, 0, 2, 5, 65535],
         [3, 2, 0, 1, 8],
         [65535, 5, 1, 0, 4],
         [65535, 65535, 8, 4, 0]]

其中，65535表示两个城市之间没有直接连接。

针对第二个任务，我们可以选择使用深度优先遍历算法。深度优先遍历算法可以通过递归的方式实现。代码实现如下：

# 深度优先遍历算法
def dfs(graph, start, visited):
    # 标记当前节点为已访问
    visited[start] = True
    print(start, end=' ')

    # 遍历邻接矩阵中当前节点的所有邻居节点
    for i in range(len(graph[start])):
        if graph[start][i] != 0 and not visited[i]:
            dfs(graph, i, visited)

# 测试深度优先遍历算法
visited = [False] * len(graph)
dfs(graph, 0, visited)

其中，visited数组用于记录每个节点是否已经被访问过。我们从北京开始遍历，输出所有可以到达的节点。

针对第三个任务，我们可以选择使用Prim算法或Kruskal算法求解最小生成树。这里我们选择使用Prim算法。Prim算法的基本思想是从一个节点开始，不断选择与当前已有节点相连的权值最小的边，并将相连的节点加入已有节点集合中，直到所有节点都被加入。代码实现如下：

# Prim算法实现最小生成树
def prim(graph):
    # 初始化已有节点集合和未加入节点集合
    in_set = [0] * len(graph)
    out_set = [i for i in range(1, len(graph))]
    in_set[0] = 1

    # 初始化最小生成树的边和权重
    edges = []
    weights = []

    # 重复加入新节点直到所有节点都被加入
    while out_set:
        min_weight = float('inf')
        min_edge = (-1, -1)

        # 遍历已有节点集合中的所有节点，查找与未加入节点集合中距离最近的边
        for i in range(len(in_set)):
            if in_set[i] == 1:
                for j in out_set:
                    if graph[i][j] < min_weight:
                        min_weight = graph[i][j]
                        min_edge = (i, j)

        # 将距离最近的节点加入已有节点集合，并从未加入节点集合中删除
        in_set[min_edge[1]] = 1
        out_set.remove(min_edge[1])

        # 将边加入最小生成树的边集合中
        edges.append(min_edge)
        weights.append(min_weight)

    # 输出最小生成树的边和权重
    for i in range(len(edges)):
        print('({}-{}):{}'.format(edges[i][0], edges[i][1], weights[i]))

# 测试Prim算法
prim(graph)

最终输出的结果为：

(0-1):1
(1-2):2
(2-3):1

表示连接所有城市的总距离最短的道路规划图为：北京-天津，天津-石家庄，石家庄-济南。