图的存储表示是否允许重复边？C++实现邻接表/矩阵应如何处理

核心结论 #

同一条边是否允许重复表示，完全取决于你要实现的图类型：

• 简单图：默认不允许两个顶点之间存在多条同方向边（无向图则不允许两顶点间存在任意多条重复边），也不允许自环（严格简单图规则）
• 多重图：允许两个顶点之间存在多条独立边，典型适用场景比如记录两个城市之间的多趟航班、两个节点之间的多条通信链路等，每条边都代表独立的实体/权重。

不同存储结构的支持情况 #

邻接表 #

天生适配多重图的重复边存储，你给出的示例中1 => 2 4 5 5就是标准的多重图邻接表写法，代表顶点1到顶点5存在两条独立的边，完全符合语法规则。

邻接矩阵 #

默认的简单图邻接矩阵每个单元格仅存0（无边）/1（有边），如果要支持多重图，可以将单元格的取值改为边的数量，或者用数组/链表存储同位置多条边的属性，即可支持重复边存储。

课程作业实现建议 #

你可以根据作业的明确要求选择处理逻辑：

1. 如果要求实现简单图：插入已存在的边时，两种处理方式都符合要求，建议在代码注释中明确说明你的选择：
   • 方案1：直接忽略重复插入请求，不做任何修改
   • 方案2：抛出错误提示，告知用户边已存在
2. 如果没有明确说明、或要求支持多重图：直接允许插入重复边即可，注意配套的删除边逻辑也要对应设计：明确单次删除操作是仅删除一条匹配的边，还是删除所有匹配的重复边。

以下是C++实现的参考代码片段：

// 简单图addEdge实现示例
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;

vector<vector<int>> adj;

void addEdge(int u, int v) {
    // 检查边是否已存在
    if (find(adj[u].begin(), adj[u].end(), v) != adj[u].end()) {
        // 二选一：要么抛出异常，要么直接return忽略
        throw invalid_argument("Edge already exists!");
        // return;
    }
    adj[u].push_back(v);
    // 无向图需要额外加 adj[v].push_back(u);
}

// 多重图addEdge实现示例，无需判重
void addEdge_multigraph(int u, int v) {
    adj[u].push_back(v);
    // 无向图需要额外加 adj[v].push_back(u);
}

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