[문법] 그래프

그래프란?

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조

 

자료구조는 크게 비선형구조, 선형구조로 구분된다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형구조는 표현에 초점이 맞춰져 있다.

이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있다.

 

그래프에서 사용되는 용어

• 노드(Node): 연결 관계를 가진 각 데이터를 의미 . 정점(Vertex)이라고도 함.
• 간선(Edge): 노드 간의 관계를 표시한 선.
• 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

 

그래프의 종류

그래프는 유방향 그래프와 무방향 그래프 두가지가 있다.

유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.

무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖는다.

 

그래프의 표현 방법

1. 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
2. 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다. 그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 한다.

인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다.

따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 한다.

대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간을 사용하면 된다.