有向加权图的邻接表 [英] adjacency list of a directed weighted graph

问题描述

我使用邻接表来表示有向加权图表，并基于这问题，我创建了以下：

I am using adjacency lists to represent a directed weighted graph and based on the example code provided by this SO question, I have created the following:

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<String, Integer>>> map = new HashMap<String, LinkedHashSet<HashMap<String, Integer>>>();

    public void addEdge(String node1, String node2, int dist) {
        LinkedHashSet<HashMap<String, Integer>> adjacent = map.get(node1);
        HashMap<String, Integer> innerMap = new HashMap<String, Integer>();
        if(adjacent==null) {
            adjacent = new LinkedHashSet<HashMap<String, Integer>>();                       
            map.put(node1, adjacent);
        }
        innerMap.put(node2, dist);
        adjacent.add(innerMap);
    }

    public boolean isConnected(String node1, String node2) {
        Set<HashMap<String, Integer>> adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<HashMap<String, Integer>> adjacentNodes(String node) {
        LinkedHashSet<HashMap<String, Integer>> adjacent = map.get(node);
        if(adjacent==null) {
            return new LinkedList<HashMap<String, Integer>>();
        }
        return new LinkedList<HashMap<String, Integer>>(adjacent);
    }

}

code> isConnected 方法正常工作。我使用错误的数据结构来表示这里的图形（ Map< String，LinkedHashSet< HashMap< String，Integer>> ）？ hashmap将保持连接的节点的名称和到它的距离：

I am having trouble making the isConnected method to work properly. Am I using a wrong data structure to represent the graph here (Map<String, LinkedHashSet<HashMap<String, Integer>>>)? The hashmap will hold the name of the connected node and the distance to it:

Map<startNode, LinkedHashSet<HashMap<endNode, distanceToEndNode>>>

1. 基本上如何检查节点
   是否属于给定基节点的
   的邻接表？我认为问题
   被减少到正确的迭代
   在相邻
Set< HashMap< String，Integer>


2. 在我的第二个方法
   adjacentNodes（String）节点）我是
   返回包含
   的链接列表
   连接节点的映射（在设置结构中）及其距离。如何有效地迭代查看任何给定节点的所有连接？

1. Basically how can I check if a node belongs to the adjacency list of a given base node? I think the problem is reduced to iterating properly over the adjacent Set<HashMap<String, Integer>> structure, or is my reasoning wrong?
2. In my second method adjacentNodes(String node) I am returning a linked list containing the maps (in a set structure) of the connected nodes and their distances. How could I efficiently iterate to see all connections of a any given node?

推荐答案

LinkedHashSet 在这里不需要，你可以用 Map< String，Map< String，Integer>< / $ c $

I think LinkedHashSet is not needed here, you can represent the graph with just a Map<String, Map<String, Integer>>.

isConnected 基本上是你已经有的：

isConnected is basically what you already have:

public boolean isConnected(String node1, String node2) {
    Map<String, Integer> adjacent = map.get(node1);
    if(adjacent==null) {
        return false;
    }
    return adjacent.containsKey(node2);
}

adjacentNodes 以拉出源节点的哈希集中的条目

adjacentNodes just needs to pull out the entries in the hash set for the source node

public Collection<Map.Entry<String, Integer>> adjacentNodes(String node) {
    Map<String, Integer> adjacent = map.get(node);
    if(adjacent==null) {
        return new ArrayList<Map.Entry<String, Integer>>();
    }
    return adjacent.entrySet();
}

这篇关于有向加权图的邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！