DFS图算法出现问题,发现错误的循环
我想创建一种算法,以了解具有相对点的图表中有多少个封闭区域,目前问题是它使用DFS算法找到了几乎所有循环。但是,出现问题
是我的实际代码,暂时完成了处理即时视频反馈的处理:
import java.util.Iterator;
import java.util.LinkedList;
class Graph {
int white = 0, gray = 1, black = 2;
ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
int V;
LinkedList<Integer>[] adj;
LinkedList<Integer>[] cycles;
LinkedList<PVector> points = new LinkedList<PVector>();
int num_cycles = 0;
Graph(int v) {
V = v;
adj = new LinkedList[V];
cycles = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList();
cycles[i] = new LinkedList();
}
}
void DFSCycleUtil(int source, int parent, int[] colors, int[] parents) {
if (colors[source] == gray) {
System.out.println("Cycle");
path.add(new ArrayList<Integer>());
int curr_parent = parent;
cycles[num_cycles].add(source);
System.out.println(source);
path.get(num_cycles).add(source);
while (curr_parent != source) {
cycles[num_cycles].add(curr_parent);
path.get(num_cycles).add(curr_parent);
System.out.println(curr_parent);
curr_parent = parents[curr_parent];
}
num_cycles++;
return;
} else if (colors[source] == black) {
return;
}
parents[source] = parent;
colors[source] = gray;
Iterator<Integer> i = adj[source].listIterator();
while (i.hasNext()) {
int n = i.next();
if (n != parent) {
DFSCycleUtil(n, source, colors, parents);
}
}
colors[source] = black;
}
void DFSCycle() {
int colors[] = new int[V];
int parents[] = new int[V];
for (int i = 0; i < V; i++) {
colors[i] = white;
}
for (int i = 0; i < V; i++) {
if (colors[i] == white) {
DFSCycleUtil(i, -1, colors, parents);
}
}
}
void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
void addPoint(int x, int y){
points.add(new PVector(x,y));
}
void drawGraph(){
for(int i = 0; i<points.size();i++){
circle(points.get(i).x,points.get(i).y,10);
text(i+1,points.get(i).x,points.get(i).y-5);
Iterator<Integer> in = adj[i+1].listIterator();
print(i + ": \n");
while (in.hasNext()) {
int t = in.next();
line(points.get(i).x,points.get(i).y,points.get(t-1).x,points.get(t-1).y);
}
}
for(int i = 0; i<path.size();i++){
fill(10,10,random(255));
beginShape();
for(int j = 0; j<path.get(i).size(); j++){
vertex(points.get(path.get(i).get(j)-1).x, points.get(path.get(i).get(j)-1).y);
}
endShape(CLOSE);
}
}
}
void setup(){
size(500,500);
Graph g = new Graph(9);
g.addEdge(1,2);
g.addEdge(1,3);
g.addEdge(3,2);
g.addEdge(3,4);
g.addEdge(5,2);
g.addEdge(5,6);
g.addEdge(4,2);
g.addEdge(4,6);
g.addEdge(4,5);
g.addPoint(100,50);
g.addPoint(150,50);
g.addPoint(100,100);
g.addPoint(150,100);
g.addPoint(200,50);
g.addPoint(200,100);
g.DFSCycle();
g.drawGraph();
}
问题是它还找到了涵盖其他先前发现的区域的区域,我不知道如何避免它。 我想首先知道是否有比我使用的方法更好的方法,然后如何解决我的需求。 提前致谢 示例图像:
这是我的实际结果:
,这将是我的最终结果:
I want to create an algorithm to understand how many closed areas there are in a graph with the relative points, at the moment the problem is that it finds almost all the loops, using a DFS algorithm. However, a problem arises
This is my actual code,momentarily done on processing for instant video feedback:
import java.util.Iterator;
import java.util.LinkedList;
class Graph {
int white = 0, gray = 1, black = 2;
ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
int V;
LinkedList<Integer>[] adj;
LinkedList<Integer>[] cycles;
LinkedList<PVector> points = new LinkedList<PVector>();
int num_cycles = 0;
Graph(int v) {
V = v;
adj = new LinkedList[V];
cycles = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList();
cycles[i] = new LinkedList();
}
}
void DFSCycleUtil(int source, int parent, int[] colors, int[] parents) {
if (colors[source] == gray) {
System.out.println("Cycle");
path.add(new ArrayList<Integer>());
int curr_parent = parent;
cycles[num_cycles].add(source);
System.out.println(source);
path.get(num_cycles).add(source);
while (curr_parent != source) {
cycles[num_cycles].add(curr_parent);
path.get(num_cycles).add(curr_parent);
System.out.println(curr_parent);
curr_parent = parents[curr_parent];
}
num_cycles++;
return;
} else if (colors[source] == black) {
return;
}
parents[source] = parent;
colors[source] = gray;
Iterator<Integer> i = adj[source].listIterator();
while (i.hasNext()) {
int n = i.next();
if (n != parent) {
DFSCycleUtil(n, source, colors, parents);
}
}
colors[source] = black;
}
void DFSCycle() {
int colors[] = new int[V];
int parents[] = new int[V];
for (int i = 0; i < V; i++) {
colors[i] = white;
}
for (int i = 0; i < V; i++) {
if (colors[i] == white) {
DFSCycleUtil(i, -1, colors, parents);
}
}
}
void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
void addPoint(int x, int y){
points.add(new PVector(x,y));
}
void drawGraph(){
for(int i = 0; i<points.size();i++){
circle(points.get(i).x,points.get(i).y,10);
text(i+1,points.get(i).x,points.get(i).y-5);
Iterator<Integer> in = adj[i+1].listIterator();
print(i + ": \n");
while (in.hasNext()) {
int t = in.next();
line(points.get(i).x,points.get(i).y,points.get(t-1).x,points.get(t-1).y);
}
}
for(int i = 0; i<path.size();i++){
fill(10,10,random(255));
beginShape();
for(int j = 0; j<path.get(i).size(); j++){
vertex(points.get(path.get(i).get(j)-1).x, points.get(path.get(i).get(j)-1).y);
}
endShape(CLOSE);
}
}
}
void setup(){
size(500,500);
Graph g = new Graph(9);
g.addEdge(1,2);
g.addEdge(1,3);
g.addEdge(3,2);
g.addEdge(3,4);
g.addEdge(5,2);
g.addEdge(5,6);
g.addEdge(4,2);
g.addEdge(4,6);
g.addEdge(4,5);
g.addPoint(100,50);
g.addPoint(150,50);
g.addPoint(100,100);
g.addPoint(150,100);
g.addPoint(200,50);
g.addPoint(200,100);
g.DFSCycle();
g.drawGraph();
}
The problem is that it also finds areas that cover other previously found areas, and I don't know how to avoid it.
I would like to know first if there is a better method than the one I am using, and then how I can solve my need.
Thanks in advance
Example images:
This is my actual result:
And this would be my final result:
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论