그래프와 인접행렬

들어가며

알고리즘 공부 중에 새롭게 알게 된 그래프와 인접행렬에 대해 작성했습니다.

개요

그래프는 트리와 다르게 계층이 아닌 서로에게 갈 수 있는 간선으로 이루어진 구조입니다.

Tree vs Graph

1. Tree = 비순환 방식 / Graph = 순환 / 비순환 모두 가능
2. Tree = 방향이 존재 / Graph = 방향은 선택 가능(시작점에 따라 다름)
3. Tree = 계층 모델 / Grpah = 네트워크 모델

관련 용어

• 순환
  - 순환이란 자기자신에서 출발하여 자기자신으로 들어올 수 있는 간선이 있는지를 의미합니다.
• 방향
  • 방향은 간선이 한쪽에서 다른 한쪽으로만 이동할 수 있는지를 의미합니다.
• 가중치
  • 가중치는 간선에 부여된 값으로, 거리, 시간, 비용 등 의미를 가집니다.

인접 행렬 vs 인접 리스트

그래프는 주로 아래의 두가지 방식으로 그래프의 연결관계를 나타냅니다.

인접 행렬

그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다.

인접 리스트

그래프의 연결 관계를 vector의 배열로 나타내는 방식입니다.

무방향 그래프

그래프

인접 행렬

	1	2	3	4	5
1	0	1	0	1	0
2	1	0	1	0	1
3	0	1	0	0	0
4	1	0	0	0	1
5	0	1	0	1	0

인접 리스트

간선 목록으로 표현 시

1: 2, 4
2: 1, 3, 5
3: 2
4: 1, 5
5: 2, 4

Java로 표현 시

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 4));
graph.put(2, Arrays.asList(1, 3, 5));
graph.put(3, Arrays.asList(2));
graph.put(4, Arrays.asList(1, 5));
graph.put(5, Arrays.asList(2, 4));

무방향 가중치 그래프

그래프

인접 행렬

	1	2	3	4	5
1	0	2	0	4	0
2	2	0	5	0	2
3	0	5	0	0	0
4	4	0	0	0	5
5	0	2	0	5	0

인접 리스트

간선 목록으로 표현 시

1: 2, 4
2: 1, 3, 5
3: 2
4: 1, 5
5: 2, 4

Java로 표현 시

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 4));
graph.put(2, Arrays.asList(1, 3, 5));
graph.put(3, Arrays.asList(2));
graph.put(4, Arrays.asList(1, 5));
graph.put(5, Arrays.asList(2, 4));

방향 그래프

그래프

인접 행렬

	1	2	3	4	5
1	0	1	0	1	0
2	0	0	1	0	1
3	0	0	0	0	0
4	0	0	0	0	1
5	0	0	0	0	0

인접 리스트

간선 목록으로 표현 시

1: 2, 4
2: 3, 5
3:
4: 5
5:

Java로 표현 시

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 4));
graph.put(2, Arrays.asList(3, 5));
graph.put(3, Collections.emptyList());
graph.put(4, Arrays.asList(5));
graph.put(5, Collections.emptyList());

가중치 방향 그래프

그래프

인접 행렬

	1	2	3	4	5
1	0	2	0	4	0
2	0	0	5	0	2
3	0	0	0	0	0
4	0	0	0	0	5
5	0	0	0	0	0

인접 리스트

간선 목록(가중치 포함)으로 표현 시

1: (2, 2), (4, 4)
2: (3, 5), (5, 2)
3:
4: (5, 5)
5:

Java로 표현 시

Map<Integer, List<int[]>> graph = new HashMap<>();
graph.put(1, Arrays.asList(new int[]{2, 2}, new int[]{4, 4}));
graph.put(2, Arrays.asList(new int[]{3, 5}, new int[]{5, 2}));
graph.put(3, Collections.emptyList());
graph.put(4, Arrays.asList(new int[]{5, 5}));
graph.put(5, Collections.emptyList());

마치며

읽어주셔서 감사합니다.

---

참고자료

[개요]

방향/무방향 그래프(Graph)의 정리
Difference Between Graph and Tree

[인접 행렬 vs 인접 리스트]

[그래프] 인접 행렬과 인접 리스트
Comparison between Adjacency List and Adjacency Matrix representation of Graph