<Udemy 그래프/그래프 순회> TIL-67

  오늘 공부한 내용은 그래프와 그래프 순회에 대해서 공부했다. 그래프란 유한하고 변할 수 있는 꼭지점(노드)의 집합으로 구성된 데이터 구조이다. 이 꼭지점들의 집합에 순서가 없는 경우에는 무방향 그래프, 순서가 있는 경우에는 유방향 그래프라고 한다. 즉, 그래프는 노드와 노드들의 연결을 모은 것이다. 그러므로 트리도 그래프의 일종이다. 다만 트리는 몇 가지 규칙이 추가되어 부모와 자식노드로 구성되고 시작점인 루트가 존재하는 것이다. 하지만 그래프에는 부모 노드라는 것이 없고, 시작점도 없다. 다 동일한 노드일 뿐이다. 또한 그래프는 트리나 연결 리스트 같은 수준의 패턴이 없다. 자유로운 형식의 노드가 있고 그 사이에 연결만 있을 뿐이다. 또한 트리는 한 노드에서 다른 노드로 가는 경로가 딱 한 가지만 존재해야 하지만 그래프는 수 개의 경로가 존재할 수 있다.

 

  그래프 자료구조를 만드는 방법은 두 가지가 존재한다. 한 가지는 인접 행렬 방식이고, 다른 하나는 인접 리스트 방식이다. 노드들이 숫자로 이뤄진 경우에는 인접 행렬 방식으로 작성하고 노드들이 문자열로 이뤄진 경우에는 인접 리스트, 즉 객체를 활용해서 간선을 표시하는 방법이 있다. 이렇게 만들어진 그래프를 탐색하는 방법에도 두 가지가 있다 DFS방법과 BFS방법이다.

 

  DFS방법은 깊이 우선 그래프 순회 방식으로 하나의 정점을 시작으로 연결되어 있는 정점의 끝까지 도달하고 그 다음으로 넘어가는 방식이고, BFS방법은 너비 우선 그래프 순회 방식으로 하나의 정점과 연결되어 있는 다른 정점들을 먼저 다 순회하고 그 다음에 다음 정점으로 옮겨가서 해당 정점과 연결되어 있는 정점들을 다 확인하는 작업을 반복하는 것이다. DFS든 BFS든 중요한 것은, 방문했던 정점들을 잘 기억하고 있어야 한다는 것이다! 

 

  오늘 공부한 그래프와 그래프 순회는 사실 머리로는 이해하는데 큰 어려움이 없었지만, 오히려 코드를 구현하는것 자체는 굉장히 어렵게 다가 왔다. 하지만 그래프 자료 구조 자체는 굉장히 신선하게 느껴졌었다. 기존에 아무런 생각없이 이용했던 네이게이션, 유튜브 알고리즘 추천, 인터넷 쇼핑몰에서의 내가 평상시 좋아하는 스타일의 옷들의 추천 등 뭔가 엄청나게 복잡한 원리가 들어있을 것이라고 생각했지만, 생각보다 기본적인 원리는 간단하다는 사실에 놀랐고, '왜 한 번도 궁금해 하지 않았을까?'라는 스스로에 대한 반성도 조금은 하게 되었다. 너무 익숙하고 자연스러운 것들이 당연하다고만 생각했지 어떻게 이런걸 만들고 동작하게 할 수 있는지에 대해서는 생각해 본적이 없으니 말이다. 

 

2022.08.17 - [언어 공부 및 정리/JavaScript [알고리즘 & 자료구조(Udemy강의)]] - 20 그래프

20 그래프

2022.08.19 - [언어 공부 및 정리/JavaScript [알고리즘 & 자료구조(Udemy강의)]] - 21 그래프 순회

21 그래프 순회