• 노드와 엣지로 구성된 집합
• 트리도 그래프의 일종

그래프의 표현

엣지 리스트

1. 엣지 리스트를 이용한 가중치가 없는 그래프 표현

   

   • 시작노드와 끝 노드를 기준으로 배열로 관리
   • 방향이 없는 경우 양방향 정보를 모두 저장하여 관리

2. 엣지 리스트를 이용한 가중치가 있는 그래프 표현

   

   • 특정 노드와 관련되어 있는 엣지를 탐색하기 쉽지 않음 → 벨만-포드나 크루스칼 알고리즘

인접 행렬

• 노드와 관련되어 있는 엣지를 탐색하려면 N 번 접근해야 하므로 노드 개수에 비해 엣지가 적을 때 공간 효율성이 떨어짐
• 노드 2번에 연결되어 있는 노드를 찾기 위해 N 번 찾아야 하므로 시간 복잡도도 높아짐

1. 인접 행렬로 가중치 없는 그래프 표현하기

   

2. 인접 행렬로 가중치 있는 그래프 표현하기

   

인접 리스트

1. 인접 리스트로 가중치 없는 그래프 표현하기

   

   • ArrayList 안에 배열로 관리 → 인덱스 접근 가능
   • 하나의 노드에 연결되어 있는 노드의 개수를 가변적으로 관리할 수 있음

2. 인접 리스트로 가중치 있는 그래프 표현하기

   

   • 가중치가 있을 경우 직접 객체를 선언해야 함
   • 빈 공간이 없기 때문에 시간 복잡도, 공간 복잡도 모두 뛰어남

유니온 파인드

• 그래프의 사이클이 생성되는지 판별하는 알고리즘
• 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘

유니온 파인드의 원리 이해하기

1. 초기화

   • 1차원 배열 이용
   • 처음에는 각 노드가 모두 대표 노드이며 배열은 자신의 인덱스 값으로 초기화

   

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산 수행