Graph에 대해서...

그래프는 tree 구조의 한 종류라고 생각하면 된다.

동그라미 처럼 되어있는 노드(버텍스)와 그것을 이어주는 선 엣지(브런치)라고 말한다.

왼쪽에 있는 건 방향 그래프이며 오른쪽에 있는건 무방향그래프이다. 말그대로 방향 표시가 있고 없고의 차이다.

무방향 그래프는 양방향 모두 이어져 있으며 방향그래프는 방향에 맞게만 이어져 있습니다. 

당연한거겠죠??? 

그럼 바로 그래프를 코드로 표현하는 두방법에 대해서 알아봅시다.

Adjacency Matxrix

노드간 연결관계를 이차원 배열로 표현한 것이다.

Adjacency list  

배열로 설정한다음 각 원소를 링크드 리스트로 표현한다.

총노드의 개수는 2m개 이므로 8개입니다.

 

그래프 탐색 기법에는 또 두가지가 있다 

1) 깊이 우선 탐색(DFS)

2) 너비 우선 탐색(BFS)