【算法基础实验】图论-构建加权无向图

构建加权无向图

理论基础

在图论中，加权无向图是一种每条边都分配了一个权重或成本的图形结构。这种类型的图在许多实际应用中都非常有用，如路由算法、网络流量设计、最小生成树和最短路径问题等。

加权无向图的基本特征

顶点和边：
- 顶点（Vertex）: 图中的节点，可以表示交叉点、位置点或网络中的节点等。
- 边（Edge）: 连接顶点的线，无向边意味着连接的顶点间没有方向性的区别。
权重：
- 每条边都有一个权重（或成本、长度），这个权重是一个数值，代表了从一个顶点到另一个顶点的“成本”。
- 权重可以表示多种含义，如距离、时间、消耗或任何其他度量标准。

存储加权无向图

加权无向图通常可以通过以下几种数据结构来存储和表示：

邻接矩阵：
- 使用二维数组来表示顶点之间的连接关系，矩阵中的每个元素代表边的权重。如果两个顶点之间没有直接连接，则该位置通常用一个特殊值（如无穷大或null）来表示。
邻接表：
- 每个顶点都对应一个列表，列表中存储了与该顶点直接相连的其他顶点及相应的权重。这种表示方法更加节省空间，尤其是在稀疏图中。
边的列表：
- 维护一个所有边的列表，每条边由一对顶点和一个权重组成。

图的操作

操作加权无向图常见的算法包括但不限于：

最小生成树（MST）：
- 寻找一种方式，通过树形结构连接图中的所有顶点，使得所有边的权重总和最小。常用算法包括Kruskal算法和Prim算法。
最短路径：
- 寻找顶点间的最短路径，即路径上的权重总和最小。常用算法包括Dijkstra算法和Floyd-Warshall算法。
网络流量优化：
- 在网络图中，寻找最优的数据流方式，使得成本最低或效率最高。

应用实例

加权无向图的应用非常广泛，例如：

交通网络：道路或铁路网中的路径规划，权重可以是距离、时间或通行费用。
电信网络：数据包的传输路径优化，权重可能是延迟或带宽。
物流配送：货物配送路线的优化，权重可能包括距离和成本。
资源分配：如电网中电力的分配。

加权无向图的研究和应用提供了一种强大的工具，可以解决实际中的许多优化和规划问题。在算法和数据结构的领域中，理解并有效使用这些工具是非常重要的。

数据结构和实验数据

请添加图片描述

代码实现

myEdge

java">public class myEdge implements Comparable<myEdge>
{private final int v;private final int w;private final double weight;public myEdge(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;}public int other(int vertex){if(vertex == v) return w;else if(vertex == w) return v;else throw new IllegalArgumentException("Invalid vertex");}public int compareTo(myEdge that){if(this.weight()<that.weight()) return -1;else if(this.weight()>that.weight()) return 1;else return 0;}public String toString(){ return String.format("%d-%d %.2f",v,w,weight);}
}

这段代码定义了一个名为 myEdge 的类，代表加权无向图中的一条边。类实现了 Comparable 接口，允许边对象之间进行比较，这通常用于算法中需要对边进行排序的情况，例如在构建最小生成树时。以下是对该类中每个部分的详细解释：

类定义和字段

java">
public class myEdge implements Comparable

类定义和字段

java">
public class myEdge implements Comparable

这段代码定义了一个名为 myEdge 的 Java 类，用于表示加权无向图的一条边。这个类实现了 `Comparable

这段代码定义了一个名为 myEdge 的 Java 类，用于表示加权无向图的一条边。这个类实现了 Comparable 接口，使得边可以根据权重进行排序，这是在图算法中常见的需求，特别是在最小生成树和最短路径算法中。

类字段

v 和 w：这两个 private final int 类型的字段代表边连接的两个顶点。final 表明一旦边被创建，这两个顶点不可更改。
weight：这是一个 private final double 类型的字段，存储边的权重。同样，final 表示权重在创建后不可更改。

构造函数

java">
public myEdge(int v, int w, double weight) {this.v = v;this.w = w;this.weight = weight;
}

构造函数接收两个顶点标识和一个权重，初始化边的基本属性。

方法

weight()：返回边的权重。

java">
public double weight() { return weight; }

either()：返回边的一个顶点。此方法用于访问边的任一端点，通常在边的迭代中使用。
```
java">
public int either() { return v; }
```

other(int vertex)：给定边的一个顶点，返回另一个顶点。如果传入的顶点不是这条边的一部分，抛出 IllegalArgumentException。

java">
public int other(int vertex) {if (vertex == v) return w;else if (vertex == w) return v;else throw new IllegalArgumentException("Invalid vertex");
}

compareTo(myEdge that)：实现 `Comparable接口的方法，用于比较两条边的权重。这使得边可以被排序，通常用于算法如 Kruskal 的最小生成树算法中。
```
java">
public int compareTo(myEdge that) {return Double.compare(this.weight, that.weight);
}
```
toString()：提供边的字符串表示，格式为 “v-w weight”，其中 v 和 w 是顶点标识，weight 是边的权重。这对于打印和调试很有用。
```
java">
public String toString() {return String.format("%d-%d %.2f", v, w, weight);
}
```

总结

myEdge 类提供了一个结构化的方式来表示图中的边，包括边的两个端点和权重。实现 Comparable 接口允许边根据权重进行排序，这在很多图算法中非常重要，特别是那些需要考虑边权重的算法，如最小生成树或最短路径算法。通过方法 either() 和 other()，可以方便地在图的上下文中使用边，而 toString() 方法则提供了边的直观表达，便于输出和调试。

myEdgeWeightedGraph

java">import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myEdgeWeightedGraph
{private int V;private int E;private myBag<myEdge>[] adj;private static final String NEWLINE = System.getProperty("line.separator");public myEdgeWeightedGraph(int V){this.V = V;this.E = E;adj = (myBag<myEdge>[]) new myBag[V];for(int v=0;v<V;v++)adj[v]=new myBag<myEdge>();}public myEdgeWeightedGraph(In in){this(in.readInt());int E = in.readInt();for (int i = 0; i < E; i++){int v = in.readInt();int w = in.readInt();double weight = in.readDouble();myEdge e = new myEdge(v,w,weight);addEdge(e);}}public int V() {return V;}public int E() {return E;}public void addEdge(myEdge e){int v = e.either(),w=e.other(v);adj[v].add(e);adj[w].add(e);E++;}public Iterable<myEdge> adj(int v){return adj[v];}public Iterable<myEdge> edges(){myBag<myEdge> b = new myBag<myEdge>();for(int v=0;v<V;v++)for(myEdge e: adj[v])if(e.other(v)<v) b.add(e);return b;}public String toString(){StringBuilder s = new StringBuilder();s.append(V +" vertexes "+ E + " edges " + NEWLINE);for(int v = 0; v<V; v++) {s.append(v + ": ");for(myEdge e:adj(v))s.append(e + "  ");s.append(NEWLINE);}return s.toString();}public static void main(String[] args){In in = new In(args[0]);myEdgeWeightedGraph G = new myEdgeWeightedGraph(in);StdOut.print(G);}
}

这段代码定义了一个表示加权无向图的类 myEdgeWeightedGraph。这里的每个重要组成部分我将逐一说明：

构造函数：
- 第一个构造函数接受一个顶点数 V，初始化图，为每个顶点创建一个用于存储边的链表。
- 第二个构造函数通过读取一个输入源来构建图。它首先读取顶点数和边数，然后连续读取每条边的两个顶点和权重，并将这些边添加到图中。
边的添加：
- addEdge 方法用于向图中添加一条边，同时将边添加到两个顶点的邻接链表中。
图的信息获取：
- V() 和 E() 方法分别返回图的顶点数和边数。
- adj(int v) 方法返回与顶点 v 相连的所有边。
- edges() 方法返回图中的所有边，确保每条边只被列出一次。
图的字符串表示：
- toString 方法生成并返回图的字符串描述，包括每个顶点及其相邻的边。
主函数：
- main 方法从文件读取图数据，构建图对象，并打印图的字符串表示。

实验

代码编译

$ javac myEdge.java
$ javac myEdgeWeightedGraph.java

代码运行

$ java myEdgeWeightedGraph ..\data\tinyEWG.txt
8 vertexes 16 edges 
0: 6-0 0.58  0-2 0.26  0-4 0.38  0-7 0.16
1: 1-3 0.29  1-2 0.36  1-7 0.19  1-5 0.32
2: 6-2 0.40  2-7 0.34  1-2 0.36  0-2 0.26  2-3 0.17
3: 3-6 0.52  1-3 0.29  2-3 0.17
4: 6-4 0.93  0-4 0.38  4-7 0.37  4-5 0.35
5: 1-5 0.32  5-7 0.28  4-5 0.35
6: 6-4 0.93  6-0 0.58  3-6 0.52  6-2 0.40
7: 2-7 0.34  1-7 0.19  0-7 0.16  5-7 0.28  4-7 0.37