c++请编写程序对给定的有向图删除若干条边。有向图中包含n个顶点,编号为0至n-1。
时间: 2023-11-26 18:59:45 浏览: 123
有向图中简单路径计数及最短路径最长路径的输出
以下是一种基于邻接表的实现方法,可以删除多条边:
```c++
#include <iostream>
#include <vector>
using namespace std;
void removeEdge(vector<vector<int>>& graph, int u, int v) {
for (int i = 0; i < graph[u].size(); i++) {
if (graph[u][i] == v) {
graph[u].erase(graph[u].begin() + i);
return;
}
}
}
int main() {
int n = 5; // 顶点数
vector<vector<int>> graph(n); // 邻接表表示的有向图
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[3].push_back(4);
// 删除边(0, 2)和(2, 4)
removeEdge(graph, 0, 2);
removeEdge(graph, 2, 4);
// 输出删除后的图
for (int u = 0; u < n; u++) {
cout << u << ": ";
for (int v : graph[u]) {
cout << v << " ";
}
cout << endl;
}
return 0;
}
```
在这个程序中,我们用一个二维向量 `graph` 存储有向图的邻接表,其中 `graph[u]` 存储从顶点 `u` 出发的所有边的终点。我们可以通过遍历 `graph[u]` 找到和顶点 `u` 有一条边连接到顶点 `v`,然后删除这条边。在上面的例子中,我们删除了边(0, 2)和(2, 4),然后输出删除后的图。
阅读全文