第四章测试1.
以下说法，错误的是（ ）。
A:加权无向图是一个包含顶点和加权有向边的图结构 B:有向图是一个包含顶点和有向边的图结构 C:无向图是一个包含顶点和无向边的图结构 D:其他选项均不正确
答案:A
2.
关于有向图的最短路径计算，正确的是（ ）。
A:Bellman-Ford算法不能处理带有负权重回路的加权有向图 B:Dijkstra算法不能处理带有负权重的加权有向图 C:拓扑排序算法不能处理存在回路的加权有向图
答案:ABC
A:对 B:错
答案:A
给定无向图的数据结构，进行插入和查找的操作，请根据要求填空。
public class Graph {
private final int V;
private int E;
private Bag<Integer>[] adj;
}
public class BreadthFirstPaths {
private static final int INFINITY = Integer.MAX_VALUE;
private boolean[] marked; // marked[v] = is there an s-v path
private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path
private int[] distTo; // distTo[v] = number of edges shortest s-v path
public BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
distTo = new int[G.V()];
edgeTo = new int[G.V()];
bfs(G, s);
}
// breadth-first search from a single source
private void bfs(Graph G, int s) {
Queue<Integer> q = new Queue<Integer>();
for (int v = 0; v < G.V(); v++)
distTo[v] = INFINITY;
distTo[s] = 0;
marked[s] = ( ？ );
q.enqueue(s);
while (!q.isEmpty()) {
int v = q.dequeue();
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.enqueue(w);
}
}
}
}
}
A:true B:null C:false D:v
答案:A
给定如下的加权图的数据结构，完成最小生成树的延时prim方法的计算（prim方法）操作。
public class Edge implements Comparable<Edge> {
private final int v;
private final int w;
private final double weight;
}
public class EdgeWeightedGraph {
private final int V;
private int E;
private Bag<Edge>[] adj;
}
public class LazyPrimMST {
private static final double FLOATING_POINT_EPSILON = 1E-12;
private double weight; // total weight of MST
private Queue<Edge> mst; // edges in the MST
private boolean[] marked; // marked[v] = true iff v on tree
private MinPQ<Edge> pq; // edges with one endpoint in tree
public LazyPrimMST(EdgeWeightedGraph G) {
mst = new Queue<Edge>();
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) // run Prim from all vertices to
if (!marked[v]) prim(G, v); // get a minimum spanning forest
}
// run Prim's algorithm
private void prim(EdgeWeightedGraph G, int s) {
marked[s] = true;
for (Edge e : G.adj(s))
if (!marked[e.other(s)]) ( ？ );
while (!pq.isEmpty()) { // better to stop when mst has V-1 edges
Edge e = pq.delMin(); // smallest edge on pq
int v = e.either(), w = e.other(v); // two endpoints
if (marked[v] && marked[w]) continue; // lazy, both v and w already scanned
mst.enqueue(e); // add e to MST
weight += e.weight();
if (!marked[v]) scan(G, v); // v becomes part of tree
if (!marked[w]) scan(G, w); // w becomes part of tree
}
}
}
A:pq.insert(e) B:Pq.del(e) C:pq.delMin() D:pq.insert(s)
答案:A
