[Swift] 그래프(Graph)

이 글은 개인적인 공부를 위해 작성하는 것임을 밝힙니다.

자세한 내용은 https://babbab2.tistory.com/105 을 방문해주세요!

그래프

그래프 자료구조

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

연결되어있는 원소간의 관계를 표현한 자료구조

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

알고 있어야 할 그래프 관련 용어

노드(정점)

컴퓨터 과학에 쓰이는 기초적인 단위

즉, 위의 그림에서는 동그라미 하나가 노드다.

그래프에서 노드는 대응하는 개체를 나타내는 정점이다.

간선(브랜치)

객체 사이를 잇는 연결

경우에 따라 노드 사이를 잇는 각 연결의 강도를 나타내는 가중치를 갖는다.

인접 정점

간선에 의해 직접 연결된 노드

위의 그래프 그림에서 1의 인접 정점은 5와 2, 6의 인접 정점은 4

참고로 이해하면 좋은 용어

단순경로

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

진입 차수

방향 그래프에서 외부 노드에서 들어오는 간선의 수

진출 차수

방향 그래프에서 한 노드에서 외부 노드로 향하는 간선의 수

경로 길이

경로를 구하기 위해 사용된 간선의 수

 

그래프의 종류

방향 그래프

방향 그래프

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

 

무방향 그래프

무방향 그래프

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

 

가중치 그래프

가중치 그래프

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

 

완전그래프

완전 그래프

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

 

그래프 표현 방법

인접 행렬 그래프

출처: https://babbab2.tistory.com/105

그래프의 노드를 2차원 Int형 배열로 만들어서 이동할 수 있으면 1, 없으면 0으로 표기한다.

 

장점 : 직관적이며 쉽게 구현 가능, 2차원 배열이므로 두 노드에 대한 연결 정보를 조회할 때 O(1)으로 조회 가능

단점 : 모든 노드에 대한 간선정보를 대입하는 과정에서 O(n^2)의 시간복잡도가 소요되고, 메모리 공간이 낭비된다.

 

인접 리스트 방식

출처: https://babbab2.tistory.com/105

주로 노드로 배열을 만들어서 이들이 갈 수 있는 간선을 배열 또는 연결리스트로 저장하는 것이다.

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

 

장점 : 필요한 정보만 저장하므로 메모리 절약이 가능, 노드의 연결정보를 탐색할 때 O(n)의 시간이면 가능하다. (n: 간선의 수)

단점 : 인접 행렬에 비해 구현이 어렵다. 특정 두 노드가 연결되었는지 확인하려면 인접 행렬에 비해 시간이 오래걸린다.

 

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