C++加权图add_vertex函数实现求助及代码咨询

Hey there! Let's walk through this together—since you're new to C++ and tackling a weighted graph, using a std::map (or std::unordered_map) for the adjacency list is a great call. It’s intuitive, plays nicely with the operations you need (MST, DFS/BFS, iterators), and makes adding vertices straightforward.

First: Set Up the Core Storage #

First, you need a private member variable in your weighted_graph class to hold the adjacency list. This will map each vertex to a list of its neighbors (paired with edge weights). Add this to the private section:

std::map<vertex, std::vector<std::pair<vertex, int>>> adjacency_list;

• std::map keeps vertices ordered (useful for consistent traversals), but if you don’t need ordering, std::unordered_map is faster for lookups—just note your vertex type will need a hash function for that.

Implementing add_vertex #

Your add_vertex function just needs to insert the vertex into the adjacency list with an empty neighbor list. We’ll skip duplicates to avoid overwriting existing data:

void add_vertex(const vertex& v) {
    // Only add the vertex if it doesn't already exist
    if (adjacency_list.find(v) == adjacency_list.end()) {
        adjacency_list[v] = std::vector<std::pair<vertex, int>>();
    }
}

That’s it! This ensures the vertex is in the graph with no connected edges, exactly what you need.

Building Out Iterators #

Your code already has skeleton iterator classes—let’s flesh them out using the adjacency list’s iterators under the hood:

Graph Iterator (for traversing all vertices) #

This wraps the std::map’s const iterator to let users loop through every vertex in the graph:

class graph_iterator {
private:
    typename std::map<vertex, std::vector<std::pair<vertex, int>>>::const_iterator it;
public:
    // Constructor for begin iterator
    graph_iterator(const weighted_graph& g) : it(g.adjacency_list.cbegin()) {}
    // Constructor for end iterator (the size_t parameter is just a dummy to distinguish)
    graph_iterator(const weighted_graph& g, size_t) : it(g.adjacency_list.cend()) {}
    ~graph_iterator() = default;

    graph_iterator& operator=(const graph_iterator& other) {
        if (this != &other) {
            it = other.it;
        }
        return *this;
    }

    bool operator==(const graph_iterator& other) const {
        return it == other.it;
    }

    bool operator!=(const graph_iterator& other) const {
        return !(*this == other);
    }

    // Prefix increment
    graph_iterator& operator++() {
        ++it;
        return *this;
    }

    // Postfix increment
    graph_iterator operator++(int) {
        graph_iterator temp = *this;
        ++it;
        return temp;
    }

    const vertex& operator*() {
        return it->first; // Dereference to get the vertex (the map's key)
    }

    const vertex* operator->() {
        return &(it->first);
    }
};

Neighbour Iterator (for traversing a vertex’s neighbors) #

This wraps the std::vector iterator from the adjacency list entry, so users can loop through a vertex’s connected edges:

class neighbour_iterator {
private:
    typename std::vector<std::pair<vertex, int>>::const_iterator it;
public:
    neighbour_iterator(const weighted_graph& g, const vertex& v) 
        : it(g.adjacency_list.at(v).cbegin()) {}
    neighbour_iterator(const weighted_graph& g, const vertex& v, size_t) 
        : it(g.adjacency_list.at(v).cend()) {}
    neighbour_iterator(const neighbour_iterator& other) : it(other.it) {}
    ~neighbour_iterator() = default;

    neighbour_iterator& operator=(const neighbour_iterator& other) {
        if (this != &other) {
            it = other.it;
        }
        return *this;
    }

    bool operator==(const neighbour_iterator& other) const {
        return it == other.it;
    }

    bool operator!=(const neighbour_iterator& other) const {
        return !(*this == other);
    }

    neighbour_iterator& operator++() {
        ++it;
        return *this;
    }

    neighbour_iterator operator++(int) {
        neighbour_iterator temp = *this;
        ++it;
        return temp;
    }

    const std::pair<vertex, int>& operator*() {
        return *it; // Returns (neighbor vertex, edge weight)
    }

    const std::pair<vertex, int>* operator->() {
        return &(*it);
    }
};

Add Iterator Accessors to the Public Interface #

Let users access these iterators by adding these to the public section of weighted_graph:

using iterator = graph_iterator;
using neighbour_iterator = neighbour_iterator;

iterator begin() const { return iterator(*this); }
iterator end() const { return iterator(*this, 0); }

neighbour_iterator neighbours_begin(const vertex& v) const { return neighbour_iterator(*this, v); }
neighbour_iterator neighbours_end(const vertex& v) const { return neighbour_iterator(*this, v, 0); }

Supporting DFS/BFS & MST #

With this adjacency list setup, implementing these operations becomes manageable:

• DFS: Use a std::stack to track vertices to visit, plus an std::unordered_set to mark visited vertices. Iterate through each vertex’s neighbors using the neighbour_iterator.
• BFS: Similar to DFS, but use a std::queue instead of a stack.
• Minimum Spanning Tree: For Prim’s algorithm, use a priority queue to track the smallest edge weights connecting unvisited vertices. For Kruskal’s, you’ll need to collect all edges, sort them, and use a union-find structure.

Quick Notes for a C++ Newbie #

• Make sure your vertex type supports operator< if using std::map (required for ordering). If you switch to std::unordered_map, you’ll need to define a hash function for your vertex type.
• The adjacency_list.at(v) call in the neighbour iterator will throw an exception if v doesn’t exist in the graph. You can adjust this to return an empty iterator or handle the error differently if needed.

内容的提问来源于stack exchange，提问作者Dan