[JAVA/알고리즘] BFS DFS 정리
BFS 는 너비 우선 탐색을 뜻하고
꼭지점의 형제들을 우선으로 탐색한다고 설명하고 있습니다.
public class bfs {
// 노드의 수
static int n = 7;
static int arr[][] = {{0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0},
{0,1,0,0,1,1,1,0},
{0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0},
{0,0,1,0,0,0,0,1},
{0,0,1,0,0,0,0,0},
{0,0,0,0,0,1,0,0}};
public static void main(String[] args) {
// 탐색한 곳을 확인하기 위함
int f[] = new int[n+1];
int q[] = new int[7];
int head = 0, tail = 0;
int i,j;
int start = 1;
f[start] = 1;
q[tail++]=start;
do {
i = q[head++];
for(j=1; j<=n; j++) {
if(arr[i][j]==1 && f[j]==0) {
q[tail++] = j;
f[j] = 1;
System.out.println(i + " -> " + j);
}
}
}while(head < tail);
}
}
보시는거와 같이 깊이 보다는
넓이 위주(같은 레벨(?))로 탐색을 하기 시작합니다.
그럼 DFS는 어떨까요
DFS 는 깊이 우선 탐색으로 꼭지점의
자식들을 먼저 탐색한다고 합니다.
형제? 자식?
그냥 보는게 빠릅니다
public class dfs {
// 노드의 수
int n = 7;
int arr[][] = {{0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0},
{0,1,0,0,1,1,0,0},
{0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1},
{0,0,1,0,0,0,1,0},
{0,0,0,0,0,1,0,0},
{0,0,0,0,1,0,0,0}};
// 탐색한 곳을 확인하기 위함
int [] f = new int[n+1];
public static void main(String[] args) {
new dfs().seach(1);
System.out.println("end");
}
public void seach(int i) {
f[i] = 1;
for (int j=1; j<=n; j++) {
if(arr[i][j]==1 && f[j]==0) {
System.out.println(i+" -> "+j);
seach(j);
}
}
}
}
자식들을 먼저 탐색하는 것을 알 수 있습니다.
끝!
문제가 있을 경우 알려주세요!
