加权无向图的定义及实现(Java语言)
程序员文章站
2022-04-15 18:01:13
1 定义加权无向图是一种为每条边关联一个权重值的图模型;可以用于多个领域。例如:在航空图中,边表示航线,权值表示距离或者费用;在电路图中,边表示导线,权值表示导线长度。2 边的实现使用对象来描述一条边。API设计:类名Edge implements Comparable构造方法Edge(int v, int w, double weight):通过顶点v和顶点w,以及权重weight值构造一个边对象成员方法1.public double weight():获取边...
1 定义
- 加权无向图是一种为每条边关联一个权重值的图模型;
- 可以用于多个领域。例如:在航空图中,边表示航线,权值表示距离或者费用;在电路图中,边表示导线,权值表示导线长度。
2 边的描述及实现
使用对象来描述一条边。
API设计:
类名 | Edge implements Comparable |
---|---|
构造方法 | Edge(int v, int w, double weight):通过顶点v和顶点w,以及权重weight值构造一个边对象 |
成员方法 | 1.public double weight():获取边的权重值 |
成员方法 | 2.public int either():获取边上的一个点 |
成员方法 | 3.public int other(int vertex):获取边上除了顶点vertex外的另外一个顶点 |
成员方法 | 4.public int compareTo(Edge that):比较当前边和参数that边的权重,如果当前边权重大,返回1,如果一样大,返回0,如果当前权重小,返回-1 |
成员变量 | 1.public final int v:顶点一 |
成员变量 | 2.public final int w:顶点二 |
成员变量 | 1.public final double weight:当前边的权重 |
代码:
public class Edge implements Comparable<Edge> {
private final int v;//顶点一
private final int w;//顶点二
private final double weight;//当前边的权重
@Override
public String toString() {
return "Edge{" +
"v=" + v +
", w=" + w +
", weight=" + weight +
'}';
}
//通过顶点v和w,以及权重weight值构造一个边对象
public Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
//获取边的权重值
public double weight(){
return weight;
}
//获取边上的一个点
public int either(){
return v;
}
//获取边上除了顶点vertex外的另外一个顶点
public int other(int vertex){
if (vertex==v){
return w;
}else{
return v;
}
}
@Override
public int compareTo(Edge that) {
int cmp;
if (this.weight()>that.weight()){
//如果当前边的权重大于参数边that的权重,返回1
cmp = 1;
}else if (this.weight()<that.weight()){
//如果当前边的权重小于参数边that的权重,返回-1
cmp=-1;
}else{
//如果当前边的权重等于参数边that的权重,返回0
cmp = 0;
}
return cmp;
}
}
3 图的实现
在无向图的基础上,将边的表示变换成Edge对象即可实现加权无向图。
public class EdgeWeightedGraph {
//顶点总数
private final int V;
//边的总数
private int E;
//邻接表
private Deque<Edge>[] adj;
//创建一个含有V个顶点的空加权无向图
public EdgeWeightedGraph(int V) {
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Deque[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
//获取图中顶点的数量
public int V() {
return V;
}
//获取图中边的数量
public int E() {
return E;
}
//向加权无向图中添加一条边e
public void addEdge(Edge e) {
//需要让边e同时出现在e这个边的两个顶点的邻接表中
int v = e.either();
int w = e.other(v);
adj[v].offer(e);
adj[w].offer(e);
//边的数量+1
E++;
}
//获取和顶点v关联的所有边
public Deque<Edge> adj(int v) {
return adj[v];
}
//获取加权无向图的所有边
public Deque<Edge> edges() {
//创建一个队列对象,存储所有的边
Deque<Edge> allEdges = new LinkedList<>();
//遍历顶点,拿到每个顶点的邻接表
for(int v =0;v<V;v++){
//遍历v顶点的邻接表,找到每一条和v关联的边
for (Edge e : adj(v)) {
/*
因为无向图中,每条边对象Edge都会在两个顶点的邻接表中各出现一次,为了不重复获取,暂定一条规则:
除了当前顶点v,再获取边e中的另外一个顶点w,如果w<v则添加,这样可以保证同一条边只会被统计一次
*/
if (e.other(v)<v){
allEdges.offer(e);
}
}
}
return allEdges;
}
}
public class Test {
public static void main(String[] args) {
EdgeWeightedGraph g = new EdgeWeightedGraph(5);
Edge e1 = new Edge(0,1,1);
Edge e2 = new Edge(1,2,2);
Edge e3 = new Edge(4,3,3);
g.addEdge(e1);
g.addEdge(e2);
g.addEdge(e3);
System.out.println(g.edges());
}
}
[Edge{v=0, w=1, weight=1.0}, Edge{v=1, w=2, weight=2.0}, Edge{v=4, w=3, weight=3.0}]
本文地址:https://blog.csdn.net/sc179/article/details/110262437