java - 图的连通度

Question

我正在尝试计算图中每个节点的度数。但是我遇到了麻烦，因为节点是节点类的一部分，我不知道如何将它们转换为 String。至少我认为这就是问题所在。这是我一直在尝试的，我有一个Hashset，其中存储节点，另一个存储边(无向图)，并且我需要获取一张表，其中包含所有存在的度数，然后是具有这些度数的节点:

public void DegreeList () {
    List<Nodes> listnodes = new ArrayList<Nodes>(Node);
    Map <Integer, List<Nodes>> DegreeList = new HashMap<Integer, List<Nodes>>();
    for (Nodes n: Node){
        int degree=0;
        for (Edges e: Edge){
            if (n.equals(e.start)||n.equals(e.end)){
                degree++;
                DegreeList.put(degree,n);
            }
        }
    }

}

Eclipse 的错误出现在最后一行，并显示:

The method put(Integer, List) in the type Map> is not applicable for the arguments (int, Nodes).

我愿意尝试其他方法。

编辑:节点和边是类。 Edge和Node是存储值的Hashsets。 (抱歉造成任何困惑)

Answer 1

工作假设

从您的代码来看，好像类型 Nodes代表单个节点，Node代表 Collection节点数。 (您的编辑证实了这一假设。)这些名称似乎是倒退的，但我将按照代码对它们的处理方式进行操作。如果我错了，请纠正我。

直接问题

这里有几个问题，但最直接的问题非常简单:你的Map需要 List<Nodes> 类型的值，但是您给它一个 Nodes 的单个实例。如果您可以更改您的Map到 Guava Multimap那么请这样做。否则，而不是

DegreeList.put(degree, n);

你需要类似的东西

List<Nodes> innerList = DegreeList.get(degree);
if (innerList == null) {
    innerList = new ArrayList<Nodes>();
    DegreeList.put(degree, innerList);
}
innerList.add(n);

这样就有一个List与每个degree相关联。您需要这个，因为 Map每个键只能存储一个值。如果您Map定义如下 Map<Integer, Nodes>那么你只能存储一个具有不同度数的节点。但这没有任何意义，不是吗？任意数量的节点可以共享相同的度数。所以你需要一个Map关联 Integer (代表学位)有Collection节点数。您似乎正在使用 List作为您的选择 Collection 。 Set可能会更好。

使用Set ，你可以定义你的 Map作为

Map<Integer, Set<Nodes>> degreeMap = new HashMap<>();

然后，当需要将一些内容放入 Map 时，你会这样做:

Set<Nodes> innerSet = degreeMap.get(degree);
if (innerSet == null) {
    innerSet = new HashSet<>();
    degreeMap.put(degree, innerSet);
}
innerSet.add(n);

无论哪种情况，您都不再需要 listNodes List .

其他观察结果

上面的代码描述了如何将一些内容放入 Map 中。但我们还需要考虑何时将某些内容放入 Map 中。现在您已将代码插入 Map每次有一条边与您正在评估的节点相匹配时:

for (Edges e: Edge){
    if (n.equals(e.start)||n.equals(e.end)){
        degree++;
        DegreeList.put(degree,n); // this shouldn't be here
    }
}
// instead, it belongs here

相反，您应该插入 Map每个节点仅一次，在确定节点的度数之后:

for (Edges e: Edge){
    if (n.equals(e.start)||n.equals(e.end)){
        degree++;
    }
}

// insert into Map here
Set<Nodes> innerSet = degreeMap.get(degree);
if (innerSet == null) {
    innerSet = new HashSet<>();
    degreeMap.put(degree, innerSet);
}
innerSet.add(n);