基于邻接表的图的边添加与删除函数实现求助

First, let’s clarify some assumptions based on your code framework:

• Your Graph class presumably has a private VertexList mVertices member (this is the core adjacency list structure).
• Vertices are identified by non-negative integers (0-indexed).
• We’ll start with a directed graph implementation (edges only go from mV to mW), then note how to adjust for undirected graphs.

Implementing addEdge #

The goal here is to add a directed edge from vertex mV to mW with the specified weight. Here’s a step-by-step breakdown and code:

Key Steps: #

1. Validate vertex indices: Ensure mV and mW are non-negative (negative indices don’t make sense for our vector-based list).
2. Resize the adjacency list if needed: If mV is larger than the current size of mVertices, expand the list to include this vertex (since vectors are 0-indexed).
3. Check for duplicates (optional): Avoid adding the same edge multiple times unless your use case allows it.
4. Add the edge: Push a new Node into mV’s adjacency list.

Code: #

bool Graph::addEdge(const Edge& edge) {
    // Reject invalid negative vertex indices
    if (edge.mV < 0 || edge.mW < 0) {
        return false;
    }

    // Expand the vertex list to accommodate mV if it doesn't exist yet
    if (edge.mV >= mVertices.size()) {
        mVertices.resize(edge.mV + 1);
    }

    // Check if the edge already exists (skip this if duplicates are allowed)
    const auto& adjList = mVertices[edge.mV];
    for (const auto& node : adjList) {
        if (node.mEnd == edge.mW) {
            return false; // Edge already present
        }
    }

    // Add the new edge to mV's adjacency list
    mVertices[edge.mV].push_back(Node{edge.mW, edge.mWeight});
    return true;
}

For Undirected Graphs: #

If your graph is undirected, you need to add the reverse edge (from mW to mV) as well. Modify the function like this:

bool Graph::addEdge(const Edge& edge) {
    // Keep validation and resize steps from above

    // Add edge mV -> mW
    mVertices[edge.mV].push_back(Node{edge.mW, edge.mWeight});

    // Add reverse edge mW -> mV
    if (edge.mW >= mVertices.size()) {
        mVertices.resize(edge.mW + 1);
    }
    mVertices[edge.mW].push_back(Node{edge.mV, edge.mWeight});

    return true;
}

(Remember to adjust the duplicate check for the reverse edge if you’re keeping that step!)

Implementing removeEdge #

This function removes a directed edge from mV to mW. Here’s how to do it:

Key Steps: #

1. Check if mV is valid: If mV is out of bounds for mVertices, return false immediately.
2. Find the edge: Iterate through mV’s adjacency list to locate the node where mEnd == mW.
3. Erase the edge: If found, remove the node from the vector. Return true if successful, false otherwise.

Code: #

bool Graph::removeEdge(const Edge& edge) {
    // Check if mV is a valid existing vertex
    if (edge.mV < 0 || edge.mV >= mVertices.size()) {
        return false;
    }

    auto& adjList = mVertices[edge.mV];
    // Search for the edge to remove
    for (auto it = adjList.begin(); it != adjList.end(); ++it) {
        if (it->mEnd == edge.mW) {
            adjList.erase(it);
            return true;
        }
    }

    // Edge not found in the adjacency list
    return false;
}

For Undirected Graphs: #

Remove the reverse edge too:

bool Graph::removeEdge(const Edge& edge) {
    // Keep initial check and remove mV -> mW as above

    // Remove the reverse edge mW -> mV
    if (edge.mW >= 0 && edge.mW < mVertices.size()) {
        auto& reverseAdjList = mVertices[edge.mW];
        for (auto it = reverseAdjList.begin(); it != reverseAdjList.end(); ++it) {
            if (it->mEnd == edge.mV) {
                reverseAdjList.erase(it);
                break; // No need to search further
            }
        }
    }

    return true;
}

Additional Notes: #

• Updating Edge Weights: If you want to allow updating the weight of an existing edge instead of returning false in addEdge, replace the duplicate check with code that updates the mWeight of the matching node.
• Performance: Linear search in the adjacency list can be slow for large graphs. For faster lookups, consider using std::unordered_set or std::map for each adjacency list instead of std::vector (this will require minor changes to your structure).
• Predefined Vertices: If you want to restrict vertices to a fixed set, add a check to ensure mV and mW are in that set before proceeding.

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