1.（必做题） 设计并验证如下算法：带权图采用邻接表表示，实现有向图的广度优先搜索与无向图的深度优先搜索。

### 回答1：
这道题要设计并验证以下算法：带权图表表示，实现有向图的广度优先搜索和无向图的深度优先搜索，以实现有向图的宽度优先搜索和无向图的深度优先搜索，并且要考虑有向图和无向图的广度优先搜索和深度优先搜索的优先级问题。

### 回答2：
在图的搜索算法中，广度优先搜索（BFS）和深度优先搜索（DFS）是两种常用的算法。本题要求设计并验证一个能够实现有向图的BFS和无向图的DFS的算法。为了达成这个目的，我们需要分别说明有向图和无向图的BFS和DFS的实现方法。

首先来看BFS。对于一个有向图，我们可以使用邻接表来表示。实现BFS需要使用一个队列来保存待访问的顶点。我们先将起始点入队，并标记它为已访问。然后依次取出队首点的所有邻接点，并将未访问的邻接点入队。重复这个过程，直到队列为空。这样可以保证我们逐层遍历整个图，找到所有与起始点连通的点。需要注意的是，当我们进行BFS时，需要记录每个顶点到起始点的距离，同时可能需要记录一些其他信息，如前驱节点等。

接下来看DFS的实现。对于无向图，我们依然使用邻接表来表示。DFS的实现可以使用递归或栈来实现。我们先选择一个起始点，将其标记为已访问，并访问它的邻接点。然后对于每个未访问的邻接点，进行递归访问。这个过程会不断递归，直到当前终止节点的所有邻接点均被访问过。需要注意的是，递归过程中需要记录每个顶点的访问顺序、状态等信息。

为了验证这个算法，我们需要编写程序，并且进行测试。我们可以使用一些经典的图例进行测试，如克鲁斯卡尔算法中使用的7个点的有向图等。对于测试用例，我们需要确定起始点，并在进行搜索前输出图的邻接表信息和搜索算法要求的其他信息。然后进行搜索，根据搜索的结果来判断算法的正确性。我们需要验证广度优先搜索能够找到所有与起始点连通的点，而深度优先搜索能够遍历整个图。同时，我们还需要对于一些特殊情况进行测试，如图为空、只有一个顶点、有向图中存在环、无向图中存在重边等。

综上，本题要求我们设计并验证一个能够实现有向图的BFS和无向图的DFS的算法。我们可以使用邻接表来表示图，使用队列和递归/栈来实现BFS和DFS。测试时需要选择好测试用例，并对于特殊情况进行特别关注。通过这个过程，我们可以更好地掌握图的搜索算法，并深入理解基础算法的设计和实现过程。

### 回答3：
一、算法设计思路：

对于带权图，我们可以在邻接表中记录边的权值信息。在广度优先搜索时，需要使用队列来进行遍历。在遍历过程中，访问顶点时需要将其标记为已访问，并将其相邻的未访问的顶点加入队列中。在每次从队列中取出一个顶点时，需要输出该顶点的信息。

在深度优先搜索时，可以使用递归来遍历无向图。每次访问时，需要将当前顶点标记为已访问，并遍历与其相邻的未访问的顶点，直到遍历完整个图为止。

二、算法验证：

我们可以通过编写代码并对实际图进行遍历来验证算法的正确性。在这里，我们以以下有向图和无向图为例进行验证。

（1）有向图：

该图的邻接表表示为：

0：1(2) 2(3)
1：3(4)
2：3(1) 4(5)
3：4(2)
4：5(6)
5：

使用广度优先搜索的结果为：0 1 2 3 4 5

使用深度优先搜索的结果为：0 1 3 4 5 2

（2）无向图：

该图的邻接表表示为：

0：1 2
1：0 3 4
2：0 4
3：1
4：1 2

使用广度优先搜索的结果为：0 1 2 3 4

使用深度优先搜索的结果为：0 1 3 4 2

通过对以上图的遍历结果可以验证广度优先搜索与深度优先搜索算法的正确性。