有權(quán)圖
一举瑰、有權(quán)圖的表示
有權(quán)圖.png
1). 稠密圖的實(shí)現(xiàn)表示
有權(quán)圖鄰接矩陣.png
鄰接矩陣中存對應(yīng)的權(quán)值
2). 稀疏圖的實(shí)現(xiàn)表示
有權(quán)圖鄰接表.png
鄰接表中要存對應(yīng)邊(或者說索引)以及對應(yīng)的權(quán)值
二、代碼實(shí)現(xiàn)
1). 核心實(shí)現(xiàn)
- 圖接口
/**
* 圖的接口
* @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);
}
- “邊”對象實(shí)現(xiàn)
/**
* 有權(quán)圖中的邊
* @author Liucheng
* @since 2019-10-15
* Weight extends Number & Comparable 寫法有點(diǎn)懵逼换况，但是我知道Weight必須得實(shí)現(xiàn)其中的抽象方法！
*/
public class Edge<Weight extends Number & Comparable> implements Comparable<Edge>{
private int a, b; // 邊的兩個(gè)端點(diǎn)
private Weight weight; // 邊的權(quán)值泛型
/**
* 構(gòu)造方法
*/
public Edge(int a, int b, Weight weight) {
this.a = a;
this.b = b;
this.weight = weight;
}
/**
* 重載的構(gòu)造方法
*/
public Edge(Edge<Weight> e) {
this.a = e.a; // 在同一個(gè)類中(而不是一個(gè)對象盗蟆！)戈二，可以訪問私有屬性！
this.b = e.b;
this.weight = e.weight;
}
public int v() {return a;} // 返回一個(gè)頂點(diǎn)
public int w() {return b;} // 返回第二個(gè)頂點(diǎn)
public Weight wt() {return weight;} // 返回權(quán)值
/**
* 給定一個(gè)頂點(diǎn)喳资，返回另一個(gè)頂點(diǎn)
*/
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;
/**
* 稠密圖 - 有權(quán)圖 - 鄰接矩陣;
* 不考慮自環(huán)邊觉吭、平行邊和刪除節(jié)點(diǎn)
* @author Liucheng
* @since 2019-10-09
*/
public class DenseWeightedGraph<Weight extends Number & Comparable>
implements WeightedGraph {
/**
* 圖的節(jié)點(diǎn)數(shù)
*/
private int n;
/**
* 圖的邊數(shù)
*/
private int m;
/**
* 是否為有向圖，true有向圖仆邓，false無向圖
*/
private boolean directed;
/**
* 圖的具體數(shù)據(jù)
*/
private Edge<Weight>[][] g;
/**
* 構(gòu)造函數(shù)
*/
public DenseWeightedGraph(int n, boolean directed) {
assert n >= 0;
this.n = n;
// 初始化時(shí)沒有任何邊
this.m = 0;
this.directed = directed;
/*
* g的初始化為n*n的布爾矩陣鲜滩，每一個(gè)g[i][j]均為false,表示沒有任何邊
* false為布爾類型變量的默認(rèn)值 */
this.g = new Edge[n][n];
}
/**
* 返回節(jié)點(diǎn)個(gè)數(shù)
*/
@Override
public int V() {return n;}
/**
* 返回邊的個(gè)數(shù)
*/
@Override
public int E() {return m;}
/**
* 向圖中添加一個(gè)連接伴鳖，也就是一條邊
*/
@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++;
}
/**
* 驗(yàn)證圖中是否有從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();
}
}
/**
* 返回圖中一個(gè)頂點(diǎn)的所有鄰邊，
* 由于java使用引用機(jī)制绒北，返回一個(gè)Vector不會(huì)帶來額外的開銷
* 可以使用java變準(zhǔn)庫中提供的迭代器
*/
@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;
/**
* 稀疏圖 - 鄰接表：
* 不考慮自環(huán)邊黎侈、平行邊和刪除節(jié)點(diǎn)情況
* @author Liucheng
* @since 2019-10-09
*/
public class SparseWeightedGraph<Weight extends Number & Comparable>
implements WeightedGraph {
/**
* 圖的節(jié)點(diǎn)數(shù)
*/
private int n;
/**
* 圖的邊數(shù)
*/
private int m;
/**
* 是否為有向圖,true表示有向圖；false表示無向圖
*/
private boolean directed;
/**
* 具體的圖數(shù)據(jù)
* 鄰接矩陣 true代表有邊闷游，false代表沒有邊
*/
Vector<Edge<Weight>>[] g;
/**
* 構(gòu)造函數(shù)
*/
public SparseWeightedGraph(int n, boolean directed) {
assert n >= 0;
this.n = n;
// 初始化時(shí)沒有任何邊
this.m = 0;
this.directed = directed;
/* g初始化為n個(gè)空的vector,
* 表示每一個(gè)g[i]都為空峻汉，即沒有任何邊*/
this.g = (Vector<Edge<Weight>>[])new Vector[n];
for (int i = 0; i < n; i++) {
g[i] = new Vector<Edge<Weight>>();
}
}
/**
* 返回節(jié)點(diǎn)的個(gè)數(shù)
*/
@Override
public int V() {return n;}
/**
* 返回邊的個(gè)數(shù)
*/
@Override
public int E() {return m;}
/**
* 向圖中添加一個(gè)邊,權(quán)值為weight
*/
@Override
public void addEdge(Edge e) {
assert e.v() >= 0 && e.v() < n ;
assert e.w() >= 0 && e.w() < n ;
// 注意, 由于在鄰接表的情況, 查找是否有重邊需要遍歷整個(gè)鏈表
// 我們的程序允許重邊的出現(xià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 ++;
}
/**
* 驗(yàn)證圖中是否有從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();
}
}
/**
* 返回圖中一個(gè)頂點(diǎn)的所有鄰邊
*/
@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;
/**
* 由于文件格式的限制，我們的文件讀取類只能讀取權(quán)值為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
- 執(zhí)行結(jié)果
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
