1.加权无向图

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

边的实现：

  1. package 图;
  3. public class Edge implements Comparable<Edge> {
  4.     private final int v;//顶点一
  5.     private final int w;//顶点二
  6.     private final double weight;//当前边的权重
  8.     //通过顶点v和w，以及权重weight值构造一个边对象
  9.     public Edge(int v, int w, double weight) {
  10.         this.v = v;
  11.         this.w = w;
  12.         this.weight = weight;
  13.     }
  15.     //获取边的权重值
  16.     public double weight() {
  17.         return weight;
  18.     }
  20.     //获取边上的一个点
  21.     public int either() {
  22.         return v;
  23.     }
  25.     //获取边上除了顶点vertex外的另外一个顶点
  26.     public int other(int vertex) {
  27.         if (vertex == v) {
  28.             //如果传入的顶点vertext是v，则返回另外一个顶点w
  29.             return w;
  30.         } else {
  31.             //如果传入的顶点vertext不是v，则返回v即可
  32.             return v;
  33.         }
  34.     }
  36.     @Override
  37.     public int compareTo(Edge that) {
  38.         int cmp;
  39.         if (this.weight() > that.weight()) {
  40.             //如果当前边的权重大于参数边that的权重，返回1
  41.             cmp = 1;
  42.         } else if (this.weight() < that.weight()) {
  43.             //如果当前边的权重小于参数边that的权重，返回-1
  44.             cmp = -1;
  45.         } else {
  46.             //如果当前边的权重等于参数边that的权重，返回0
  47.             cmp = 0;
  48.         }
  49.         return cmp;
  50.     }
  51. }

加权无向图的实现:

  1. package 图;
  3. import 线性表.Queue;
  5. public class EdgeWeightedGraph {
  6.     //顶点总数
  7.     private final int V;
  8.     //边的总数
  9.     private int E;
  10.     //邻接表
  11.     private Queue<Edge>[] adj;
  13.     //创建一个含有V个顶点的空加权无向图
  14.     public EdgeWeightedGraph(int V) {
  15.         //初始化顶点数量
  16.         this.V = V;
  17.         //初始化边的数量
  18.         this.E = 0;
  19.         //初始化邻接表
  20.         this.adj = new Queue[V];
  21.         //初始化邻接表中的空队列
  22.         for (int i = 0; i < adj.length; i++) {
  23.             adj[i] = new Queue<Edge>();
  24.         }
  25.     }
  27.     //获取图中顶点的数量
  28.     public int V() {
  29.         return V;
  30.     }
  32.     //获取图中边的数量
  33.     public int E() {
  34.         return E;
  35.     }//向加权无向图中添加一条边e
  37.     public void addEdge(Edge e) {
  38.         //获取边中的一个顶点v
  39.         int v = e.either();
  40.         //获取边中的另一个顶点w
  41.         int w = e.other(v);
  42.         //因为是无向图，所以边e需要同时出现在两个顶点的邻接表中
  43.         adj[v].enqueue(e);
  44.         adj[w].enqueue(e);
  45.         //边的数量+1
  46.         E++;
  47.     }
  49.     //获取和顶点v关联的所有边
  50.     public Queue<Edge> adj(int v) {
  51.         return adj[v];
  52.     }
  54.     //获取加权无向图的所有边
  55.     public Queue<Edge> edges() {
  56.         //创建一个队列，存储所有的边
  57.         Queue<Edge> allEdge = new Queue<>();
  58.         //遍历顶点，拿到每个顶点的邻接表
  59.         for (int v = 0; v < this.V; v++) {
  60.             //遍历邻接表，拿到邻接表中的每条边
  61.             for (Edge e : adj(v)) {
  62. /*
  63. 因为无向图中，每条边对象Edge都会在两个顶点的邻接表中各出现一次，为了不重复获取，暂定
  64. 一条规则：
  65. 除了当前顶点v，再获取边e中的另外一个顶点w，如果v<w则添加，这样可以保证同一条边
  66. 只会被统计一次
  67. */
  68.                 if (e.other(v) < v) {
  69.                     allEdge.enqueue(e);
  70.                 }
  71.             }
  72.         }
  73.         return allEdge;
  74.     }
  75. }

2.加权有向图

边的实现：

  1. package 图;
  3. public class DirectedEdge {
  4.     private final int v;//起点
  5.     private final int w;//终点
  6.     private final double weight;//当前边的权重
  8.     //通过顶点v和w，以及权重weight值构造一个边对象
  9.     public DirectedEdge(int v, int w, double weight) {
  10.         this.v = v;
  11.         this.w = w;
  12.         this.weight = weight;
  13.     }
  15.     //获取边的权重值
  16.     public double weight() {
  17.         return weight;
  18.     }
  20.     //获取有向边的起点
  21.     public int from() {
  22.         return v;
  23.     }
  25.     //获取有向边的终点
  26.     public int to() {
  27.         return w;
  28.     }
  29. }

加权有向图的实现:

  1. package 图;
  3. import 线性表.Queue;
  5. public class EdgeWeightedDigraph {
  6.     //顶点总数
  7.     private final int V;
  8.     //边的总数
  9.     private int E;
  10.     //邻接表
  11.     private Queue<DirectedEdge>[] adj;
  13.     //创建一个含有V个顶点的空加权有向图
  14.     public EdgeWeightedDigraph(int V) {
  15.         //初始化顶点数量
  16.         this.V = V;
  17.         //初始化边的数量
  18.         this.E = 0;
  19.         //初始化邻接表
  20.         this.adj = new Queue[V];
  21.         //初始化邻接表中的空队列
  22.         for (int i = 0; i < adj.length; i++) {
  23.             adj[i] = new Queue<DirectedEdge>();
  24.         }
  25.     }
  27.     //获取图中顶点的数量
  28.     public int V() {
  29.         return V;
  30.     }
  32.     //获取图中边的数量
  33.     public int E() {
  34.         return E;
  35.     }
  37.     //向加权有向图中添加一条边e
  38.     public void addEdge(DirectedEdge e) {
  39.         //获取有向边的起点
  40.         int v = e.from();
  41.         //因为是有向图，所以边e只需要出现在起点v的邻接表中
  42.         adj[v].enqueue(e);
  43.         //边的数量+1
  44.         E++;
  45.     }
  47.     //获取由顶点v指出的所有的边
  48.     public Queue<DirectedEdge> adj(int v) {
  49.         return adj[v];
  50.     }
  52.     //获取加权有向图的所有边
  53.     public Queue<DirectedEdge> edges() {
  54.         //创建一个队列，存储所有的边
  55.         Queue<DirectedEdge> allEdge = new Queue<>();
  56.         //遍历顶点，拿到每个顶点的邻接表
  57.         for (int v = 0; v < this.V; v++) {
  58.             //遍历邻接表，拿到邻接表中的每条边存储到队列中
  59.             for (DirectedEdge e : adj(v)) {
  60.                 allEdge.enqueue(e);
  61.             }
  62.         }
  63.         return allEdge;
  64.     }
  65. }