[그래프 이론] 알고리즘 - 그래프 이론 (Graph)

그래프 이론 알고리즘 

정점들과 간선들로 이루어진 집합을 "그래프"라고 한다.

그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 표현한다.

 

 

 

그래프의 종류

• 트리 : 부모, 자식 계층 구조를 가진다. (특징 : 간선 수 = 노드 수  - 1)
• 이진트리  : 각 노드의 자식 노드 수가 2개 이하로 구성되어 있는 트리를 의미한다.

정 이진 트리	자식 노드가 0 또는 2개인 이진 트리를 의미 한다.
완전 이진 트리	왼쪽부터 채워져 있는 이진트리, 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있다.
변질 이진 트리	자식 노드가 하나밖에 없는 이진 트리를 의미한다.
포화 이진 트리	모든 노드가 꽉 차 있는 이진 트리를 의미한다.
균형 이진 트리	모든 노드의 왼쪽 하위 트리와 오른쪽 하위트리의 차이가 1이하인 트리이다. Ex) 레드 블랙 트리

 

• 이진 탐색 트리 : 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 포함되고 왼쪽 하위트리에는 노드의 값보다 작은 값이 들어 있는 트리를 의미한다. => 왼쪽에는 작은 값, 오른쪽에는 큰 값으로 구분되어 있어 검색에 용이하다.
• 이진 탐색트리의 시간 복잡도 : O(logN)

 

 

그래프의 구현과 탐색 방법

1. 인접 행렬(Adjacency Matrix) : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
2. 인접 리스트(Adjacency List) : 리스트로 그래프의 연결관계를 표현하는 방식

 

 

1. 인접 행렬

• 그래프에서 정점과 간선의 관계를 나타내는 Bool Type의 정사각형 행렬을 말한다.
• 0은 두 정점 사이의 경로가 없음을 의미하며 1은 두 정점 사이의 경로가 있음을 의미한다.

• 위의 무방향(양방향) 그래프를 인접 행렬로 표현하면 아래와 같다.

	0	1	2	3
0	0	1	0	1
1	1	0	1	1
2	0	1	0	0
3	1	1	0	0

장점 : 2차원 배열에 모든 노드들의 간선 정보가 있기 때문에, 두 노드를 연결하는 간선을 조회할 때 O(1)의 시간 복잡도를 가진다.
단점 : 간선의 수와 무관하게 항상 n^2크기의 2차원 배열이 필요하므로 메모리 낭비가 심하다. 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n^2)의 시간이 소요된다.

 

 

 

2. 인접 리스트

• 그래프의 각 노드에 인접한 노드들을 연결리스트(Linked List) 로 표현하는 방법이다.
• 노드의 개수만큼 인접 리스트가 존재하며 각 인접 리스트에는 인접한 노드 정보가 저장된다.
• 그래프는 각 인접 리스트에 대한 헤드 포인터를 배열로 갖는다.
• 위의 무방향(양방향) 그래프를 인접 리스트로 표현하면 아래와 같다.

장점 : 존재하는 간선만 관리 -> 메모리 사용이 효율적이다.
단점 : 두 노드를 연결하는 간선을 조회하거나, 노드의 차수를 조회하기 위해서는 노드의 인접 리스트를 탐색해야 하므로 노드의 차수만큼 시간이 필요하다.

 

인접 행렬 VS 인접 리스트 

	인접 행렬	인접 리스트
간선 (u, v) 검색	O(1)	O(degree(v))
정점(v)의 차수 계산	O(n)	O(degree(v))
전체 노드 탐색	O(n^2)	O(e)
메모리	n*n	n+2
구현	쉬움	어려움

전체 정점 개수 : n

전체 간선 개수 : e

 

 

그래서,

그래프가 희소할 때는 인접리스트, 조밀할 때에는 인접 행렬이 좋다.
: 그래프가 희소할 때 인접 행렬이 인접 리스트보다 메모리를 더 많이 사용해야한다. 간선이 없어서 인접행렬의 대부분의 요소가 0인데도 2차원 배열을 만들게되면 해당 부분을 포함하여 2차원 배열이 만들어지기 때문이다.
: 그래프가 조밀할 때 인접행렬이 인접 리스트보다 좋다. 대부분의 노드가 연결되어 있기 때문에 메모리의 낭비가 없이 효율성은 동일해지고 정점 i에서 정점 J 까지의 간선이 있는지 확인하는 속도가 더 빠르기 때문에 인접 행렬이 더 빠르다

 

 

---

그래프 문제 LV3

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

풀이

https://h-castle.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%EB%A8%BC-%EB%85%B8%EB%93%9C-by-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EA%B7%B8%EB%9E%98%ED%94%84-bfs

[프로그래머스] 가장 먼 노드 by 파이썬(Python) : 그래프 bfs