[DS] 그래프(Graph) / 트리(Tree)

그래프, 트리

노드의 관계를 저장하는 자료구조이다.

일반적으로 탐색을 하기 위해선 반복문같은 프로그래밍 문법이 아니라 (for, while..)

DFS-깊이탐색,BFS-너비탐색 알고리즘을 사용해야한다

 

 

 

트리 (Tree)

트리는 노드가 나무 가지처럼 연결괴어 있는 비선형 자료구조이다.

마치 나무를 뒤집어 놓은 모습과 유사하다.

트리 내 또 다른 하위 트리가 있고, 그 안에 또 다른 하위 트리가 있는 재귀적인 구조를 가진다.

컴퓨터의 디렉토리 구조가 트리 구조이다.

보통 최상단 노드를 RootNode(뿌리 노드), 나머지 노드를 LeafNode(잎 노드) 라고 한다.

 

 

그래프 (Graph)

그래프는 노드와 노드를 연결하는 간선을 모아놓은 자료구조이다.

트리와 많이 비교가 되는데 트리 역시 그래프의 형태이나, 그래프는 방향이 있거나, 없을 수 있으며,

루트 노드라는 개념이 없다. 또한 사이클이 가능한 형태로 구성되어있다.

 

순회를 하는 방법

DFS, BFS 알고리즘 사용

 

 

그래프를 표현할 떄는 인접행렬과 링크드리스트를 사용하는 방식이 있따.

보통 알고리즘 문제를 푸는데 있어서는 인접행렬을 활용한 방식을 많이 사용한다.

 

 

 

 

인접행렬

PS의 경우 인접행렬을 사용하는게 유리하지만 실무에서는 링크드리스트로 만드는게 보통일거같다.

다음은 인접행렬을 이용해 그래프를 표현하고 1번 노드가 연결되어있는 다른 노드의 종류를 표현하는 예제이다.

0번은 2번 노드만 갈수있고

1번은 0번,2번,3번 노드를 갈수있다

2번은 1번 노드만 갈수있다.

3번은 아무 노드도 갈수없다.

4개의 노드가 갈수있는 최대가 4개이니 4x4 2차원 배열이 필요하다.

 

그럼 노드를 입력받고 그 노드가 갈수있는 노드를 모두 출력해보자

ex) 입력 1, 출력 0번노드 1번노드 3번노드

 

 

코드

 

출력결과

 

 

 

가중치가 있는 그래프

연습문제 : 각 노드가 갈수 있는 노드번호와 비용을 출력을 전부 해보자.

 

 

코드

 

 

출력결과