加权BFS算法C++实现

加权的BFS算法，可以求取从一点到另外一点的最小或者最大权重值之和。

带加权的图

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>

template<typename T>
struct vertex_type
{
    T parent{};
    T self{};
    size_t weight{};

    vertex_type(const T& p, const T& s, const size_t& w) : parent(p), self(s), weight(w) {}
    vertex_type(const vertex_type<T>& v) : parent(v.parent), self(v.self), weight(v.weight) {}
    void operator=(const vertex_type<T>& v)
    {
        this->parent = v.parent;
        this->self = v.self;
        this->weight = v.weight;
    }

    bool operator<(const vertex_type& other) const
    {
        return other.weight < this->weight;
    }
};

template<typename T>
using weight_graph_type = std::map<T, std::vector<std::pair<T, size_t>>>;
using c_weight_graph = weight_graph_type<char>;

void wbfs_viewer(const c_weight_graph& gp, char st)
{
    std::set<char> used_vertex;
    std::priority_queue<vertex_type<char>> vertex_queue;
    std::vector<vertex_type<char>> vertex_tree;

    vertex_queue.emplace(' ', st, 0);

    while (!vertex_queue.empty())
    {
        auto item = vertex_queue.top();
        vertex_queue.pop();

        auto current_weight = item.weight;

        if (used_vertex.find(item.self) == used_vertex.end())
        {
            std::cout << item.self << " ";
            auto child_vertex = gp.at(item.self);

            std::for_each(child_vertex.begin(), child_vertex.end(),
                [&](auto& c) {
                    vertex_queue.emplace(item.self, c.first, c.second + current_weight);
                });

            vertex_tree.emplace_back(item);
        }
        used_vertex.insert(item.self);
    }
    std::cout << '\n';

    for (auto& item : vertex_tree)
    {
        std::cout << item.parent << " : " << "(" << item.self << "," << item.weight << ")" << std::endl;
    }

}

/*
***************************
*       B---1---D         *   
*      /|      /|\        *      
*    2/ |     / | \7      *          
*    /  |    /  |  \      *     
*   A  2|  4/   |4  F     *     
*    \  |  /    |         *            
*    1\ | /     |         *         
*      \|/      |         *           
*       C---3---E         *          
***************************
*/

int main()
{
    c_weight_graph gp{
        {'A', {{'B', 2},{'C',1}}},
        {'B', {{'A',2}, {'C',2},{'D',1}}},
        {'C', {{'A',1},{'B',2},{'D',4},{'E',3}}},
        {'D', {{'B',1},{'C',4},{'E',4},{'F',7}}},
        {'E', {{'C',3},{'D',4}}},
        {'F', {{'D',7}}}
    };

    char c;
    while (std::cin >> c) {
        wbfs_viewer(gp, c);
    }
}

运行结果：

从A起点到个点的权重值之和从小到大罗列