给定一个无向图,在此无向图中删除一条边
时间: 2024-03-07 07:49:11 浏览: 136
在邻接表表示法中,删除一条边可以分为两个步骤:
1. 找到待删除的边
2. 从邻接表中删除该边
下面是一个示例函数,可以在以邻接表形式存储的无向图 `G` 上删除一条边 `(u, v)`。
```
int DeleteArc(ALGragh &G, int u, int v) {
// 找到待删除的边
ArcNode* pre = nullptr;
ArcNode* cur = G.vertices[u].firstarc;
while (cur != nullptr && cur->adjvex != v) {
pre = cur;
cur = cur->nextarc;
}
if (cur == nullptr) {
// 边不存在
return ERROR;
}
// 从邻接表中删除该边
if (pre == nullptr) {
// 删除第一条边
G.vertices[u].firstarc = cur->nextarc;
} else {
pre->nextarc = cur->nextarc;
}
delete cur;
// 对称删除
pre = nullptr;
cur = G.vertices[v].firstarc;
while (cur != nullptr && cur->adjvex != u) {
pre = cur;
cur = cur->nextarc;
}
if (cur == nullptr) {
// 边不存在
return ERROR;
}
if (pre == nullptr) {
// 删除第一条边
G.vertices[v].firstarc = cur->nextarc;
} else {
pre->nextarc = cur->nextarc;
}
delete cur;
G.arcnum--;
return OK;
}
```
其中,`u` 和 `v` 是边 `(u, v)` 的两个顶点,`G` 是邻接表表示的无向图。该函数返回 `OK` 表示删除成功,返回 `ERROR` 表示边不存在。在删除边 `(u, v)` 之后,还需要对称删除边 `(v, u)`。
阅读全文