北大PKU 慕课 EDX 数据结构与算法 第八章图 quiz答案与解析[推荐]_edx慕课

北大PKU 慕课 EDX 数据结构与算法 第八章图 quiz答案与解析[推荐]由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“edx慕课”。

第八章 图

PROBLEM 1

(1/1 分)下图中的强连通分量的个数为多少个？

How many strongly connected graphs in the under graph?

3正确

对于无向图，所有结点的度数加起来一定是偶数。As for undirected graphs, the sum of degrees of all vertices is definitely even number.将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Reversion all the edges of a strongly connected component of a directed graph, then the subgraph is still a strongly connected component.对于有向图，每个结点的出度必须要等于入度。As for

对于一个连通directed graph, each vertices’ out-degree is equal to its in-degree.图，一定存在一种给边添加方向的方案使得这个图变成强连通图。For a connected graph, there must be a way of directing all the edges of the original graph to make the graph strongly connected graph.Explanation 结点度数是边数的2倍，故一定为偶数。

The sum of degrees of vertices is equal to the amount of edge times 2, so it must be even number.原来强连通分量中的点必须能够互达，边全部反向后，仍然能够互达。而原来强连通分量外的点和强连通分量内的点之间的边没有变化，以前不能互达现在还是不能，这样保证了仍然是极大的强连通子图。

In the original strongly connected component, every pair of vertices in the subgraph is connected by a path.After reversion, this property doesn't change.And the connectivity of the vertices outside of the subgraph and vertices in the subgraph don't change too.So we can guarantee it still be the maximal strongly connected subgraph.所有结点的出度之和等于入度之和，但是每个结点并没有出度和入度相等的性质。The sum of in-degrees of all nodes is equal to the sum of out-degrees of all nodes.But for each node, it doesn't work.给两个结点新增一条边相连，能够形成一个连通图，但是不管怎么给边定向都不能使其成为强连通图。

Add an edge of two vertex, then we can get a connected graph.But we can't make it strongly connected graph however we direct the edges.PROBLEM 3

(1/1 分)当各边上的权值满足什么要求时，宽度优先搜索算法可用来解决单源最短路径问题？(单选)What requirement do the weight of edges should satisfied to make width-first search algorithm can solve single source shortest path problem?（There is only one correct answer）

不一定相等 No limitation.other.均互不相等 Each edge is not equal to each 均相等 Equal 均相等 Equal正确

当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。When the graph doesn't contain circuit of negative weight, but contains the edge of negative weight.Dijkstra algorithm can't guarantee the correctne of the algorithm.当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。When the graph doesn't contain edge of negative weight, Dijkstra algorithm can calculate the shortest path of each pair of vertices.当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。When the graph contains the circuit of negative weight, Dijkstra algorithm can certainly calculate the shortest path form the single source to all the vertices.Dijkstra算法不能用于每对顶点间最短路计算。Dijkstra algorithm can't be applied to calculate the shortest path of each pair of vertices.Explanation 当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。即使是只有负权边，也会导致以前已经被选出来更新其它结点最短路值的结点的最短路值被更新，造成错误。

当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。可以执行多次Dijkstra算法实现这一要求。

当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。Dijkstra算法无法处理图中存在任何负权边的情况。

Dijkstra算法不能用于每对顶点间最短路计算。可以执行多次Dijkstra算法实现这一要求。When the graph doesn't contain circuit of negative weight, but contains the edge of negative weight.Dijkstra algorithm can't guarantee the correctne of the algorithm.Even if there is only the edge of negative weight, it would result in that the shortest path of the node which be selected previously to update the shortest path of the other vertices changes, then cause errors.When the graph doesn't contain edge of negative weight, Dijkstra algorithm can calculate the shortest path of each pair of vertices.We can perform Dijkstra algorithm repeatedly to satisfy this requirement.When the graph contains the circuit of negative weight, Dijkstra algorithm can certainly calculate the shortest path form the single source to all the vertices.Dijkstra algorithm can't handle the situation that graph contains any edge of negative weight.Dijkstra algorithm can't be applied to calculate the shortest path of each pair of vertices.We can perform Dijkstra algorithm repeatedly to satisfy this requirement.PROBLEM 5

(1/1 分)请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b(a

Please use Kruskal algorithm to the following graph and find the minimum spanning tree, and write the number of the valid vertex with minimum merging cost in turn(if there are many vertices satisfy requirement, choose the vertex with minimum number).The number of the edge connecting vertex a and vertex b is ab.Like the edge with weight 1 in the graph, its number is 02(different numbers separated by a blank space).02 35 14 25

02 35 14 25 12正确

02 25 35 12 14 Explanation 最小生成树中已经选择的顶点的集合U初始为｛0｝，从0起，先挑选其他节点到0权值最小为1的边02，把顶点2加入U，U变为｛0，2｝，再选择到U权值最小为4的边25，U变为｛0，2，5｝，再选择到U权值最小为2的边35，U变为｛0，2，5，3｝，再选择到U权值最小为5的边12，U变为｛0，2，5，3，1｝，再选择到U权值最小为3的边14，U变为｛0，2，5，3，1，4｝，结束，答案为02 25 35 12 14 The original set of the selected vertices of the minimum spanning tree is {0}.We firstly select the edge with the minimum weight of edges which connect vertex 0 and other vertices.So we select edge 02 with weight 1 and add vertex 2 into U, then U becomes {0, 2}.Next, in the set of edges which connect U and others, we select the edge 25 with the minimum weight 4, then U becomes {0, 2, 5}.Next, in the set of edges which connect U and others, we select the edge 35 with the minimum weight 2, then U becomes {0, 2, 5, 3}.Similarly, then we select the edge 12 with the minimum weight 12, U becomes {0, 2, 5, 3, 1}.Then we select the edge 14 with the minimum weight 3, then U becomes {0, 2, 5, 3, 1, 4}, over.The answer is 02 25 35 12 14

PROBLEM 7

(本题共有1分)题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列 注意：

1.优先访问编号小的结点

2.顶点序列内无空格，先写深度优先搜索遍历序列，再写广度优先搜索遍历序列。3.深度优先搜索遍历序列和广度优先搜索遍历序列之间用空格隔开 The following graph is an undirected graph, please write the vertices sequences obtained by the depth-first search traversal algorithm and width-first search traversal algorithm respectively.Notice: 1.The vertex with smaller number should have higher priority to be visited.2.There is no blank space among the vertices sequences, write the sequence produced by the depth-first search traversal algorithm at first, then write the another one.3.There two sequences should be separated by a blank space.123456 123564 Explanation 根据深度优先定义，先访问1，依次是2、3、4、5、6，注意是无向图。广度优先是一层一层访问，即123564，答案为123456 123564 According to the definition of the depth-first, we firstly visit vertex 1, then 2, 3, 4, 5, 6 in turn, you should noticed that it’s undirected graph.Width-first traversal algorithm visit the vertices layer by layer，the sequence is 123564.So the answer is 123456 123564.