-
그래프(Graph) 설명과 DFS, BFS 구현자료구조 2021. 10. 30. 12:57
그래프 란
- 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것
- 그래프에는 방향성이 있을수도 있고 없을수도 있다.
- 트리는 그래프의 한 종류이다.
- 모든 그래프가 트리는 아니다.
- 트리는 사이클이 없는 하나의 연결 그래프
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA - 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다.
- 모든 점점 쌍간에 경로가 존재하는 그래프는 '연결 그래프' 라고 부른다.
- 그래프에는 사이클이 존재할 수도 있고 존재하지 않을 수도 있다.
사이클이 없는 비순환 그래프 https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA - 그래프를 시각적으로 그려보면 아래와 같다.
출처: 코딩 인터뷰 완전분석 그래프를 표현하는 방법
1) 인접행렬
- 2차원 배열에 표현하는 방법
- 그래프를 표에다 표현하는 방법
- 서로 연결된 노드들은 1로 표현하고 연결이 없으면 0으로 2차원 배열방을 채우는 방법이다.
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA 2) 인접리스트
- 배열에 노드들을 나열하고 관계를 연결 리스트로 표현하는 방법
- 배열 방에 모든 노드들을 집어넣고 각 배열방에 있는 해당 노드와 인접한 노드들을 연결리스트로 나열해서 저장하는 방법
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA 그럼 위 그림에서 노드들의 개수는 몇개일까?
-> 노드들은 관계를 나타낸다. 간선의 개수를 m 이라 할 때, 총 노드의 개수는 2m 개 생긴다.
연결은 두개의 노드가 서로 연결되는것이니까 원래 간선 개수보다 2배 많아지는것이 이유이다.그래프 탐색
- 깊이 우선 탐색 (Depth-First Search)
- inorder, preorder, postorder 순회 방법이 DFS 에 속한다.
- 하나의 자식노드를 방문했으면 그 자식들을 끝까지 파고든다.
- 자식노드의 마지막 노드를 만날때까지 반복한 후 형제노드를 방문한다.
- 너비 우선 탐색 (Breadth-First Search)
- 시작점에서 자식노드를 모두 방문하고 , 자식의 자식을 방문하는 식으로 검색한다.
- 즉, 레벨단위로 검색이 이루어진다.
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 유용하다.
- DFS 를 이용하게되면 정답에서 동떨어진 경로를 계속해서 탐색해 나갈 수 있다.
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA 
출처: 코딩 인터뷰 완전분석 DFS, BFS 구현
(업데이트 예정)
참고자료
'자료구조' 카테고리의 다른 글
트리(Tree) 설명과 구현 (0) 2021.10.30 LinkedList (0) 2021.09.10 ArrayList & LinkedList 설명과 비교 (0) 2021.08.21 HashTable (0) 2021.08.21