Graph

출처 : GeeksforGeeks https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

1. 단순히 노드(node)와 노드를 연결하는 간선(엣지 edge)를 하나로 모아 놓은 자료 구조

2. Root 노드 개념 없음

3. 부모 - 자식 노드 개념 없음

4. 연결되어 있는 데이터들의 관계를 표현 할 수 있는 자료 구조

• 지도, 지하철 노선도, 도로 등
• 페이스북의 나와 친구 사이의 관계
• 간선(엣지)가 없는 고립된 노드도 존재한다.

5. 인접리스트, 인접행렬로 구현할 수 있다.

• 인접리스트 (Adjacency List) - 노드에 연결된 엣지들을 리스트로 나열
• 공간은 적게 차지하지만 복잡함

출처 : 제로초님 블로그 https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

• 인접행렬 (Adjacency Matrix) - 그래프를 이차원 배열로 만들어서 엣지로 연결이 되어 있으면 1, 아니면 0으로 표현
• 공간은 많이 차지하지만 간단하게 구현 가능

출처 : 제로초님 블로그
https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

6. 깊이우선탐색(DFS) vs 너비우선탐색(BFS)

1. 깊이우선탐색 - 갈 수 있는 깊이만큼 끝까지 가서 탐색 한 후 더 이상 탐색 할 곳이 없으면 이전에 탐색한 정점으로 돌아가 탐색 진행
   • Stack 을 이용해서 탐색
2. 너비우선탐색 - 최단거리의 노드를 탐색 후 그 다음 최단거리의 노드 탐색
   • Queue를 이용하여 탐색