上述代码只能解决添加一条重边的情况,请优化代码,使其适用于所有无向带权图
时间: 2023-06-27 17:02:48 浏览: 42
好的,下面是可以处理所有无向带权图的代码:
```python
def add_edge(u, v, w):
if u not in graph:
graph[u] = {}
if v not in graph:
graph[v] = {}
if v in graph[u]:
graph[u][v] = min(graph[u][v], w)
graph[v][u] = min(graph[v][u], w)
else:
graph[u][v] = w
graph[v][u] = w
```
这个函数首先检查图中是否已经存在起点为`u`,终点为`v`的边,如果存在,则更新该边的权值为新权值`w`和原来的权值的较小值。如果不存在,则创建一条新的边,并将其权值设为`w`。同时,由于是无向图,还需要在`v`的邻接表中添加起点为`u`,终点为`v`的边,并将其权值设为`w`。
这个函数的时间复杂度是$O(1)$,与图的大小无关,因此非常适合处理大型图。
相关问题
无向带权图删边的代码
对于无向带权图的删除边操作,可以通过遍历边集合,找到需要删除的边并移除它。下面是一个示例代码:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
self.edges = []
def add_edge(self, u, v, weight):
self.adj_list[u].append((v, weight))
self.adj_list[v].append((u, weight))
self.edges.append((u, v, weight))
def remove_edge(self, u, v):
for i, (x, y, _) in enumerate(self.edges):
if (u, v) == (x, y) or (v, u) == (x, y):
self.adj_list[u] = [edge for edge in self.adj_list[u] if edge[0] != v]
self.adj_list[v] = [edge for edge in self.adj_list[v] if edge[0] != u]
del self.edges[i]
break
# 创建一个无向带权图
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 5)
g.add_edge(1, 2, 3)
g.add_edge(1, 4, 1)
g.add_edge(2, 3, 4)
# 删除边(1, 4)
g.remove_edge(1, 4)
```
用c语言代码输出无向带权图的邻接表
好的,以下是C语言代码输出无向带权图的邻接表的示例:
```c
#include <stdio.h>
#define MAXV 1000 // 最大顶点数
#define INF 0x3f3f3f3f // 表示无穷大的值
int n, m; // 顶点数和边数
int adj[MAXV][MAXV]; // 邻接矩阵表示图
int degree[MAXV]; // 存储每个顶点的度数
void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj[i][j] = INF; // 初始化为无穷大
}
}
}
void addEdge(int u, int v, int w) { // 添加边
adj[u][v] = w;
adj[v][u] = w;
degree[u]++;
degree[v]++;
}
void printGraph() { // 输出邻接表
printf("Vertex\tDegree\tAdjacency List\n");
for (int i = 1; i <= n; i++) {
printf("%d\t%d\t", i, degree[i]);
for (int j = 1; j <= n; j++) {
if (adj[i][j] != INF && i < j) {
printf("%d(%d) ", j, adj[i][j]);
}
}
printf("\n");
}
}
int main() {
scanf("%d %d", &n, &m); // 输入顶点数和边数
init();
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w); // 输入每条边的起点、终点、权值
addEdge(u, v, w); // 添加边
}
printGraph(); // 输出邻接表
return 0;
}
```
Hope it helps!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)