有权图
一、有权图的表示
有权图.png
1). 稠密图的实现表示
有权图邻接矩阵.png
邻接矩阵中存对应的权值
2). 稀疏图的实现表示
有权图邻接表.png
邻接表中要存对应边(或者说索引)以及对应的权值
二、代码实现
1). 核心实现
- 图接口
/**
* 图的接口
* @author Liucheng
* @date 2019/10/13 15:48
*/
public interface WeightedGraph<Weight extends Number & Comparable> {
public int V();
public int E();
public void addEdge(Edge<Weight> e);
boolean hasEdge( int v , int w );
void show();
public Iterable<Edge<Weight>> adj(int v);
}
- “边”对象实现
/**
* 有权图中的边
* @author Liucheng
* @since 2019-10-15
* Weight extends Number & Comparable 写法有点懵逼，但是我知道Weight必须得实现其中的抽象方法！
*/
public class Edge<Weight extends Number & Comparable> implements Comparable<Edge>{
private int a, b; // 边的两个端点
private Weight weight; // 边的权值泛型
/**
* 构造方法
*/
public Edge(int a, int b, Weight weight) {
this.a = a;
this.b = b;
this.weight = weight;
}
/**
* 重载的构造方法
*/
public Edge(Edge<Weight> e) {
this.a = e.a; // 在同一个类中(而不是一个对象！)，可以访问私有属性！
this.b = e.b;
this.weight = e.weight;
}
public int v() {return a;} // 返回一个顶点
public int w() {return b;} // 返回第二个顶点
public Weight wt() {return weight;} // 返回权值
/**
* 给定一个顶点，返回另一个顶点
*/
public int other(int x) {
assert x == a || x == b;
return x == a ? b : a;
}
/**
* 输出边的信息
*/
@Override
public String toString() {
return String.valueOf(a) + "-" + b + ": " + this.weight;
}
/**
* 边之间的比较
*/
@Override
public int compareTo(Edge that) {
if (this.weight.compareTo(that.wt()) < 0) {
return -1;
} else if (this.weight.compareTo(that.wt()) > 0) {
return 1;
}
return 0;
}
}
- 稠密图
import java.util.Vector;
/**
* 稠密图 - 有权图 - 邻接矩阵;
* 不考虑自环边、平行边和删除节点
* @author Liucheng
* @since 2019-10-09
*/
public class DenseWeightedGraph<Weight extends Number & Comparable>
implements WeightedGraph {
/**
* 图的节点数
*/
private int n;
/**
* 图的边数
*/
private int m;
/**
* 是否为有向图，true有向图，false无向图
*/
private boolean directed;
/**
* 图的具体数据
*/
private Edge<Weight>[][] g;
/**
* 构造函数
*/
public DenseWeightedGraph(int n, boolean directed) {
assert n >= 0;
this.n = n;
// 初始化时没有任何边
this.m = 0;
this.directed = directed;
/*
* g的初始化为n*n的布尔矩阵，每一个g[i][j]均为false,表示没有任何边
* false为布尔类型变量的默认值 */
this.g = new Edge[n][n];
}
/**
* 返回节点个数
*/
@Override
public int V() {return n;}
/**
* 返回边的个数
*/
@Override
public int E() {return m;}
/**
* 向图中添加一个连接，也就是一条边
*/
@Override
public void addEdge(Edge e) {
if (this.hasEdge(e.v(), e.w())) {
return;
}
g[e.v()][e.w()] = new Edge(e);
if (e.v() != e.w() && !this.directed) {
g[e.w()][e.v()] = new Edge(e.w(), e.v(), e.wt());
}
m++;
}
/**
* 验证图中是否有从v到w的边
*/
@Override
public boolean hasEdge(int v, int w) {
// 不能越界
assert (v >= 0 && v < n);
assert (w >= 0 && w < n);
return g[v][w] != null;
}
/**
* 显示图的信息
*/
@Override
public void show() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != null) {
System.out.print(g[i][j].wt() + "\t");
} else {
System.out.print("NULL\t");
}
}
System.out.println();
}
}
/**
* 返回图中一个顶点的所有邻边，
* 由于java使用引用机制，返回一个Vector不会带来额外的开销
* 可以使用java变准库中提供的迭代器
*/
@Override
public Iterable<Edge<Weight>> adj(int v) {
assert v >= 0 && v < n;
Vector<Edge<Weight>> adjV = new Vector<>();
for (int i = 0; i < n; i++) {
if (g[v][i] != null) {
adjV.add(g[v][i]);
}
}
return adjV;
}
}
- 稀疏图
import java.util.Vector;
/**
* 稀疏图 - 邻接表：
* 不考虑自环边、平行边和删除节点情况
* @author Liucheng
* @since 2019-10-09
*/
public class SparseWeightedGraph<Weight extends Number & Comparable>
implements WeightedGraph {
/**
* 图的节点数
*/
private int n;
/**
* 图的边数
*/
private int m;
/**
* 是否为有向图,true表示有向图；false表示无向图
*/
private boolean directed;
/**
* 具体的图数据
* 邻接矩阵 true代表有边，false代表没有边
*/
Vector<Edge<Weight>>[] g;
/**
* 构造函数
*/
public SparseWeightedGraph(int n, boolean directed) {
assert n >= 0;
this.n = n;
// 初始化时没有任何边
this.m = 0;
this.directed = directed;
/* g初始化为n个空的vector,
* 表示每一个g[i]都为空，即没有任何边*/
this.g = (Vector<Edge<Weight>>[])new Vector[n];
for (int i = 0; i < n; i++) {
g[i] = new Vector<Edge<Weight>>();
}
}
/**
* 返回节点的个数
*/
@Override
public int V() {return n;}
/**
* 返回边的个数
*/
@Override
public int E() {return m;}
/**
* 向图中添加一个边,权值为weight
*/
@Override
public void addEdge(Edge e) {
assert e.v() >= 0 && e.v() < n ;
assert e.w() >= 0 && e.w() < n ;
// 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表
// 我们的程序允许重边的出现
g[e.v()].add(new Edge(e));
if (e.v() != e.w() && !directed) {
g[e.w()].add(new Edge(e.w(), e.v(), e.wt()));
}
m ++;
}
/**
* 验证图中是否有从v到w的边
*/
@Override
public boolean hasEdge(int v, int w) {
assert (v >= 0 && v < n);
assert (w >= 0 && w < n);
for (int i = 0; i < g[v].size(); i++) {
if(g[v].elementAt(i).other(v) == w) {
return true;
}
}
return false;
}
@Override
public void show() {
for( int i = 0 ; i < n ; i ++ ){
System.out.print("vertex " + i + ":\t");
for( int j = 0 ; j < g[i].size() ; j ++ ){
Edge e = g[i].elementAt(j);
System.out.print( "( to:" + e.other(i) + ",wt:" + e.wt() + ")\t");
}
System.out.println();
}
}
/**
* 返回图中一个顶点的所有邻边
*/
@Override
public Iterable<Edge<Weight>> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}
2). 测试
- 测试代码
/**
* @author Liucheng
* @since 2019-10-13
*/
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.util.Locale;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
/**
* 通过文件读取有全图的信息
*/
public class ReadWeightedGraph{
private Scanner scanner;
/**
* 由于文件格式的限制，我们的文件读取类只能读取权值为Double类型的图
*/
public ReadWeightedGraph(WeightedGraph<Double> graph, String filename){
readFile(filename);
try {
int V = scanner.nextInt();
if (V < 0) {
throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative");
}
assert V == graph.V();
int E = scanner.nextInt();
if (E < 0) {
throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");
}
for (int i = 0; i < E; i++) {
int v = scanner.nextInt();
int w = scanner.nextInt();
Double weight = scanner.nextDouble();
assert v >= 0 && v < V;
assert w >= 0 && w < V;
graph.addEdge(new Edge<Double>(v, w, weight));
}
}
catch (InputMismatchException e) {
String token = scanner.next();
throw new InputMismatchException("attempts to read an 'int' value from input stream, but the next token is \"" + token + "\"");
}
catch (NoSuchElementException e) {
throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available");
}
}
private void readFile(String filename){
assert filename != null;
try {
File file = new File(filename);
if (file.exists()) {
FileInputStream fis = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
scanner.useLocale(Locale.ENGLISH);
}
else {
throw new IllegalArgumentException(filename + " doesn't exist.");
}
}
catch (IOException ioe) {
throw new IllegalArgumentException("Could not open " + filename, ioe);
}
}
}
- maven工程resources下的测试文件testG1.txt
8 16
4 5 .35
4 7 .37
5 7 .28
0 7 .16
1 5 .32
0 4 .38
2 3 .17
1 7 .19
0 2 .26
1 2 .36
1 3 .29
2 7 .34
6 2 .40
3 6 .52
6 0 .58
6 4 .93
- 执行结果
test G1 in Sparse Weighted Graph:
vertex 0: ( to:7,wt:0.16) ( to:4,wt:0.38) ( to:2,wt:0.26) ( to:6,wt:0.58)
vertex 1: ( to:5,wt:0.32) ( to:7,wt:0.19) ( to:2,wt:0.36) ( to:3,wt:0.29)
vertex 2: ( to:3,wt:0.17) ( to:0,wt:0.26) ( to:1,wt:0.36) ( to:7,wt:0.34) ( to:6,wt:0.4)
vertex 3: ( to:2,wt:0.17) ( to:1,wt:0.29) ( to:6,wt:0.52)
vertex 4: ( to:5,wt:0.35) ( to:7,wt:0.37) ( to:0,wt:0.38) ( to:6,wt:0.93)
vertex 5: ( to:4,wt:0.35) ( to:7,wt:0.28) ( to:1,wt:0.32)
vertex 6: ( to:2,wt:0.4) ( to:3,wt:0.52) ( to:0,wt:0.58) ( to:4,wt:0.93)
vertex 7: ( to:4,wt:0.37) ( to:5,wt:0.28) ( to:0,wt:0.16) ( to:1,wt:0.19) ( to:2,wt:0.34)
~~~
test G1 in Dense Graph:
NULL NULL 0.26 NULL 0.38 NULL 0.58 0.16
NULL NULL 0.36 0.29 NULL 0.32 NULL 0.19
0.26 0.36 NULL 0.17 NULL NULL 0.4 0.34
NULL 0.29 0.17 NULL NULL NULL 0.52 NULL
0.38 NULL NULL NULL NULL 0.35 0.93 0.37
NULL 0.32 NULL NULL 0.35 NULL NULL 0.28
0.58 NULL 0.4 0.52 0.93 NULL NULL NULL
0.16 0.19 0.34 NULL 0.37 0.28 NULL NULL
