用C#设计无向带权图类,包括字段设计、构造函数设计,插入边、插入顶点、删除边、删除顶点等主要方法设计。
时间: 2023-11-20 08:06:26 浏览: 81
带权无向图
5星 · 资源好评率100%
好的,以下是用C#设计无向带权图类的代码:
```csharp
using System;
using System.Collections.Generic;
namespace Graph
{
class Graph
{
private int V; // 顶点数量
private int E; // 边数量
private List<List<(int, int)>> adj; // 邻接表,用元组存储与顶点相连的顶点和边权
// 构造函数
public Graph(int v = 0)
{
V = v;
E = 0;
adj = new List<List<(int, int)>>();
// 初始化邻接表为空列表
for (int i = 0; i < V; i++)
{
adj.Add(new List<(int, int)>());
}
}
// 插入顶点
public void AddVertex(int v)
{
adj.Add(new List<(int, int)>());
V++;
}
// 插入边
public void AddEdge(int u, int v, int w)
{
adj[u].Add((v, w));
adj[v].Add((u, w));
E++;
}
// 删除顶点
public void RemoveVertex(int v)
{
// 删除与顶点v相连的所有边
foreach ((int u, int w) in adj[v])
{
adj[u].RemoveAll(x => x.Item1 == v);
E--;
}
// 删除邻接表中的顶点v
adj.RemoveAt(v);
V--;
}
// 删除边
public void RemoveEdge(int u, int v)
{
adj[u].RemoveAll(x => x.Item1 == v);
adj[v].RemoveAll(x => x.Item1 == u);
E--;
}
// 获取相邻顶点
public List<(int, int)> GetNeighbors(int v)
{
return adj[v];
}
// 获取边权重
public int GetWeight(int u, int v)
{
foreach ((int neighbor, int weight) in adj[u])
{
if (neighbor == v)
{
return weight;
}
}
return 0; // 如果u和v之间没有边,则返回0
}
}
}
```
这个类有私有字段V、E和adj,分别表示顶点数量、边数量和邻接表。其中邻接表adj是一个列表,每个元素是一个列表,用元组存储与该顶点相连的顶点和边权。
这个类有构造函数和五个主要方法:
- 构造函数:可以传入顶点数量V,也可以不传入,不传入时默认为0,同时将邻接表adj初始化为空列表
- 插入顶点:AddVertex(int v):向图中添加一个顶点v,即在邻接表中添加一个新的空列表
- 插入边:AddEdge(int u, int v, int w):向图中添加一条从顶点u到顶点v的权重为w的边。要注意这是一个无向图,所以还需要添加一条从顶点v到顶点u的权重为w的边。同时更新顶点u和顶点v在邻接表中的信息
- 删除顶点:RemoveVertex(int v):从图中删除一个顶点v,即删除邻接表中对应的列表以及所有与之相连的边
- 删除边:RemoveEdge(int u, int v):从图中删除一条从顶点u到顶点v的边。同时也需要删除一条从顶点v到顶点u的边。同时更新顶点u和顶点v在邻接表中的信息
- 获取相邻顶点:GetNeighbors(int v):获取与顶点v相连的所有顶点以及对应的边的权重
- 获取边权重:GetWeight(int u, int v):获取顶点u和顶点v之间的边的权重
阅读全文