一.概述
加权无向图是一种为每条边关联一个权重值或成本的图模型。这种图能够自然地表示许多应用。
在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题。
二.实现
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
在这里插入图片描述
加权边类：
//加权边对象
public class Edge implements Comparable<Edge>{
private final int v; //顶点v
private final int w; //顶点w
private final double weight; //当前边顶点权重
public Edge(int v, int w, double weight) { //初始化边类Edge
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight(){ //获取边的权重
return weight;
}
public int either(){ //返回边上的顶点v
return v;
}
public int other(int y) { //返回边上除了顶点传入顶点y的另外一个顶点
if (y == v) {
return w;
} else {
return v;
}
}
@Override
public int compareTo(Edge o) {
int r = 0;
//如果当前边权重值大于o，则让r=1；
if(this.weight()>o.weight()){
r=1;
}else if(this.weight()<o.weight()){
r=-1;
}else if(this.weight()==o.weight()){
r=0;
}
return r;
}
}
加权无向图：
//加权无向图
class pathWeight{
private int V; //顶点个数
private int E; //边的个数
private Queue<Edge>[] adj; //每个邻接表中存的都是Edge ！而不是普通顶点了
public pathWeight(int v) { //初始化
this.V = v;
this.E = 0;
this.adj = new LinkedList[v];
for(int i=0;i<v;i++){
adj[i]=new LinkedList<>(); //初始化adj数组的每一个元素 即顶点
}
}
public int V(){
return V;
}
public int E(){
return E;
}
public void addEdge(Edge e){
//无向图，让边出现在两个顶点的邻接表中！
int v=e.either();//获取顶点v
int w=e.other(v);//获取顶点w
adj[v].add(e); //将e边添加到v的邻接表中
adj[w].add(e); //将e边添加到w的邻接表中
E++;
}
public Queue<Edge> adj(int v){ //返回v的邻接表，即v关联的所有边
return adj[v];
}
public Queue<Edge> edgs(){ //获取所有边
Queue<Edge> allEdges=new LinkedList<>();
//遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存的是该顶点关联的每一条边
//由于是无向图，同一条边出现在两个顶点的邻接表中，要避免重复
//避免重复： 当边的一个顶点比另一个小时才添加，否则不添加！
for(int v=0;v<V;v++){ //遍历每个顶点
for (Edge k : adj[v]) { //遍历每个顶点的邻接表
if(v>k.other(v)){ //比较v和另一个顶点w，满足条件则添加至allEdges
allEdges.add(k);
}
}
}
return allEdges;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89348.html
