3

隣接リストを使用して有向加重グラフを表し、この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<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);
    }

}

isConnectedメソッドを正しく機能させるのに問題があります。ここでグラフを表すために間違ったデータ構造を使用していますか（Map<String, LinkedHashSet<HashMap<String, Integer>>>）？ハッシュマップは、接続されたノードの名前とノードまでの距離を保持します。

Map<startNode, LinkedHashSet<HashMap<endNode, distanceToEndNode>>>
  1. 基本的に、ノードが特定のベースノードの隣接リストに属しているかどうかを確認するにはどうすればよいですか？問題は構造を適切に反復することに帰着すると思いますかadjacent Set<HashMap<String, Integer>> 、それとも私の推論は間違っていますか？
  2. 2番目の方法 adjacentNodes(String node)では、接続されたノードとその距離のマップ（セット構造）を含むリンクリストを返します。特定のノードのすべての接続を効率的に反復処理するにはどうすればよいですか？
4

1 に答える 1

5

ここでは必要ないと思います。LinkedHashSetグラフは。だけで表すことができますMap<String, Map<String, Integer>>。

isConnected基本的にあなたがすでに持っているものです：

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

adjacentNodesソースノードのハッシュセットのエントリを引き出す必要があります

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();
}
于 2010-01-02T01:34:58.690 に答える