Swift) 그래프(Graph) 이해하기

 

 

 

안녕하세요!! 소들입니다 :)

오늘은 자료구조 중에서 그래프란 것에 대해 알아볼 것입니다!!

음 알고리즘 중에서 뭐

 

너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)

 

이런 것들 들어 보셨졍??

이것들이 모두 오늘 공부할 그래프라는 것을 순회하는 방식이에여 👀

따라서 그래프라는 것이 무엇인지, 정의부터 알고 갑시다!!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 그래프란?

 

그럼 도대체 그래프가 뭔데!!!

 

노드(정점)과 간선(브랜치)로 이루어진 자료구조로,

실생활의 현상이나 사물을 그래프로 활용할 수 있음

 

ㅇㅖ.......?

노드요? 간선이요? 이거 이진 탐색 트리할 때 공부했던 것들 아님?? 맞음!!

사실 트리도 그래프의 일종임!! 다만, 트리와 그래프는 성질이 좀 다름 (맨 나중에 설명하겠음)

 

실생활의 현상이나 사물을 그래프로 활용할 수 있단 말은,

내가 집에서 학교로 가는 방법엔 걸어가는 방법, 버스를 타는 방법, 지하철을 타는 방법

총 3가지가 있다면 그래프로는 다음과 같이 표현할 수 이씀

 

 

 

 

이런 식으로 노드와 간선을 이용한 그래프로 나타낼 수 있음!!!

그럼 이제 그래프에서 사용하는 용어에 대해 알아볼 것임 :)

 

 

 

 

2. 그래프 관련 용어

 

2-1. 필수로 알아두어야 하는 용어

 

 ① 노드(정점)  : 데이터가 저장됨

 

 

 

 ② 간선(branch)  : 노드를 연결한 선 

 

 

 

 ③ 인접 정점  : 간선에 의해 직접 연결된 노드 

 

 

 

집의 인접 접점은 걷기

걷기의 인접 접점은 학교

 

 

 

2-2. 참고로 이해하면 좋은 용어

 

◦ 단순 경로 : 반복되는 노드가 없는 경로 (같은 간선을 지나가지 않는 경로)

◦ 진입 차수 : 방향 그래프에서 외부 노드에서 들어오는 간선의 수

◦ 진출 차수 : 방향 그래프에서 한 노드에서 외부 노드로 향하는 간선의 수

◦ 경로 길이 : 경로를 구하기 위해 사용된 간선의 수

 

 

 

 

3. 그래프의 종류

 

3-1. 방향 그래프

 

 

 

간선에 방향이 있는 그래프로, 간선 그래프 방향으로만 갈 수 있음

(집 노드에서 도서관 노드로 갈 수 있고, 도서관 노드에선 집 노드로 갈 수 없음)

 

 

 

3-2. 무방향 그래프

 

 

 

간선에 방향이 없는 그래프로, 노드는 양방향으로 갈 수 있음

(집 노드에서 도서관 노드로 갈 수 있고, 도서관 노드에서 집 노드로 갈 수도 있음)

 

 

 

3-3. 가중치 그래프

 

 

 

노드를 이동할 때 드는 비용, 또는 가중치가 할당된 그래프

 

 

 

3-4. 완전 그래프

 

 

 

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

 

 

 

 

4. 그래프 표현 방법

 

이젠 데이터를 가지고 어떻게 그래프를 표현 하는지를 봐볼 것임 :)

 

 

 

4-1. 인접 행렬 그래프

 

 

 

그래프의 노드를 2차원 Int형 배열로 만들어서, 

이동할 수 있으면 1, 없으면 0으로 표기하는 것임!!!

 

 

장점	단점
- 직관적이며 쉽게 구현 가능하다 - 2차원 배열 안에 모든 노드들의 간선 정보를 담기 때문에, 두 노드에 대한 연결 정보를 조회할 때 O(1)이면 가능하다	- 모든 노드에 대한 간선 정보를 대입해야 하여, O(n²)의 시간 복잡도가 소요된다 - 무조건 2차원 배열이 필요하기 때문에 메모리 공간이 낭비된다

 

 

 

4-2. 인접 리스트 방식

 

 

 

주로 노드로 배열을 만들어서, 이들이 갈 수 있는 간선을 배열(혹은 연결 리스트)로 저장하는 것임

(노드의 데이터를 Key 값으로 해서 Dictionary로 만들고, Value를 간선들의 배열로 표현해도 됨)

 

 

장점	단점
- 필요한 정보만 저장하기 때문에 메모리를 절약할 수 있다 - 노드들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능하다 (n은 간선 갯수)	- 인접 행렬에 비해 구현이 비교적 어렵다 - 특정 두 노드가 연결 되었는지 확인하려면 인접 행렬에 비해 시간이 오래 걸린다

 

 

 

 

5. 그래프와 트리의 차이

 

위에서 트리는 그래프의 일종이라고 했음!!!

근데 완전 새로운 내용을 배우는 거 같지 않음????

이 노드와 간선으로 이루어져 있지만, 성질이 많이 다르기 때문임

 

 

	그래프	트리
정의	노드와 노드를 연결하는 간선으로 표현되는 자료 구조	그래프의 한 종류, 방향성이 있는 비순환 그래프
방향성	방향 그래프, 무방향 그래프 둘다 존재	방향 그래프만 존재
사이클	사이클 가능, 순환 및 비순환 그래프 모두 존재	비순환 그래프로 사이클이 존재하지 않는다
루트 노드	X	O
부모 / 자식 관계	X	O

 

 

그러하다 :)

 

 

 

 

 

.

.

.

그리 어렵진 않은데.....!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

이해가 안 가거나 피드백, 궁금증은 언제나 댓글.. 주세요!!!!!!!!!!!!!!!!!!!!!!

 

출처 : 

 

coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

 

m.blog.naver.com/occidere/220923695595

[그래프] 쉽게 쓴 그래프 알고리즘 기초 (2018.03.06 수정완료)