算法5-1：图的遍历——深度优先搜索【图】Description 深度...

算法5-3：无向图的连通分量和生成树【图】 Description 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索的过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。 对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。 假设以孩子兄弟链表作为生成森林的存储结构，则需写出生成非连通图的深度优先生成森林的算法和建立以p为根的深度优先生成树的算法。 在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立无向图的生成森林。对于森林中的每一棵生成树，遍历所有顶点，并输出遍历顶点的顺序。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。 其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。 Output 每一行输出无向图中的一棵生成树，表示按照题目描述中的深度优先遍历算法遍历相应的连通分量的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。 Sample Input6 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0Sample Output0 3 1 2 4 5

1. 【说明】

实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。

【算法】

第一步：首先访问连通图G的指定起始顶点v；

第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。

第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。

因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。

A、v1,v2,v3,v5,v4

B、v1,v2,v3,v4,v5

C、v1,v3,v4,v5,v2

D、v1,v4,v3,v5,v2

算法5-2：图的遍历——广度优先搜索【图】 Description 广度优先搜索遍历类似于树的按层次遍历的过程。其过程为：假设从图中的某顶点v出发，在访问了v之后依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点。重复上述过程，直至图中所有顶点都被访问到为止。 在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。 Output 只有一行，包含n个整数，表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。 每个整数后输出一个空格，并请注意行尾输出换行。 Sample Input4 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0Sample Output0 3 1 2 HINT 在本题中，需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后，需要严格按照题目描述的遍历顺序对图进行遍历。另外，算法中描述的FirstAdjVex函数和NextAdjVex函数，需要认真的自行探索并完成。在本题中需要使用队列结构，需要对队列的概念进行复习。 通过这道题目，应该能够对图的广度优先搜索建立更加直观和清晰的概念。

对此图进行深度优先遍历正确的有（ ）

A、0,1,2,5,3,4

B、0,1,2,5,4,3

C、0,3,5,2,1,4

D、0,2,1,4,5,3

算法5-4：最小生成树【图】 Description 最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。 可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。 而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。 在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。 Output 只有一个整数，即最小生成树的总代价。请注意行尾输出换行。 Sample Input4 0 2 4 0 2 0 3 5 4 3 0 1 0 5 1 0Sample Output6

算法5-7：信道安全【图】 Description Alpha 机构有自己的一套网络系统进行信息传送。情报员 A 位于节点 1，他准备将一份情报 发送给位于节点 n 的情报部门。可是由于最近国际纷争，战事不断，很多信道都有可能被遭到监 视或破坏。 经过测试分析，Alpha 情报系统获得了网络中每段信道安全可靠性的概率，情报员 A 决定选 择一条安全性最高，即概率最大的信道路径进行发送情报。 你能帮情报员 A 找到这条信道路径吗？ Input 第一行： T 表示以下有 T 组测试数据 （ 1≤T ≤8 ） 对每组测试数据： 第一行：n m 分别表示网络中的节点数和信道数 (1< n="10000，1<=m<=50000) 接下来有 m 行， 每行包含三个整数 i，j，p，表示节点 i 与节点 j 之间有一条信道，其信 道安全可靠性的概率为 p%。 ( p="100)Output 每组测试数据，输出占一行，一个实数 即情报传送到达节点 n 的最高概率，精确到小数点后 6 位。 Sample Input1 5 7 5 2 100 3 5 80 2 3 70 2 1 50 3 4 90 4 1 85 3 1 70Sample Output61.200000&lt;br&gt;&lt;p class=" answer">

1、某内排序方法的稳定性是指( )。

A、该排序算法不允许有相同的关键字记录

B、该排序算法允许有相同的关键字记录

C、平均时间为0（n log n）的排序方法

D、以上都不对

下列选项中，不是下图深度优先遍历序列的是（ ）。

A、V1,V5,V4,V3,V2

B、V1,V3,V2,V5,V4

C、V1,V2,V5,V4,V3

D、V1,V2,V3,V4,V5

E、V1,V3,V5,V4,V2

F、V1,V5,V2,V3,V4