graph - 너비 우선 검색 대신 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 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]]);
                }
            }
        }
    }

기본 차이점은 꼭지점을 테스트하는 순서입니다. 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를 게시하십시오.

프로그램의 전체 코드. 목표는 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);
    }
}