[자료 구조] Java로 그래프 구현하기 :: 인접 행렬로 구현한 그래프

우리는 지난 시간에 그래프에 대해서 학습하였다.

 

이번에는 이론적인 그래프를 직접 Java를 이용하여 코드로 옮겨 보는 학습을 해볼 예정이다.

 

이와 같은 노드를 갖고 있는 그래프가 있다고 생각해보자.

 

지난 번에도 말 했듯이 그래프를 구현하는 방법에는 두 가지가 있다.

 

1. 인접 행렬
2. 인접 리스트

오늘은 인접 행렬로 그래프를 구현해볼 것이다.

인접 행렬

인접 행렬(adjacency matrix)이란 은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다.

출처 : 위키 백과

위키 백과에서는 인접 행렬에 대한 예로 다음과 같은 그림을 보여준다.

 

이 그림을 분석해보자면 1번 노드부터 6번 노드까지 연결되어 있는 노드에 1을 넣는 것이다.

 

그럼 아까 그렸던 그래프를 한 번 인접 행렬로 옮겨 보자.

 

위와 같은 상태로 노드가 6개이므로 6x6 표를 준비한다.

 

그리고 노드와 노드가 서로 연결되어 있는 상태를 1 연결되어 있지 않은 상태를 0으로 행렬을 채워보자.

 

이렇게 행렬을 채우면 인접 행렬을 그리는 것은 끝!

 

만약 간선에 가중치가 있다면 1이 아닌 가중치를 그리면 되는 것이다.

 

소스 코드로 옮겨보자.

 

이제 위에서 그린 그래프를 행렬로 변환시켜주는 그래프를 그려보자.

 

특징

그래프를 인접 행렬로 구현했을 때 장점이 있고, 단점이 있다. 우리가 v1과 v2에 대해서 검색을 할 때는 연결 리스트로 구현했을 때와 다르게 한 번에 접근할 수 있다는 점이 있다.

 

	특징	공간 복잡도
인접 행렬	특정 점점에 한 번에 접근할 수 있다.	v라는 간선의 수가 있을 때 O(V^2)