题目
题目
单项选择题

Prims_Alg_5 This question relates to the use of the Graph Abstract Data Type (ADT) implemented with an Adjacency Map, as covered in class. Below is the pseudocode for Prim’s Algorithm, which is used to compute a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph:   PrimJarnikMST(Graph g):    d = empty map                      // d[v] = min edge weight to connect v    tree = empty list                 // stores MST edges    pq = AdaptableHeapPriorityQueue()    pqlocator = empty map            // maps vertex to its entry in pq     for each vertex v in g.vertices():        if d is empty:            d[v] = 0        else:            d[v] = ∞        pqlocator[v] = pq.add(d[v], (v, None))     while pq is not empty:        (key, (u, edge)) = pq.remove_min()        remove u from pqlocator        if edge ≠ None:            add edge to tree         for each link in g.incident_edges(u):            v = link.opposite(u)            if v in pqlocator:                weight = link.element()                if weight < d[v]:                    d[v] = weight                    pq.update(pqlocator[v], d[v], (v, link))     return tree Which condition guarantees that Prim’s algorithm terminates after building the MST?

选项
A.When all edges are explored
B.When the queue becomes empty
C.When the tree contains n-1 edges
D.When all edge weights are zero
查看解析

查看解析

标准答案
Please login to view
思路分析
Let’s walk through what terminates PrimJarnikMST according to the given pseudocode. Option 1: 'When all edges are explored' — This is not the stated termination condition. The algorithm iterates by examining the incident edges of the currently chosen vertex, updating priorities, and removing vertices from the priority queue. It does not require that every edge in the graph be processed for terminati......Login to view full explanation

登录即可查看完整答案

我们收录了全球超50000道考试原题与详细解析,现在登录,立即获得答案。

类似问题

Prims_2 This question relates to the use of the Graph Abstract Data Type (ADT) implemented with an Adjacency Map, as covered in class. We are using Prim’s algorithm to form a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph. Below is the pseudocode for Prim’s algorithm: PrimJarnikMST(Graph g):    d = empty map                        // d[v] = min edge weight to connect v    tree = empty list                   // stores MST edges    pq = AdaptableHeapPriorityQueue()    pqlocator = empty map               // maps vertex to its entry in pq     for each vertex v in g.vertices():        if d is empty:            d[v] = 0                    // start vertex        else:            d[v] = ∞        pqlocator[v] = pq.add(d[v], (v, None))     while pq is not empty:        (key, (u, edge)) = pq.remove_min()        remove u from pqlocator        if edge ≠ None:            add edge to tree         for each link in g.incident_edges(u):            v = link.opposite(u)            if v in pqlocator:                weight = link.element()                if weight < d[v]:                    d[v] = weight                    pq.update(pqlocator[v], d[v], (v, link))     return tree We have just completed visiting vertex 4, as part of executing Prim’s algorithm. Using the current state of the distance and parent tables (shown below), and based on the priority queue selection logic in the pseudocode above: Which vertex will be visited next by the algorithm?

Kruskal_Algo_3 This question relates to the use of the Graph Abstract Data Type (ADT) implemented with an Adjacency Map, as covered in class. You are working with an undirected, connected, weighted graph G, where all edges have non-negative weights. The goal is to compute a Minimum Spanning Tree (MST) of G. The following pseudocode implements Kruskal’s Algorithm using a priority queue to select edges in increasing order of weight and a disjoint set forest to track connected components: KRUSKAL-MST(Graph G):    Initialize an empty list MST to store edges of the minimum spanning tree    Initialize a priority queue PQ with all edges of G, prioritized by weight    Initialize a forest where each vertex is its own component     while MST has fewer than (number of vertices - 1) edges and PQ is not empty:        Remove the edge with the smallest weight from PQ        Let (u, v) be the endpoints of the edge         if u and v are in different components:            Add edge (u, v) to MST            Merge the components of u and v     return MST Why does the algorithm stop when the MST contains exactly (number of vertices - 1) edges?

Prims_Alg_3 This question relates to the use of the Graph Abstract Data Type (ADT) implemented with an Adjacency Map, as covered in class. Below is the pseudocode for Prim’s Algorithm, which is used to compute a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph: PrimJarnikMST(Graph g):    d = empty map                      // d[v] = min edge weight to connect v    tree = empty list                 // stores MST edges    pq = AdaptableHeapPriorityQueue()    pqlocator = empty map            // maps vertex to its entry in pq     for each vertex v in g.vertices():        if d is empty:            d[v] = 0        else:            d[v] = ∞        pqlocator[v] = pq.add(d[v], (v, None))     while pq is not empty:        (key, (u, edge)) = pq.remove_min()        remove u from pqlocator        if edge ≠ None:            add edge to tree         for each link in g.incident_edges(u):            v = link.opposite(u)            if v in pqlocator:                weight = link.element()                if weight < d[v]:                    d[v] = weight                    pq.update(pqlocator[v], d[v], (v, link))     return tree Why does the algorithm update d[v] when it finds a lighter edge (u, v) during the inner loop?

Both Prim's and Kruskal's algorithms help us form MSTs.

更多留学生实用工具

加入我们，立即解锁 海量真题 与 独家解析，让复习快人一步！