[자료구조] 그래프에 대해 알아보자

 

 

 

 

 

 

📚 그래프 정의

 

그래프는 연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 비선형 자료구조이며,
노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조이다.

 

그래프는 TCP 라우팅 알고리즘과 페이스북 관계망 등에서 자주 쓰이는 자료구조이다.

 

 

🧬 그래프 구조

 

 

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

 

📝 그래프 표현 방법

 

 

그래프를 코드로 표현하는 방법은 LinkedList와 Array가 있는데

 

☝ LinkedList는 각 정점간의 관계를 노드로 연결하여 표현한다.
head를 3으로 가리킨 후 계속 다음 데이터를 가리키는 쪽으로 따라가면

1, 2, 5 번이 있다는 것을 알 수 있다.  

위에 사진을 예로 들면 3번과 연결되어 있는 정점들을 보려면

서로 연결된 정점끼리 노드로 연결되어 있는 것이다.

 

 

 

☝ Array는 각 정점 간의 관계를 이차원 배열로 나타내

서로 연결되어 있으면 1(True)을

서로 연결되어 있지 않으면 0(False)으로 나타낸다

 

위에 사진을 예로 들면 정점 1번에서 정점 2번간의 관계를 보려면

인덱스 [0][1] = 1 (1번에서 2번으로 연결되어 있음)

인덱스 [1][0] = 0 (2번에서 1번으로 연결되어 있지 않음)

를 보면 된다.

 

 

LinkedList는 Array보다는 공간복잡도가 적은 대신 데이터 탐색 시간복잡도는 크지만

Array는 LinkedList보다는 데이터 탐색 시간복잡도는 작지만 공간복잡도가 크다