定向加权图的邻接表
我使用邻接列表来表示有向加权图,并根据此 SO问题提供的示例代码,我创建了以下内容:
import java.util.HashMap; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.Map; import java.util.Set; public class _Graph { private Map<String, LinkedHashSet<HashMap>> map = new HashMap<String, LinkedHashSet<HashMap>>(); public void addEdge(String node1, String node2, int dist) { LinkedHashSet<HashMap> adjacent = map.get(node1); HashMap innerMap = new HashMap(); if(adjacent==null) { adjacent = new LinkedHashSet<HashMap>(); map.put(node1, adjacent); } innerMap.put(node2, dist); adjacent.add(innerMap); } public boolean isConnected(String node1, String node2) { Set<HashMap> adjacent = map.get(node1); if(adjacent==null) { return false; } return adjacent.contains(node2); } public LinkedList<HashMap> adjacentNodes(String node) { LinkedHashSet<HashMap> adjacent = map.get(node); if(adjacent==null) { return new LinkedList<HashMap>(); } return new LinkedList<HashMap>(adjacent); } }
我无法使isConnected
方法正常工作。 我在这里使用错误的数据结构来表示图形( Map<String, LinkedHashSet<HashMap>>
)? hashmap将保存连接节点的名称及其距离:
Map<startNode, LinkedHashSet<HashMap>>
- 基本上我如何检查节点是否属于给定基节点的邻接列表? 我认为问题被简化为在
adjacent
Set<HashMap>
结构上正确迭代,或者我的推理是错误的? - 在我的第二个方法
adjacentNodes(String node)
我返回一个链表,其中包含连接节点的映射(以集合结构)及其距离。 我怎样才能有效地迭代以查看任何给定节点的所有连接?
我认为这里不需要LinkedHashSet
,你可以用Map
表示图形。
isConnected
基本上就是你已有的:
public boolean isConnected(String node1, String node2) { Map adjacent = map.get(node1); if(adjacent==null) { return false; } return adjacent.containsKey(node2); }
adjacentNodes
只需要拉出源节点的哈希集中的条目
public Collection> adjacentNodes(String node) { Map adjacent = map.get(node); if(adjacent==null) { return new ArrayList>(); } return adjacent.entrySet(); }
- Apache Kafka和Avro:org.apache.avro.generic.GenericData $ Record无法强制转换为com.harmeetsingh13.java.Customer
- 如何使用libgdx获取手机语言?