Java数据结构之加权无向图的设计实现

目录

• 前言
• 边的表示
• API设计
• 代码实现
• 图的实现
• API设计
• 代码实现

前言

加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低。

边的表示

加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。

API设计

类名Edge implements Comparable成员变量1.private final int v：顶点一2.private final int w：顶点二3.private final double weight：当前边的权重构造方法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

代码实现

/**
 * 边
 *
 * @author alvin
 * @date 2022/11/3
 * @since 1.0
 **/
public class Edge implements Comparable<Edge> {
    //顶点一
    private final int v;
    //顶点二
    private final int w;
    //当前边的权重
    private final double 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()) {
            //如果当前边的权重值大，则让cmp=1；
            cmp = 1;
        } else if (this.weight() < that.weight()) {
            //如果当前边的权重值小，则让cmp=-1；
            cmp = -1;
        } else {
            //如果当前边的权重值和that边的权重值一样大，则让cmp=0
            cmp = 0;
        }

        return cmp;
    }
}

图的实现

之前我们已经完成了无向图，在无向图的基础上，我们只需要把边的表示切换成Edge对象即可。

API设计

类名EdgeWeightedGraph成员变量1.private final int V: 记录顶点数量2.private int E: 记录边数量3.private Queue[] adj: 邻接表构造方法EdgeWeightedGraph(int V)：创建一个含有V个顶点的空加权无向图成员方法1.public int V():获取图中顶点的数量2.public int E():获取图中边的数量3.public void addEdge(Edge e):向加权无向图中添加一条边e4.public Queue adj(int v)：获取和顶点v关联的所有边5.public Queue edges()：获取加权无向图的所有边

代码实现

/**
 * 加权无向图的实现
 *
 * @author alvin
 * @date 2022/11/3
 * @since 1.0
 **/
public class EdgeWeightedGraph {
    //顶点总数
    private final int V;
    //边的总数
    private int E;
    //邻接表
    private Queue<Edge>[] adj;

    //创建一个含有V个顶点的空加权无向图
    public EdgeWeightedGraph(int V) {
        //初始化顶点数量
        this.V = V;
        //初始化边的数量
        this.E = 0;
        //初始化邻接表
        this.adj = new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayDeque<>();
        }

    }

    //获取图中顶点的数量
    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].add(e);
        adj[w].add(e);

        //边的数量+1
        E++;
    }

    //获取和顶点v关联的所有边
    public Queue<Edge> adj(int v) {
        return adj[v];
    }

    //获取加权无向图的所有边
    public Queue<Edge> edges() {
        //创建一个队列对象，存储所有的边
        Queue<Edge> allEdges = new ArrayDeque<>();

        //遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边
        //因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只记录一次；
        for (int v = 0; v < V; v++) {
            //遍历v顶点的邻接表，找到每一条和v关联的边
            for (Edge e : adj(v)) {
                if (e.other(v) < v) {
                    allEdges.add(e);
                }
            }
        }
        return allEdges;
    }
}

到此这篇关于Java数据结构之加权无向图的设计实现的文章就介绍到这了,更多相关Java加权无向图内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！