DFS(깊이우선탐색) 알고리즘

dfs()는 스텍을 사용하여 구현한 함수

dfs_rec()는 재귀를 사용하여 구현한 함수

검색했을 때 개념은 스텍으로 설명했지만 막상 스텍으로 구현한 소스는 거의 없었는데, dfs의 경우는 재귀가 훨씬 간단해서 그런 것 같음.

package com.company;

import java.util.Scanner;
import java.util.Stack;

public class Main {

    static int[][] graph = new int[1001][1001];
    static boolean[] visitied = new boolean[1001]; //노드의 방문여부

    static int N, E, startPoint;



    public static void main(String[] args) {
   // write your code here

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); //노드의 수
        E = sc.nextInt(); //간선의 수
        startPoint = sc.nextInt(); //시작지점;


        int v1, v2;
        for(int i=1; i<=E; i++){
            v1 = sc.nextInt();
            v2 = sc.nextInt();

            graph[v1][v2]=1;
            graph[v2][v1]=1;
        }

//        dfs_rec(startPoint); //재귀를 이용한 DFS
        dfs_stack(startPoint); //스텍을 이용한 DFS

    }

    static void dfs_rec(int pos){

        visitied[pos] = true;
        System.out.printf(pos + " ");

        for(int i=1; i<=N; i++){

            //연결되어 있으면서 방문하지 않은 노드를 방문
            if( graph[pos][i]==1 && visitied[i]==false){
                visitied[i] = true;
                dfs_rec(i);
            }
        }
    }

    static void dfs_stack(int startPoint){

        Stack<Integer> stack = new Stack();

        int pos = startPoint; //현재위치
        visitied[startPoint]=true;
        System.out.printf(pos + " ");

        //시작지점을 큐에 넣음
        stack.push(startPoint);

        //스텍이 차 있는 동안 진행
        while( !stack.isEmpty() ){

            boolean isConnection = false; //현재 위치에서 이동할 수 있는 곳이 있는지
            for(int i=1; i<=E; i++){

                if( graph[pos][i]==1 && visitied[i]==false){
                    pos=i;

                    stack.push(pos);
                    visitied[pos]=true;
                    isConnection = true;

                    System.out.printf(pos + " ");
                }
            }//for

            if( isConnection == false ){
                pos = stack.pop();
            }

        }
    }
}

*테스트 Case

4 5 1

1 2

1 3

1 4

2 4

3 4

=>1 2 4 3