如何基于自定义C++邻接表图结构实现边的添加？

首先，咱们先梳理下你现有的图结构：你的Graph是顶点的集合，每个Vertex用邻接表（vector<Edge>）存储相连的边，每条Edge记录了起点、终点指针和遍历时间。要实现边的添加，核心是找到对应的源顶点和目标顶点，然后把边对象加入源顶点的邻接列表里（如果是无向图还要处理反向边）。

第一步：实现顶点查找辅助函数 #

因为你的Graph里的顶点存在vector<Vertex>中，咱们需要先写一个根据id查找对应顶点指针的函数，这样才能在添加边时精准定位到源和目标顶点：

Vertex* findVertexById(Graph* graph, int id) {
    for (auto& vertex : graph->vertices) {
        if (vertex.id == id) {
            // 返回指向该顶点的指针
            return &vertex;
        }
    }
    // 没找到对应顶点，返回nullptr
    return nullptr;
}

第二步：实现添加边的函数 #

接下来就可以写addEdge函数了，这里分两种常见场景：有向图和无向图，我都给你整理好：

场景1：添加有向边

有向边只需要在源顶点的邻接列表中添加一条指向目标顶点的边：

bool addEdge(Graph* graph, int sourceId, int destId, int traverseTime) {
    // 查找源顶点和目标顶点
    Vertex* source = findVertexById(graph, sourceId);
    Vertex* dest = findVertexById(graph, destId);

    // 检查两个顶点是否都存在
    if (!source || !dest) {
        // 顶点不存在，添加失败
        return false;
    }

    // 创建新的边对象
    Edge newEdge;
    newEdge.org = source;
    newEdge.dest = dest;
    newEdge.traverse_time = traverseTime;

    // 将边添加到源顶点的邻接列表
    source->edges.push_back(newEdge);

    // 添加成功
    return true;
}

场景2：添加无向边

无向图需要同时添加两条互逆的边：源到目标，以及目标到源：

bool addUndirectedEdge(Graph* graph, int vertexAId, int vertexBId, int traverseTime) {
    Vertex* vertexA = findVertexById(graph, vertexAId);
    Vertex* vertexB = findVertexById(graph, vertexBId);

    if (!vertexA || !vertexB) {
        return false;
    }

    // 添加A到B的边
    Edge edgeAB;
    edgeAB.org = vertexA;
    edgeAB.dest = vertexB;
    edgeAB.traverse_time = traverseTime;
    vertexA->edges.push_back(edgeAB);

    // 添加B到A的边
    Edge edgeBA;
    edgeBA.org = vertexB;
    edgeBA.dest = vertexA;
    edgeBA.traverse_time = traverseTime;
    vertexB->edges.push_back(edgeBA);

    return true;
}

第三步：使用示例 #

你可以像这样调用这些函数，和你添加顶点的逻辑配合使用：

// 创建图和顶点
Graph* g1 = new Graph;
Vertex* newVertex0 = addVertex(0);
g1->vertices.push_back(*newVertex0);
Vertex* newVertex1 = addVertex(1);
g1->vertices.push_back(*newVertex1);

// 添加有向边：0 -> 1，遍历时间为5
addEdge(g1, 0, 1, 5);

// 或者添加无向边：0 <-> 1，遍历时间为5
// addUndirectedEdge(g1, 0, 1, 5);

注意事项 #

• 确保你的addVertex函数生成的顶点id是唯一的，不然findVertexById可能会返回错误的顶点（比如多个顶点id相同的话，只会找到第一个匹配的）。
• 如果需要处理顶点不存在的异常情况，可以通过addEdge返回的bool值在业务逻辑里做错误处理。

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