DFS图算法出现问题,发现错误的循环

发布于 2025-01-18 09:18:54 字数 4132 浏览 4 评论 0原文

我想创建一种算法,以了解具有相对点的图表中有多少个封闭区域,目前问题是它使用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:

enter image description here

And this would be my final result:

enter image description here

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文