有权图的表示和存储

有权图的表示和存储

带权图的存储于无全图的存储差别在于边上,这里将边作为一个类存储。
Edge类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package MinimumSpanTrees;

/**
* @ Description: 图的边 类
* @ Date: Created in 07:47 2018/8/2
* @ Author: Anthony_Duan
*/
public class Edge<Weight extends Number & Comparable> implements Comparable<Edge<Weight>> {
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 "" + a + "-" + b + ":" + weight;
}

@Override
public int compareTo(Edge that) {
if (weight.compareTo(that.wt()) < 0) {
return -1;
} else if (weight.compareTo(that.wt()) > 0) {
return +1;
} else {
return 0;
}
}
}

DenseWeightedGraph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package MinimumSpanTrees;

import java.util.Vector;

/**
* @ Description: 用邻接矩阵表示带权稠密图
* @ Date: Created in 11:35 2018/8/1
* @ Author: Anthony_Duan
*/
public class DenseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph {
//节点数
private int n;

//边数
private int m;
//是否为有向图
private boolean directed;

//图的具体数据
private Edge<Weight>[][] g;


/**
* 构造函数
* @param n
* @param directed
*/
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为Boolean型的变量的默认值
g = new Edge[n][n];
for(int i = 0 ; i < n ; i ++) {
for(int j = 0 ; j < n ; j ++) {
g[i][j] = null;
}
}
}

//返回节点个数
@Override
public int V(){
return n;
}

//返回边的个数
@Override
public int E(){
return m;
}


/**
* 向图中添加一个边
* @param e
*/
@Override
public void addEdge(Edge e) {
assert e.v() >= 0 && e.v() < n;
assert e.w() >= 0 && e.w() < n;

if (hasEdge(e.v(), e.w())) {
return;
}

g[e.v()][e.w()] = new Edge(e);
if (e.v() != e.w() && !directed) {
g[e.w()][e.v()] = new Edge(e.w(), e.v(), e.wt());
}
m++;
}


/**
* 验证图中是否有从v到w的边
* @param v
* @param w
* @return
*/
@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不会带来额外开销
* @param v
* @return
*/
@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;
}
}

SparseWeightedGraph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package MinimumSpanTrees;

import java.util.Vector;

/**
* @ Description: 用邻接表表示稀疏图
* @ Date: Created in 11:35 2018/8/1
* @ Author: Anthony_Duan
*/
public class SparseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph {
//节点数
private int n;
//边数
private int m;
//是否为有向图
private boolean directed;
//图的具体数据
private Vector<Edge<Weight>>[] g;

public SparseWeightedGraph(int n, boolean directed) {
assert n >= 0;
this.n = n;
//初始化没有任何边
this.m = m;
this.directed = directed;

//g初始化为n个空vector 表示每一个g[i]都表示为空,即没有任何边
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;
}


/**
* 向图中添加一个边
* 这里并没有处理平行边的情况
* 因为邻接表如果要考虑没有平行边,每次添加边都需要遍历一次g[v]
* 效率太低,所以一般是先添加,最后一次性处理,
* 这里就暂时允许有平行边
* @param v
* @param w
*/
@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++;
}


/**
* 显示图的信息
*/
@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();
}
}


/**
* 验证图中是否有从v到w的边
* @param v
* @param w
* @return
*/
@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;
}


/**
* 返回图中一个顶点的所有邻边
* 由于java使用引用机制所以返回一个Vector不会带来额外开销
* @param v
* @return
*/
@Override
public Iterable<Edge<Weight>> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}

-------------End Of This ArticleThank You For Reading-------------