[ DFS 개 념 ]
각 정점 노드를 깊게 탐색하는 방식

매 탐색 STACK으로 갈 수 있는 "최대 깊이" 탐색 갈 곳 없으면 이전 정점 돌아감

재귀 # 스택

1. 현재 정점과 인접한 간선 하나하나 검사.

2. 아직 방문하지 않은 정점으로 향하는 간선 있다면 그대로.

3. 더이상 갈 곳이 없다면 포기, 마지막에 온 간선을 따라 돌아감. ( => 재귀 )

인접 배열

For Loop v번 탐색 - O(v)

v개의 정점 모두 탐색 - O(v)

Total - O(v^2)

visted = {false,false,false,false,false,false,false,false};

graph = {{2,3,...},{2,3,...},{2,3,...},{2,3,...},{2,3,...},{2},{3,...},{5}};

main{ dfs(start) }

void dfs (int x) { void dfs2 ( int x ) {

check[x] = true;                                          visited[x] = true;              => 현재 노드 방문 처리

for(int i = 1; i <= v; i++){                             System.out.println(v+ "");    => 방문 노드 출력

      if(graph[x][i] == 1 && !check[i]){              for(int i : graph[x]) {          => 인접 노드 탐색

          dfs(i);                                                  if(visited[i]==false) {     => 방문못한 인접노드중 가장 작은거

      }                                                                  dfs(x);

}                                                                  }

} }

                                                           }

// 스택 사용

void dfs3 (int [][] graph, int start, boolean[] visited) {

  visited[start] = true;                         => 시작 노드 방문 처리

  System.out.print(start + " ");               => 방문 노드 출력



  Deque<Integer> stack = new LinkedList<>();

  stack.push(start);                              => 시작 노드 스택에 입력



  while(!stack.isEmpty()){

       int now = stack.pop();

       boolean hasNear = false;               => 방문 못한 인접노드 유무 확인

       for(int i : graph[now]){                   => 인접 노드 방문 안한경우 스택에 저장 후 방문처리

           if(!visited[i]){

                hasNear = true;

                stack.push(i);

                visited[i] = true;

                System.out.println(i + " ");      => 방문 노드 출력

                break;

           }

       }

       if(hasNear == false)     stack.pop();    => 방문 못한 인접노드 없는 경우 해당 노드 꺼내기

  }

}

인접 리스트

각 정점에 연결된 간선(v) 개수만큼 탐색 - O(v)

각 정점의 인접한 노드(e) 번 탐색 - O(e)

Total - O(v+e)

void dfs (List[] list, boolean check, int x) {

check[x] = true;

for(int i = 0; i < list[x].size(); i++){

      int next = (int) list[x].get(i);

      if(!check[next]){

          dfs(next);

      }

}

}

[ BFS 개 념 ]
가까운 인접 노드부터 탐색

QUEUE 를 사용해서 현재 노드에서 인접해 있는 노드를 QUEUE에 넣는 방식 작동

각 정점 방문 후 모든 인접 정점 검사

ㄴ> 처음 보는 정점을 발견하여 방문예정으로 기록

ㄴ> 인접한 정점을 모두 검사 후 저장 목록에서 다음 정점 꺼내 방문

큐 # 다익스트라 # 프림

상태

1. 미발견 상태 (!check[i])

2. 발견했지만 방문예정 상태

3. 발견하고 방문 상태 (check[i])

인접 배열

For Loop v번 탐색 - O(v)

v개의 정점 모두 탐색 - O(v)

Total - O(v^2)

void bfs (int v, int start) {

queue<Integer> q = new LinkedList<>();    // 방문예정

boolean[] check = new boolean[v+1];

check[start] = true;     

q.add(start);         

while(!q.empty()){    

      int now = q.poll();  

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

           if(graph[now][i] == 1 && !check[i]){     

              check[i] = true;

              q.add(i);

           }

      }

}

}

인접 리스트

각 정점에 연결된 간선(v) 개수만큼 탐색 - O(v)

각 정점의 인접한 노드(e) 번 탐색 - O(e)

Total - O(v+e)

void bfs (List[] list, int v, int start) {

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

boolean[] check = new boolean[v+1];

check[start] = true;

q.add(start);

while(!q.empty()){

      int now = q.poll();

      for(int i = 0; i < list[now].size(); i++){

          int next = (int)list[now].get(i);

          if(!check[next]){

               check[next] = true;

               q.add(next);

          }

      }

}

}

@ BFS 와 DFS 언제 사용
1. 모든 노드 방문 -> DFS (약우위) 이유는..?

2. DFS가 BFS보다 좀 더 간단함

3. 검색속도 우선 -> BFS

*결과

1. 검색 대상 그래프가 정말 클때 or 경로의 특징을 저장할때 -> DFS

2. 검색 대상 규모가 안크고 시작지점으로 부터 원하는 대상 별로 멀지 않다면 or 최단거리 -> BFS