java - Java中的加权图实现
问题描述
我刚开始学习算法和数据结构课程。几个小时以来,我一直在尝试实现加权图,但我无法为边添加权重。你会建议我做什么?
这是我的代码:
public class Graph {
int numberOfNodes = 0;
Hashtable<Integer, ArrayList<Integer>> adjacentList = new Hashtable<>();
public void addNode(int node) {
adjacentList.put(node, new ArrayList<>());
numberOfNodes++;
}
public void addEdge(int node1, int node2) {
adjacentList.get(node1).add(node2);
adjacentList.get(node2).add(node1);
}
public void showConnections() {
Object[] keys = adjacentList.keySet().toArray();
for (Object key : keys) {
System.out.println(key + " ---> " + adjacentList.get(Integer.parseInt(key.toString())));
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addNode(5);
graph.addNode(54);
graph.addNode(44);
graph.addEdge(5,54);
graph.addEdge(5,44);
graph.showConnections();
}
}
解决方案
public final class Graph {
private final Map<Integer, Set<Integer>> adjacentList = new HashMap<>();
private final Map<Integer, Map<Integer, Double>> weights = new HashMap<>();
public void addNode(int node) {
adjacentList.computeIfAbsent(node, key -> new TreeSet<>());
}
public void addEdge(int one, int two, double weight) {
addDirectedEdge(one, two, weight);
addDirectedEdge(two, one, weight);
}
private void addDirectedEdge(int one, int two, double weight) {
addNode(one);
addNode(two);
adjacentList.get(one).add(two);
setWeight(one, two, weight);
}
private void setWeight(int one, int two, double weight) {
weights.computeIfAbsent(one, key -> new HashMap<>());
weights.get(one).put(two, weight);
}
public void showConnections() {
for (Map.Entry<Integer, Set<Integer>> entry : adjacentList.entrySet()) {
int one = entry.getKey();
System.out.print(entry.getKey() + " ---> [");
boolean comma = false;
for (int two : entry.getValue()) {
if (comma)
System.out.print(", ");
comma = true;
double weight = weights.get(one).get(two);
System.out.format(Locale.ENGLISH, "%d (weight: %.2f)", two, weight);
}
System.out.println(']');
}
}
public static void main(String... args) {
Graph graph = new Graph();
graph.addNode(5);
graph.addNode(54);
graph.addNode(44);
graph.addEdge(5, 54, 1.1);
graph.addEdge(5, 44, 2.2);
graph.showConnections();
}
}
输出:
5 ---> [44 (weight: 2.20), 54 (weight: 1.10)]
54 ---> [5 (weight: 1.10)]
44 ---> [5 (weight: 2.20)]
推荐阅读
- python - 从 **kwargs 实例化多个对象的 Pythonic 方法是什么?
- rabbitmq - 没有消费者的公共交通检查发布的消息
- spring - 带有枚举的 QuerySyntaxException
- mysql - 如何使用开源 kafka connect 从 Aurora 连接 MSK
- objective-c - 带有自定义 UI 的 UIActivityViewController
- jsx - 有没有AE脚本api可以把音视频图层文件的一部分放到指定的入点和出点?
- spring-mvc - Spring MVC 不允许特定控制器/控制器方法的字段
- c++ - 类字符串类型的 C++ 迭代器
- r - 从函数调用返回一个包含各种元素的命名列表
- xml - 将 xml 请求转换为具有嵌套标签的 java pojo 类