[알고리즘] BFS와 DFS - 코드

| Using Adjacency Matrix

• 2차원 배열
• bfs만 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G1_AdjMatrixTest {

	static int N;
	static boolean[][] adjMatrix;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int C = Integer.parseInt(in.readLine());
		adjMatrix = new boolean[N][N];

		StringTokenizer st = null;
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adjMatrix[from][to] = adjMatrix[to][from] = true;
		}

		bfs();

	}

	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];

		// 탐색 시작 정점: 0으로 출발
		int start = 0;
		queue.offer(start);
		visited[start] = true;

		while (!queue.isEmpty()) {
			int current = queue.poll();
			// 현재 정점에관련된 처리
			System.out.println((char) (current + 65));

			// 인접 정점 탐색
			for (int i = 0; i < N; i++) {
				if (adjMatrix[current][i] // 인접정점
						&& !visited[i]) { // 미방문정점: 방문여부를 하는 이유는 다른 녀석에 의해 탐색이 되었는지 체크
					queue.offer(i);
					visited[i] = true;
				}
			}
		}

	}

}

| Using Adjacency List - 1

• LinkedList
• bfs, dfs 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// using LinkedList
public class G2_AdjListTest {

	static class Node {
		int vertex;
		Node next;

		public Node(int vertex, Node next) {
			super();
			this.vertex = vertex;
			this.next = next;
		}

		public Node(int vertex) {
			super();
			this.vertex = vertex;
		}

		@Override
		public String toString() {
			return "Node [vertex=" + vertex + ", next=" + next + "]";
		}

	}

	static int N;
	static Node[] adjList;
	static boolean[] visited; // for dfs

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int C = Integer.parseInt(in.readLine());
		adjList = new Node[N];

		StringTokenizer st = null;
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			adjList[from] = new Node(to, adjList[from]);
			adjList[to] = new Node(from, adjList[to]);
		}

		bfs();

		visited = new boolean[N];
//		visited[0] = true;
		dfs(0);

	}

	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];

		int start = 0;
		queue.offer(start);
		visited[start] = true;

		while (!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println((char) (current + 65));

			// 인접정점만 반복처리하기 때문에 인접체크조건이 없다.
			for (Node temp = adjList[current]; temp != null; temp = temp.next) {
				if (!visited[temp.vertex]) {
					queue.offer(temp.vertex);
					visited[temp.vertex] = true;

				}
			}

		}
	}

	private static void dfs(int current) {
		visited[current] = true;
		System.out.println((char) (current + 65));

		for (Node temp = adjList[current]; temp != null; temp = temp.next) {
			if (!visited[temp.vertex]) {
//				visited[current] = true;	// 여기에다가 방문체크 해도 됨. + 69번쨋줄에도 주석풀기
				dfs(temp.vertex);
			}
		}

	}

}

| Using AdjacencyList - 2

• ArrayList
• bfs, dfs 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// using ArrayList 
public class G3_AdjListTest2 {

	static int N;
	static ArrayList<Integer>[] adjList;
	static boolean[] visited; // for dfs

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int C = Integer.parseInt(in.readLine());
		adjList = new ArrayList[N];

		for (int i = 0; i < N; i++) {
			adjList[i] = new ArrayList<Integer>();
		}

		StringTokenizer st = null;
		for (int i = 0; i < C; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			adjList[from].add(to);
			adjList[to].add(from);

		}

		bfs();

		visited = new boolean[N];
//		visited[0] = true;
		dfs(0);

	}

	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];

		int start = 0;
		queue.offer(start);
		visited[start] = true;

		while (!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println((char) (current + 65));

			// 인접정점만 반복처리하기 때문에 인접체크조건이 없다.
			for (int temp : adjList[current]) { // temp:current와 인접정점인 해당정점의 번호
				if (!visited[temp]) {
					queue.offer(temp);
					visited[temp] = true;
				}
			}

		}
	}

	private static void dfs(int current) {
		visited[current] = true;
		System.out.println((char) (current + 65));

		for (int temp : adjList[current]) {
			if (!visited[temp]) {
//				visited[current] = true;	// 여기에다가 방문체크 해도 됨. + 69번쨋줄에도 주석풀기
				dfs(temp);
			}
		}

	}

}

input data - 세 코드 모두 동일

7
8
0 1
0 2
1 3
1 4
2 4
3 5
4 5
5 6