Content Table

图-创建图

为了方便创建图,可以把图的边按照格式 startVertex1-endVertex1:weight1,startVertex2-endVertex2:weight2 保存为一个字符串,例如 A-B:16,B-C:10,C-D:3,D-E:4,E-F:8,F-A:14,B-G:7,C-G:6,E-G:2,F-G:9,A-G:12,C-E:5,解析字符串得到图的所有边,使用邻接表存储图的数据。

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
131
132
133
134
135
package graph;

import com.alibaba.fastjson.JSON;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;
import org.apache.commons.lang3.StringUtils;

import java.util.*;
import java.util.stream.Collectors;

/**
* 图
*/
@Getter
@Setter
@Accessors(chain = true)
public class Graph {
Map<String, List<Edge>> adjacentList = new HashMap<>(); // 邻接表存储图: key 为顶点,Edge 为此顶点和临接点构成的边

/**
* 获取图的顶点
*
* @return 返回顶点的集合
*/
public Set<String> getVertices() {
return adjacentList.keySet();
}

/**
* 获取图的边,无向图中 2 条相同的边只输出一条
*
* @return 返回边的集合
*/
public Set<Edge> getEdges() {
return adjacentList.values().stream().flatMap(List::stream).collect(Collectors.toSet());
}

/**
* 获取传入的顶点的所有边
*
* @param vertex 顶点
* @return 返回边的数组
*/
public List<Edge> getVertexEdges(String vertex) {
return adjacentList.get(vertex);
}

/**
* 使用图的边构建图,边的格式为 start-end:weight,边之间使用逗号分隔,例如 A-B:10,A-G:5
*
* @param edges 图的所有边
* @return 返回图的对象
*/
public static Graph build(String edges) {
Graph graph = new Graph();

for (String edgeContent : StringUtils.split(edges, ",")) {
// 边: A-B:10
int indexOfDash = edgeContent.indexOf("-");
int indexOfColon = edgeContent.indexOf(":");
String vertex1 = edgeContent.substring(0, indexOfDash);
String vertex2 = edgeContent.substring(indexOfDash+1, indexOfColon);
double weight = Double.parseDouble(edgeContent.substring(indexOfColon+1));

// 找到顶点 vertex1 的边集,添加它的边
graph.adjacentList.putIfAbsent(vertex1, new LinkedList<>());
graph.adjacentList.get(vertex1).add(new Edge(vertex1, vertex2, weight));

// 找到顶点 vertex2 的边集,添加它的边
graph.adjacentList.putIfAbsent(vertex2, new LinkedList<>());
graph.adjacentList.get(vertex2).add(new Edge(vertex2, vertex1, weight));
}

return graph;
}

/**
* 图的边,由起点、终点和权重构成
*/
@Getter
@Setter
@Accessors(chain = true)
public static class Edge {
String start; // 边的起点
String end; // 边的终点
double weight; // 边的权重

public Edge(String start, String end, double weight) {
this.start = start;
this.end = end;
this.weight = weight;
}

/**
* 2 个顶点相同的边则为同一条边
*/
@Override
public boolean equals(Object obj) {
if (obj.getClass() != getClass()) {
return false;
}

Edge other = (Edge) obj;

if (this.start.equals(other.start) && this.end.equals(other.end)) {
return true;
}

if (this.start.equals(other.end) && this.end.equals(other.start)) {
return true;
}

return false;
}

@Override
public int hashCode() {
// start, end 从小到大排序
if (start.compareTo(end) < 0) {
return Objects.hash(start, end);
} else {
return Objects.hash(end, start);
}
}
}

public static void main(String[] args) {
Graph graph = Graph.build("A-B:16,B-C:10,C-D:3,D-E:4,E-F:8,F-A:14,B-G:7,C-G:6,E-G:2,F-G:9,A-G:12,C-E:5");
System.out.println(JSON.toJSONString(graph.getAdjacentList()));
System.out.println(graph.getVertices());
System.out.println(JSON.toJSONString(graph.getEdges()));
System.out.println(JSON.toJSONString(graph.getVertexEdges("A"), true));
}
}

下面是顶点 A 的所有边:

1
2
3
4
5
6
7
8
9
10
11
12
13
[{
"end":"B",
"start":"A",
"weight":16.0
},{
"end":"F",
"start":"A",
"weight":14.0
},{
"end":"G",
"start":"A",
"weight":12.0
}]