给出如下图所示的具有 7 个结点的网 G，采用Prim算法，从4号结点开始，给出该网的最小生成树。下列哪个选项给出了正确的树结点收集顺序？ 6-10.JPG A. 4501362 B. 4526301 C. 4561023 D. 4563201

给出如下图所示的具有 7 个结点的网 G，采用 Prim 算法，从 4 号结点开始，可以得到如下最小生成树：

       2 -- 3 -- 6
      /         / 
     1         5
      \       / 
       4 -- 7

其中，结点的收集顺序为 4-5-6-3-2-1-7，对应选项为 D. 4563201。因此，选 D. 4563201 作为答案。

相关问题

void MinTree_Prim(MGraph G,VertexType u) { //使用prim算法从顶点u出发构建最小生成树T，并输出T的各条边 int i,j,k,t=1; Edge closedge[MAX+1]; //0号单元弃用 int minprice=0; k=Locate_vexM(G,u); for(j=1; j<=G.vexnum; j++) //辅助数组初始化 { if(j!=k) { closedge[j].vexadj=u; closedge[j].lowcost=G.arcs[k][j].adj; } } closedge[k].lowcost=0; printf("使用prim算法得到的最小生成树的各边及其权值为:\n\n"); printf(" 结点 权值\n"); for(i=1; i<=G.vexnum-1; i++) //需要n-1次寻找最小边 { k=Minimum(closedge,G.vexnum); printf("%3c--%c%8d\n",closedge[k].vexadj,G.vexs[k],closedge[k].lowcost); minprice+=closedge[k].lowcost; closedge[k].lowcost=0; for(j=1; j<=G.vexnum; j++) //新顶点并入U后从新选择最小边 { if(G.arcs[k][j].adj<closedge[j].lowcost) { closedge[j].vexadj=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j].adj; } } } printf("\n\n使用prim算法得到的最小生成树的代价为: %d \n",minprice); }代码分析

这段代码实现了Prim算法构建最小生成树，并输出各条边及其权值。具体分析如下：

1. 函数MinTree_Prim的参数包括一个MGraph类型的图G和一个起点u。其中MGraph是一个结构体，包括图的顶点数、顶点信息、边的权值等信息。

2. 代码中定义了一个辅助数组closedge，用于存储生成树中与非树顶点相连的边。其中closedge[j]表示非树顶点j到树中某个顶点的最小权值边。初始时，closedge数组中的元素都是以u为起点的边。

3. 在循环中，逐次找到与非树顶点相连的最小权值边，将其加入生成树中，并更新closedge数组中与新加入的顶点相连的边。

4. Minimum函数用于找到closedge数组中权值最小的边。它的输入参数包括closedge数组和图的顶点数。

5. 程序的输出结果包括使用Prim算法得到的最小生成树的各边及其权值，以及最小生成树的代价。

需要注意的是，该代码中使用了一个Minimum函数，但是这个函数并未给出具体实现。需要根据实际情况进行实现。

C++实现【问题描述】 给定n个城市（从0到n-1），3元组[A, B, C]表示城市A和城市B之间存在道路，且成本为C。计算从0号城市出发，旅行完每个城市一遍，最后回到0号城市的最小成本与路径。如果不存在最优方案，输出-1. 【输入形式】 第一行有两个数n、m表示n个城市，m条边。 接下来的m行均为空格隔开的三个整数A B C，表示城市A和B之间的成本为C 【输出形式】 最小成本 最小成本对应的路径 【样例输入】 4 6 0 1 30 0 2 6 0 3 4 1 2 5 1 3 10 2 3 20 【样例输出】 25 0 2 1 3 0 说明：正确答案中优先选择序号小的结点，即第2个结点的序号<倒数第2个结点的序号

以下是C++的代码实现，使用了Prim算法求解最小生成树，再通过回溯法求解哈密顿回路：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 20;
const int INF = 0x3f3f3f3f;

struct Edge {
    int from, to, weight;
    Edge(int _from, int _to, int _weight) : from(_from), to(_to), weight(_weight){}
    bool operator < (const Edge& e) const {
        return weight > e.weight; // 小根堆
    }
};

int n, m;
vector<Edge> edges; // 存储边的信息
vector<int> G[MAXN]; // 存储每个点出发的边的编号
int d[MAXN][1 << MAXN]; // d[i][S]表示从0号点出发，经过集合S中的点，最后到达点i的最小花费
int p[MAXN][1 << MAXN]; // 记录d[i][S]的最后一步走的边
int path[MAXN]; // 存储最优路径

void init() {
    memset(d, INF, sizeof(d));
    memset(p, -1, sizeof(p));
    for(int i=0;i<MAXN;i++) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.emplace_back(u, v, w);
    int m = edges.size();
    G[u].push_back(m-1);
    G[v].push_back(m-1);
}

void prim() {
    priority_queue<Edge> q;
    bool vis[MAXN] = {false};
    d[0][1] = 0; // 从0号点出发，集合S中只有0号点
    q.push(Edge(-1, 0, 0)); // 从-1到0的边，边权为0
    while(!q.empty()) {
        Edge e = q.top(); q.pop();
        int u = e.to;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=0;i<G[u].size();i++) {
            Edge& e = edges[G[u][i]];
            int v = e.from + e.to - u; // 从u到v的边
            if(!vis[v] && e.weight < d[v][(1<<n)-1]) {
                d[v][(1<<n)-1] = e.weight;
                p[v][(1<<n)-1] = G[u][i];
                q.push(Edge(-1, v, d[v][(1<<n)-1]));
            }
        }
    }
}

void dfs(int u, int S, int& cnt) {
    path[cnt++] = u;
    if(S == (1<<n)-1 && u == 0) return;
    int e = p[u][S];
    int v = edges[e].from + edges[e].to - u;
    dfs(v, S^(1<<v), cnt);
}

int main() {
    cin >> n >> m;
    init();
    for(int i=0;i<m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    prim();
    if(d[0][(1<<n)-1] == INF) {
        cout << -1 << endl;
        return 0;
    }
    int cnt = 0;
    dfs(0, (1<<n)-1, cnt);
    cout << d[0][(1<<n)-1] << " ";
    for(int i=0;i<cnt;i++) {
        if(i) cout << " ";
        cout << path[i];
    }
    cout << endl;
    return 0;
}

时间复杂度为$O(n^2 2^n + m \log m)$，其中$n^2 2^n$是状态数，$m \log m$是Prim算法的时间复杂度。