그래프

노드와 노드를 연결하는 엣지로 이루어진 비선형구조의 자료구조

• 노드(Node) : 데이터, 정점
• 엣지(Edge) : 노드들을 잇는 간선

그래프의 종류

무방향 그래프 : 두 노드를 연결하는 간선에 방향이 없는 그래프

방향그래프 : 간선에 방향성이 존재하는 그래프

가중치그래프 : 간선에 비용이나 가중치가 할당된 그래프

완전그래프 : 모든 노드가 간선으로 연결되어있는 그래프

연결그래프 : 무방향 그래프의 모든 노드 쌍에 대해 항상 경로가 존재하는 그래프
ex) 트리

비연결그래프 : 무방향 그래프에서 특점 노드 사이에 경로가 존재하지 않는 그래프

순환그래프 (Cycle) : 단순 경로에서 시작과 도착 노드가 동일한 그래프

비순환그래프 : 사이클이 없는 그래프

그래프의 구현 방법

1. 인접행렬 방식
   

그래프의 노드를 2차원 배열로 나타내는 것
노드들이 직접 연결이 되어있으면 1(true)을, 아니면 0(false)을 넣어 행렬을 완성시킴

• 인접리스트에 비해 구현이 쉬움
• 간선의 수와 무관하게 항상 n^2의 메모리 공간 필요
• 인접한 노드를 찾기 위해 모든 노드 순회해야 함 → 효율성 낮음
• 정점 간 관계 유무 파악 시 시간복잡도 O(1)

2. 인접리스트 방식
   

가장 일반적인 방식
모든 노드를 인접리스트에 저장해 인접한 정점들을 리스트로 표시한 것

• 인접행렬에 비해 구현이 어려움
• 연결 정보 탐색 시 시간복잡도 O(n)
• 인접행렬에 비해 공간 낭비가 적어 효율성 높음

그래프 탐색

: 하나의 정점으로 시작해 차례대로 모든 정점을 한 번씩 방문하는 것

탐색 알고리즘

1. 데이터 하나 읽기
2. 연결된 데이터 찾아서 큐 / 스택에 삽입
3. 큐 / 스택에 저장된 데이터 중 하나 꺼내기
4. 2, 3번을 반복

---

[참고]
프로그래머스 데브코스 강의, https://code-lab1.tistory.com/433