java - j图 : General Traversal & Forest Traversal

Question

早上好/下午好/晚上好。

因此，我们的数据结构类(class)给了我们一个作业，使用以下算法在 java 中分割灰度图像:

Input: A gray-scale image with P pixels and number R
Output: An image segmented into R regions
1. Map the image onto a primal weighted graph.
2. Find an MST of the graph.
3. Cut the MST at the R – 1 most costly edges.
4. Assign the average tree vertex weight to each vertex in each tree in the forest
5. Map the partition onto a segmentation image

问题是，他们只是把我们蒙在鼓里。他们给了我们 jgraph 包，我们完全没有经验(我们从未研究过它)，实际上是在说“去自学”。没有什么新东西。

我要做的方法是为顶点对象创建一个类，其中除了像素值之外还包含像素的坐标，以便我可以将每个顶点添加到图形和二维数组中。之后，我使用数组在相邻顶点之间添加加权边，因为 java 无法分辨图中顶点实际上没有边的位置。

之后，我使用 Kruskal 的最小生成树封装方法和数组列表来绕过树中边权重的 protected 状态，如下所示:

ArrayList<WeightedEdge> edgeList = new ArrayList<>(height*width*3);
KruskalMinimumSpanningTree mst4 = new KruskalMinimumSpanningTree(map4);
Set<DefaultWeightedEdge> edges = mst4.getSpanningTree().getEdges();
for (DefaultWeightedEdge edge : edges) {
    edgeList.add(new WeightedEdge(edge, map4.getEdgeWeight(edge)));
}
edgeList.sort(null);

for (int i = 0; i < n; i++) {
    map4.removeEdge(edgeList.get(edgeList.size()-1).getEdge());
}  

现在我砍掉了图中成本最高的 (R-1) 条边，我应该留下一片森林。这就是我遇到另一个死胡同的地方。如何让程序遍历每棵树？按照我的理解，我需要一个通用的遍历算法来访问每棵树并将平均值分配给每个顶点。问题？包中没有通用的遍历算法。而且也没有办法识别单个树木。

这个想法确实很容易理解并在纸上实现。问题仅在于实际上用 java 编写了所有这些内容。

很抱歉，如果这很困惑或太长，但我正处于我的智力极限和 body 极限。预先感谢您。

Answer 1

我是JGraphT的忠实粉丝老实说，我认为为您的任务分配提供它非常好。上手需要一些时间，但后来证明它是一个非常好的工具。但你还需要了解实现算法背后的CS，在不了解理论的情况下使用JGraphT有些困难。

根据您的任务分配，我不太理解步骤 1(构建原始加权图)。其余的应该可以很好地与 JGraphT 配合使用。

您使用 KruskalMinimumSpanningTree 完成了第 2 步。现在，您可以按权重对边进行排序，并从图表中删除 R-1 顶部边。

但是，我建议您首先构建一个新图表来表示计算出的 MST。然后从该图中删除 R-1 顶部边缘。有效地将其变成森林。

How do I get the program to traverse each tree?

对于上一步中的森林，您可以使用 ConnectivityInspector 获取连接顶点集的列表。每组都包含森林中一棵树的顶点。顶点集很容易使用，您不需要任何遍历，只需迭代集合即可。