贪心算法之单元最短路径用c++设计

贪心算法是一种通过每一步选择当前状态下最优解来逼近全局最优解的策略。对于单位最短路径问题，比如经典的Dijkstra算法，它不是典型的贪心算法，而是图论中的启发式搜索算法。不过，如果你想要了解如何用C++设计基于贪心思想的求解简单路径问题，可以考虑Kruskal's 算法，它用于寻找无向图中最小生成树，虽然不是精确的单源最短路径。

Kruskal's算法的主要步骤是：
1. 将所有边按照权重从小到大排序。
2. 初始化一个空集合作为最小生成树。
3. 遍历排序后的边，如果这条边连接的两个顶点不在同一棵树中，则将其添加到最小生成树，并合并这两个顶点所在的集合。

以下是使用C++实现Kruskal's算法的一个简化版示例：

#include <iostream>
#include <vector>
#include <set>
#include <limits>

// 边结构体
struct Edge {
    int src, dest, weight;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

int kruskalMST(Edge edges[], int n) {
    std::vector<int> parent(n);
    std::iota(parent.begin(), parent.end(), 0); // 建立每个节点的初始集合为其自身

    std::sort(edges, edges + n, compareEdges);

    int result = 0; // 最小生成树总重量
    for (int i = 0; i < n - 1; ++i) {
        int x = edges[i].src, y = edges[i].dest;
        if (findSet(x, parent) != findSet(y, parent)) { // 如果两节点在同一集合外
            unionSet(x, y, parent); // 合并集合
            result += edges[i].weight; // 添加边的权重
        }
    }

    return result;
}

// 查找集合
int findSet(int v, std::vector<int>& parent) {
    return parent[v] == v ? v : parent[v] = findSet(parent[v], parent);
}

// 合并集合
void unionSet(int a, int b, std::vector<int>& parent) {
    parent[findSet(a, parent)] = findSet(b, parent);
}

int main() {
    int numVertices, edgeCount;
    std::cout << "Enter number of vertices: ";
    std::cin >> numVertices;
    std::cout << "Enter number of edges: ";
    std::cin >> edgeCount;

    Edge edges[edgeCount];
    // 输入边的起点、终点和权重
    for (int i = 0; i < edgeCount; ++i) {
        std::cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    int mstWeight = kruskalMST(edges, edgeCount);
    std::cout << "Minimum Spanning Tree weight: " << mstWeight << std::endl;

    return 0;
}