비선형 구조(2) - 그래프

💡 그래프(Graph)의 개념

• 그래프는 노드(N; Node)와 노드를 연결하는 간선(E; Edge)을 하나로 모아 놓은 자료 구조이다.
• 트리(Tree)는 사이클이 없는 그래프이다.

📍 그래프의 유형

➡️ 방향성의 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.

 

📌 방향 그래프

• 정점을 연결하는 선에 방향이 있는 그래프
• n개의 정점으로 구성된 방향 그래프의 최대 간선 수는 n(n-1)

방향 그래프

 

📌 무방향 그래프

• 정점을 연결하는 선에 방향이 없는 그래프
• n개의 정점으로 구성된 무방향 그래프의 최대 간선 수는 n(n-1)/2

무방향 그래프

 

📍 그래프 용어

용어	설명
경로(Path)	임의 정점에서 다른 정점으로 이르는 길
경로 길이(Path Length)	경로상 있는 간선의 수
단순 경로(Simple Path)	한 경로의 모든 간선이 다를 때의 경로
사이클(Cycle)	동일 정점에서 시작과 끝이 이어지는 경로

 

📍 그래프 탐색 방법

탐색 방법	설명
깊이 우선 탐색 (DFS; Depth-First Search)	최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동
너비 우선 탐색 (BFS; Breadth-Frist Search)	최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

한 눈에 알아보기!!