Undirected Graph Adjacency List, Matrix:: 무 방향 그래프, 인접 목록, 행렬

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보, 잡지식을 꾸준히 쌓아가는 글입니다. 출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ 

---

무방향 그래프를 나타내는 두 가지 방법이 있다. ( 방향이 없는 그래프 ) 

• 인접 행렬
• 인접 목록

 

1. 인접 행렬  Adjacency Matrix 

그래프 이론에서 어느 꼭짓점들이 변으로 연결되어있는지 나타내는 ㅎㅎㅎㅎ정사각형 행렬(노드의 갯수 x 노드의 갯수)입니다. 

연결 행렬이라고도 합니다.

그래프에서 방향이 지정되지 않은 경우 인접 행렬은 대칭이다. 

 

1과 0으로 노드들의 연결 관계를 표현한다. ( True 와 False로 표현하기도 한다.) 

 

즉, 인접 행렬에서 간선인 경우 matrix(i, j) = 1이고 선이 없다면, matrix(i, j) = 0이 된다. 

무방향, 방향이 따로 없는 그래프에서는 당연히 연결 표현들이 다 대칭으로 구성됩니다. 

 

예를 들어  ( 1, 0 ) 의 간선이 있다면, 반드시 ( 0, 1 ) 의 간선도 있다는 뜻이다. 

 

그래프가 밀집되어있거나 간선이 많은 경우 인접행렬은 간단하게 표현이 가능하다. 

데이터 구조 등에 많이 활용되기도 한다. 

행렬을 사용하기 때문에, 인접 행렬을 통해서 몰랐던 중요 인사이트를 얻을 수 있다. 

2. 인접 목록 Adjacency List

인접 목록의 경우 아래와 같은 형태로 만들어진다. 

dict()메서드를 이용하여 이런 식으로 표현된다. 

가독성도 뛰어나고 훨 활용도가 높긴하다. 

 

 

 

참고

위키