그래프

그래프

정의

• 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조
• 연결되어있는 객체간의 관계를 표현할 수 있는 자료구조
  지도, 지하철 노선도의 최단 경로 등..

용어

• 정점 (노드) : 데이터가 저장 됨.
• 간선 (링크) : 노드간의 관계를 나타냄.
• 인접 정점 : 간선에 의해 서로 연결된 정점
• 단순 경로 : 같은 간선을 지나가지 않는 경로
• 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (몇개가 한 노드에 연결되었는가)
• 진출 차수 : 방향그래프에서 사용되는 용어로, 한 노드에서 외부로 향하는 간선의 수
• 진입 차수 : 방향그래프에서 사용되는 용어로 외부 노드에서 들어온 간선의 수

구현 방식

• 인접행렬 방식 : 그래프의 노드를 2차원 배열로 만든 것.

  {: width="50%" height="50%"}

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

• 장점 : 2차원 배열 안에 모든 정점들의 간선 정보를 담기 떄문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 $$O(1)$$의 시간복잡도를 가짐.
• 단점 : 무조건 2차원 배열 이상을 사용하므로 필요 이상의 메모리 공간을 차지함.

• 인접 리스트 방식 : 그래프의 노드들을 리스트로 표현한 것.

  {: width="50%" height="50%"}

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

• 장점 : 정점들의 연결 정보를 탐색할 때 $$O(n)$$의 시간 복잡도를 가짐.
• 단점 : 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸림.

그래프의 종류

• 무방향 그래프 : 두 정점을 잇는 간선에 방향이 없는 그래프

• 방향 그래프 : 두 정점을 연결하는 간선에 방향이 존재하는 그래프 (간선 방향으로만 이동 가능)

• 가중치 그래프 : 두 정점을 이동할 떄 비용이 드는 그래프

• 완전 그래프 : 모든 정점이 간선으로 연결되어있는 그래프

그래프의 탐색

DFS (깊이 우선 탐색)

갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식.

{: width="50%" height="50%"}

BFS (넓이 우선 탐색)

시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 우선 방문하는 방법 (일반적으로 QUEUE 이용)

{: width="50%" height="50%"}

그래프에 관한 기본 개념에 대해 정리하였다. 다음 포스트에선 DFS와 BFS를 구현해보고 BOJ 문제 풀이로 익숙해지도록 연습해야겠다.