[백준] DFS_BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/*
Graph
           1
        /  |  \
       2   3   4
      /   / \   \
     5   6   7   8
         | 
         9
*/

public class DFS_BFS {

	static int matrix[][];
	static boolean[] visit;
	static int v, e, s;

	public static void main(String[] args) {

		int num1, num2;

		Scanner sc = new Scanner(System.in);

		System.out.print("Vertex: ");
		v = sc.nextInt();

		System.out.print("Edge: ");
		e = sc.nextInt();

		System.out.print("Start: ");
		s = sc.nextInt();

		matrix = new int[v + 1][v + 1];
		visit = new boolean[v + 1];

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

			System.out.println("Vertex---Edge---Vertex");

			System.out.print("num1: ");
			num1 = sc.nextInt();

			System.out.print("num2: ");
			num2 = sc.nextInt();

			matrix[num1][num2] = matrix[num2][num1] = 1;

		}

		System.out.println("DFS Recursive");
		dfs_r(s);
		init_visit();

		System.out.println("DFS <STACK>");
		dfs(s);
		init_visit();

		System.out.println("BFS <QUEUE>");
		bfs(s);

		sc.close();

	}

	public static void init_visit() {

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

			visit[i] = false;

		}
		System.out.println();

	}

	public static void dfs_r(int s) {

		System.out.print(s + " ");
		visit[s] = true;

		for (int i = 1; i < v + 1; i++) {
			if (matrix[s][i] == 1 && !visit[i]) {
				dfs_r(i);
			}
		}

	}

	public static void dfs(int s) {

		Stack<Integer> stack = new Stack<Integer>();

		int p;
		boolean flag;

		stack.push(s);
		visit[s] = true;
		System.out.print(s + " ");

		while (!stack.isEmpty()) {

			p = stack.peek();
			flag = false;

			for (int i = 1; i < v + 1; i++) {
				if (matrix[p][i] == 1 && !visit[i]) {

					stack.push(i);
					flag = true;
					System.out.print(i + " ");
					visit[i] = true;
					break;

				}
			}

			if (!flag) {
				stack.pop();
			}
		}

	}

	public static void bfs(int s) {

		Queue<Integer> queue = new LinkedList<Integer>();

		queue.offer(s);
		visit[s] = true;

		while (!queue.isEmpty()) {

			s = queue.poll();
			System.out.print(s + " ");

			for (int i = 1; i < v + 1; i++) {
				if (matrix[s][i] == 1 && !visit[i]) {

					queue.offer(i);
					visit[i] = true;

				}

			}
		}
		

	}

}