그래프(Graph) 과 DFS, BFS 구현

그래프란?

---

• 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것
• 그래프에는 방향성이 있을수도 있고 없을수도 있다.
• 트리는 그래프의 한 종류이다.
• 모든 그래프가 트리는 아니다.
• 트리는 사이클이 없는 하나의 연결 그래프

그래프 종류

---

무방향 그래프

방향성이 없는 그래프를 무방향 그래프라 한다.

방향 그래프

무방향 그래프에서 간선에 방향 정포가 포함된 그래프를 방향 그래프라 한다

완전 그래프

각각의 장점에서 다른 모든 장점을 연결한 그래프를 완전 그래프라 한다

 

 

 

그래프에서 사용하는 용어

---

정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)
간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 나타낸다..
인접 정점(adjacent vertex) : 간선에 의해 연결된 정점으로 위에서 (정점0과 정점1은 인접 정점)
단순 경로(simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (정점 0의 차수는 3)
진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수를 뜻한다
진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수를 뜻한다.

 

 

 

그래프 탐색

---

• 깊이 우선 탐색 (DFS, Depth-First Search)
  
  • inorder, preorder, postorder 순회 방법이 DFS 에 속한다.
  • 하나의 자식노드를 방문했으면 그 자식들을 끝까지 파고든다.
  • 자식노드의 마지막 노드를 만날때까지 반복한 후 형제노드를 방문한다.

 

• 너비 우선 탐색(BFS, Breadth-First Search)
  • 시작점에서 자식노드를 모두 방문하고 , 자식의 자식을 방문하는 식으로 검색한다.
  • 즉, 레벨단위로 검색이 이루어진다.
  • 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 유용하다.
  • DFS 를 이용하게되면 정답에서 동떨어진 경로를 계속해서 탐색해 나갈 수 있다.

출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA

참고 자료

---

https://hyokeun0419.tistory.com/59

https://coding-factory.tistory.com/610

https://yunyoung1819.tistory.com/86