加权无向图的定义及实现（Java语言）

1 定义

1. 加权无向图是一种为每条边关联一个权重值的图模型；
2. 可以用于多个领域。例如：在航空图中，边表示航线，权值表示距离或者费用；在电路图中，边表示导线，权值表示导线长度。

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