알고리즘20 :: Graph Search

* 그래프 탐색모든 시작점 x에서 모든 정점을 1번씩 하는것을 의미한다. 
* 깊이 우선 탐색 vs 너비우선탐색
깊이는 갈수있을때까지 진행하고 못가면 뒤로백 합니다.
너비는 한정점에서 갈수있는걸 동시에긴다. 

어떤 순서로 방문하는가가 중요한데,
Dfs는 보통 스택을 이용하고,
이 목적은 모든 정점을 한번씩 방문한다. 가 가장 핵심 포인트다.
Check 배열이 필요하다.
순서는 상관없다.
스택에 쌓인다. 그러면,
1 - 2 - 3 - 4 - 5 - 5에서 더이상 갈수있는게없음 스택 이용 기록중 전정점4로 돌아감 -6
방문을 6까지 하고
스택이비면 탐색 종료한다.
Dfs는 재귀함수를 쓴다. 스택으로 구현할 수 도 있다.

dfs를 인접리스트로 구현하게 되면 존재하는 간선만 저장하게 되는데,반면에, 시간복잡도는 인접행렬은 모든 정점 한번씩 방문Dfs함수는 정점의개수 V만큼 호출O(V)가 되고 모든 정점을 방문하게 되니 복잡도는 O(V^2)

인접리스트는 V만큼 호출
한정점과 연결된 간선의개수이므로
모든 정점 한번씩방문하고 그리고
간선의개수를 추가 하게 된다.
시간복잡도는 O(V+E)이다.
=> 공간뿐만아니라 시간도 차이가난다.

* Bfs는 큐를 이용해서 어디방문기록한다.
1,5,2
Bfs갈수있는걸 큐에다넣는다.
1,5,3
동시에 체크해줘야한다.
큐에넣음과 동서에 방문했다 체크 이 부분이 중요하다.
큐가비면 탐색완료, 직접 그림을 그려보면 쉽게 알 수 있다.

BFS는 소스코드를 보면 front 값을 저장하고 pop을 한뒤 visited 를 체크한다.
이 뒤에 해당 정점에서 갈 수 있는 정점을 모두 push 하고 queue가 비어있지 않으면 또다시 하나를 꺼내서 
해당 정점과 연결되어 있는 모든 정점을 살펴본다. 이는 시간복잡도가 V제곱이 걸린다. (visited가 방문되면 찾아보지 않는다.)
=>정점의 개수만큼 반복문을 돌면서 정점이 존재하는지 그리고 check 여부를 살펴보기 때문에 

하지만, 인접리스트는 V더하기 E다 왜?
간선이 존재하는지 여부만 확인하고 해당 정점(check 배열로 true/false 하여) 을 갈 수 있는지 확인하고 갈 수 있으면 push 하여 queue에 넣어주게 된다. 
=>O(V+E)

* 연결요소
위에서 소개한 그래프들은 연결그래프라고한다
연결요소는
Bfs dfs아무거나써도된다.(=>한 정점에서 시작해서 연결된 모든 정점을 한번씩 방문하는것이기 때문이다.)
그래서 찾게되면 연결요소 하나찾음
여기서 이미방문되어있으면 기존의 연결요소를 의미하고 새로운정점발견시 새연결요소를 찾았다는 의미가된다..
Dfs 시작을 2번이니 연결요소도 2번이된다.
이와 관련된 문제가 있다. 
BOJ :: 11724 - 연결 요소의 개수 , 이문제는 정점의 개수만큼 돌면서 check 배열을 둬서 dfs로 check가 이루어지지 않은 부분에 대해서 존재하면 cnt를 하나 
증가시켜서 연결요소를 찾으면 된다. 

* 이분 그래프
그래프인데, A B로 나눌 수 있다. 조건은 A에 들어있는 정점끼리는 연결하는 간선이 없어야 한다. 
이분 그래프는 방문하지 않지만, 색은 검사한다. 색이 서로 달라야 한다. 탐색을 이어갈때마다 방문하지 않은 정점이면 방문하고,
이미 방문했으면 색이 서로 다른지만 비교한다. 
이와 관련된 문제는 BOJ:: 1107 문제가 있다.