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

时间:2022-11-05 JAVA旭阳人气:0

前言

加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？
在下图中，从顶点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;
    }
}

加载全部内容