问题描述
早上好/下午/晚上.
因此，我们的数据结构课程为我们分配了使用以下算法在Java中分割灰度图像的任务:
So our data structures course gave us an assignment to segment a grayscale image in java using the following algorithm:
问题是，他们只是把我们扔在了黑暗中.他们给了我们一个jgraph软件包，我们完全没有经验(从未研究过)，实际上说去教自己".那里没有新东西.
The thing is, they just threw us in the dark. They gave us the jgraph package which we had absolutely no experience with (we never studied it) practically saying "go teach yourselves". Nothing new there.
我要这样做的方法是为顶点对象创建一个类，该类除了包含像素的值外还包含像素的坐标，以便可以将每个像素都添加到图形和2D数组中.之后，我使用该数组在相邻顶点之间添加了加权边，因为java无法确定顶点在图中的何处实际上没有边.
The way I'm going about doing this is by making a class for vertix objects that contains the coordinates of the pixel in addition to its value so that I can add each one both to the graph and a 2D array. Afterwards, I used the array to add weighted edges between adjacent vertices because java can't tell where in the graph a vertix actually is without edges.
然后，我使用Kruskal的打包方法来生成最小的生成树，并使用arraylist来绕开树中边缘权重的受保护状态，如下所示:
Afterwards, I used Kruskal's packaged method for minimum spanning trees and an arraylist to get around the protected status of edge weights in the tree like so:
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)边，我应该留下一片森林.那就是我碰到另一个死胡同的地方.如何获得遍历每棵树的程序?以我的理解方式，我需要一种通用的遍历算法来访问每棵树并将平均值分配给每个顶点.问题?程序包中没有通用的遍历算法.而且也没有一种方法可以识别单个树.
So now that I cut the (R-1) most costly edges in the graph, I should be left with a forest. And that's where I hit another dead end. How do I get the program to traverse each tree? The way I'm understanding this, I need a general traversal algorithm to visit every tree and assign the average value to each vertix. The problem? There isn't a general traversal algorithm in the package. And there isn't a way to identify individual trees either.
这个想法很容易理解，并且可以在纸上实现.问题仅在于实际上在Java中对所有这些进行编码.
The idea is easy to understand and implement on paper, really. The problems only lie in actually coding all of this in java.
很抱歉，如果它太乱或太长，但我只是出于机智和身体上的限制.预先谢谢你.
Sorry if this was messy or too long, but I'm just at my wit's end and physical limits. Thank you in advance.
推荐答案
我是 JGraphT 的忠实粉丝老实说，我认为为您分配任务是一件非常不错的事情.开始需要花费一些时间，但是事实证明，它是一个非常好的工具.但是，您还需要使用JGraphT了解实现的算法背后的CS，而又不知道该理论有些困难.
I am a big fan of JGraphT and honestly I think it is pretty good that you're given it for your task assignment. It takes a bit of time to get started, but then it proves to be a very good tool. But you also need to understand the CS behind implemented algorithms, using JGraphT without knowing the theory is somewhat difficult.
从您的任务分配中，我不太了解步骤1(构建原始加权图).其余的应该可以与JGraphT一起很好地工作.
From your task assignment I don't really understand step 1 (building the primal weighted graph). The rest should work with JGraphT quite well.
您使用KruskalMinimumSpanningTree完成了第2步.现在，您可以按重量对边缘进行排序，并从图中删除R-1个顶部边缘.
You did step 2 with KruskalMinimumSpanningTree. Now you can sort the edges by weight and remove R-1 top edges from the graph.
但是，我建议您首先构建一个新图，该图将代表计算出的MST.然后从该图中删除删除R-1顶部边缘.有效地将其扎入森林.
I would, however, suggest that you first build a new graph which would represent the calculated MST. And then remove remove R-1 top edges from that graph. Effectively truning it into a forest.
使用上一步中的目录林，您可以使用ConnectivityInspector获取一组连接的顶点列表.每组将包含来自森林中一棵树的顶点.顶点集易于使用，您不需要任何遍历，只需遍历顶点集即可.
With the forest from the previous step you can use the ConnectivityInspector to get a list of sets of connected vertices. Each set will contain vertices from one of the trees of the forest. Sets of vertices are easy to work with, you don't need any traversal, just iterate over the set.
这篇关于Jgraph:一般遍历森林穿越的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！