그래프(Graph)의 개념과 특징을 이해할 수 있다.

Goal

  • 그래프(Graph)의 기본 개념을 이해한다.
  • 그래프(Graph)의 종류를 구분할 수 있다.
  • 그래프(Graph)의 특징을 이해할 수 있다.

그래프(Graph)의 개념

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

그래프와 트리의 차이

참고

그래프(Graph)와 관련된 용어

그래프(Graph)의 특징

그래프(Graph)의 종류

무방향 그래프 VS 방향 그래프

가중치 그래프

연결 그래프 VS 비연결 그래프

사이클 VS 비순환 그래프

완전 그래프

그래프(Graph)의 구현 2가지

1. 인접 리스트(Adjacency List)

인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법 이다.

2. 인접 행렬(Adjacency Matrix)

인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻이다.

인접 리스트와 인접 행렬 중 선택 방법

그래프(Graph)의 탐색

일반적인 방법 두 가지:
깊이 우선 탐색(Depth-First Search)너비 우선 탐색(Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

관련된 Post

References