# DFS and BFS

**틀린 부분(틀린 이유)**

BFS에서 현재 노드의 인접노드를 넣을 때, 현재 큐에서 뽑은 노드의 인접노드를 넣어주어야 하는데 처음 시작한 노드의 인접노드를 넣어버렸다! 그래서 첫 노드의 인접노드만 방문하고 탐색이 종료되었다!

1. DFS

```java
public static void dfs(int x) {
        if (c[x]) {
            return;
        }
        c[x] = true;
        System.out.print(x + " ");
        for (int y : a[x]) {
            if (c[y] == false) {
            	//c[y] = true;
                dfs(y);
            }
        }
    }
```

2\. BFS

```java
public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        c[start] = true;
        while (!q.isEmpty()) {
            int x = q.remove();
            System.out.print(x + " ");
            for (int y : a[x]) {
                if (c[y] == false) {
                    c[y] = true;
                    q.add(y);
                }
            }
        }
    }
```

**DFS와 BFS 구현의 차이**

BFS : for(int y:a\[x])문으로 인접리스트를 통해서 인접 노드를 방문하지 않았다면 true 처리하고, 큐에 넣는다.

DFS : for(int y:a\[x])문 안에서 재귀호출만하고 true처리하지 않는다. 왜냐하면 이 for문 내에서 true로 처리해버리면 그 바로 밑에 재귀함수 호출에 들어가는 인자는 true가 되버려 DFS가 재귀호출되어도 바로 리턴되버리기 때문이다!

**main 함수 구현**\
**1. 인접리스트 : 정수형 ArrayList 배열 생성, 이용한다!**

```java
public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();
        a = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u].add(v);
            a[v].add(u);
        }
        for (int i=1; i<=n; i++) {
            Collections.sort(a[i]);
        }
        c = new boolean[n+1];
        dfs(start);
        System.out.println();
        c = new boolean[n+1];
        bfs(start);
        System.out.println();
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph/dfs-and-bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.