>

그래프를 작성하는 JAVA 프로그램이 있고 너비 우선 검색이 있지만 깊이 우선 검색으로 변경하고 싶습니다. 코드에서 어떤 변경을해야합니까? 미리 도움을 주셔서 감사합니다.

public class ConnectedComponents
{
    static final int MAXV         = 100;
    static boolean   processed[]  = new boolean[MAXV];
    static boolean   discovered[] = new boolean[MAXV];
    static int       parent[]     = new int[MAXV];
    static void bfs(CCGraph g, int start)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        int i, v;
        q.offer(start);
        discovered[start] = true;
        while (!q.isEmpty())
        {
            v = q.remove();
            process_vertex(v);
            processed[v] = true;
            for (i = g.degree[v] - 1; i >= 0; i--)
            {
                if (!discovered[g.edges[v][i]])
                {
                    q.offer(g.edges[v][i]);
                    discovered[g.edges[v][i]] = true;
                    parent[g.edges[v][i]] = v;
                }
            }
        }
    }


  • 답변 # 1

    깊이 우선 검색과 너비 우선 검색의 차이점을 이해해야한다고 생각합니다. 심도 우선 검색 코드는 다음과 같습니다.

    public class ConnectedComponents
    {
        static final int MAXV         = 100;
        static boolean   processed[]  = new boolean[MAXV];
        static boolean   discovered[] = new boolean[MAXV];
        static int       parent[]     = new int[MAXV];
        static void dfs(CCGraph g, int vertex)
        {
            discovered[vertex] = true;
                for (i = g.degree[vertex] - 1; i >= 0; i--)
                {
                    if (!discovered[g.edges[vertex][i]])
                    {
                        parent[g.edges[v][i]]=vertex;
                        dfs(g.edges[v][i]]);
                    }
                }
            }
        }
    
    

  • 답변 # 2

    기본 차이점은 꼭지점을 테스트하는 순서입니다. BFS는 대기열 (FIFO : First In First Out)을 사용하지만 DFS는 스택 (LIFO : Last In First Out)을 사용합니다.
    LinkedList 를 사용하여 스택을 구현할 수 있습니다 :

    LinkedList<Integer> stack = new LinkedList<Integer>();
    stack.pop(); //returns the top of the stack
    
    

    자세한 내용은 테스트 데이터를 포함한 mcve를 게시하십시오.

  • 답변 # 3

    프로그램의 전체 코드. 목표는 bfs를 dfs로 변경하는 것입니다.

    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    class CCGraph
    {
        static final int MAXV      = 100;
        static final int MAXDEGREE = 50;
        public int       edges[][] = new int[MAXV + 1][MAXDEGREE];
        public int       degree[]  = new int[MAXV + 1];
        public int       nvertices;
        public int       nedges;
        CCGraph()
        {
            nvertices = nedges = 0;
            for (int i = 1; i <= MAXV; i++)
                degree[i] = 0;
        }
        void read_CCGraph(boolean directed)
        {
            int x, y;
            Scanner sc = new Scanner(System.in);
            System.out.println("Enter the number of vertices: ");
            nvertices = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            int m = sc.nextInt();
            System.out.println("Enter the edges: <from> <to>");
            for (int i = 1; i <= m; i++)
            {
                x = sc.nextInt();
                y = sc.nextInt();
                insert_edge(x, y, directed);
            }
            sc.close();
        }
        void insert_edge(int x, int y, boolean directed)
        {
            if (degree[x] > MAXDEGREE)
                System.out.printf(
                        "Warning: insertion (%d, %d) exceeds max degree\n", x, y);
            edges[x][degree[x]] = y;
            degree[x]++;
            if (!directed)
                insert_edge(y, x, true);
            else
                nedges++;
        }
        void print_CCGraph()
        {
            for (int i = 1; i <= nvertices; i++)
            {
                System.out.printf("%d: ", i);
                for (int j = degree[i] - 1; j >= 0; j--)
                    System.out.printf(" %d", edges[i][j]);
                System.out.printf("\n");
            }
        }
    }
    public class ConnectedComponents
    {
        static final int MAXV         = 100;
        static boolean   processed[]  = new boolean[MAXV];
        static boolean   discovered[] = new boolean[MAXV];
        static int       parent[]     = new int[MAXV];
    
        static void bfs(CCGraph g, int start)
        {
            LinkedList<Integer> q = new LinkedList<Integer>();
            int i, v;
            q.offer(start);
            discovered[start] = true;
            while (!q.isEmpty())
            {
                v = q.remove();
                process_vertex(v);
                processed[v] = true;
                for (i = g.degree[v] - 1; i >= 0; i--)
                {
                    if (!discovered[g.edges[v][i]])
                    {
                        q.offer(g.edges[v][i]);
                        discovered[g.edges[v][i]] = true;
                        parent[g.edges[v][i]] = v;
                    }
                }
            }
        }
        static void initialize_search(CCGraph g)
        {
            for (int i = 1; i <= g.nvertices; i++)
            {
                processed[i] = discovered[i] = false;
                parent[i] = -1;
            }
        }
        static void process_vertex(int v)
        {
            System.out.printf(" %d", v);
        }
        static void connected_components(CCGraph g)
        {
            int c;
            initialize_search(g);
            c = 0;
            for (int i = 1; i <= g.nvertices; i++)
            {
                if (!discovered[i])
                {
                    c++;
                    System.out.printf("Component %d:", c);
                    bfs(g, i);
                    System.out.printf("\n");
                }
            }
        }
        static public void main(String[] args)
        {
            CCGraph g = new CCGraph();
            g.read_CCGraph(false);
            g.print_CCGraph();
            connected_components(g);
        }
    }
    
    

관련 자료

  • 이전 algorithm - 파이썬에서 암시 적 오일러로 pde 해결 - 잘못된 출력
  • 다음 swift - 수신자 부담 전화 번호로 AG를 반환하는 PhoneNumberKit