greenhelix
greenhelix
greenhelix
08-01 10:23
  • All (229)
    • Algorithm (118)
      • Algorithm (17)
      • Graph (0)
      • Core (6)
      • Python (18)
      • PythonSnippet (4)
      • Java (59)
      • Kotlin (14)
    • Project (0)
    • Study (8)
      • License (5)
      • EIP (3)
    • Programming (63)
      • Android (41)
      • Flutter (1)
      • Bugs Life (21)
      • Linux (0)
    • Tech (32)
      • Tech (17)
      • Drone (4)
      • Hacking (11)
    • Life (6)
      • INGRESS (1)
      • 심시티빌드잇 (0)
250x250

티스토리

hELLO · Designed By 정상우.
greenhelix

greenhelix

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

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

2021. 5. 12. 23:18

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


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

  • 인접 행렬
  • 인접 목록

 

1. 인접 행렬  Adjacency Matrix 

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

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

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

 

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

 

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

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

 

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

 

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

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

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

2. 인접 목록 Adjacency List

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

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

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

 

 

 

참고

위키

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > Algorithm' 카테고리의 다른 글

[프로그래머스] 수식 최대화  (0) 2021.07.06
불량사용자 - 카카오 코딩테스트  (0) 2021.05.06
Binary Search 이진 탐색 이분 탐색  (0) 2021.05.06
    'Algorithm/Algorithm' 카테고리의 다른 글
    • [프로그래머스] 수식 최대화
    • 불량사용자 - 카카오 코딩테스트
    • Binary Search 이진 탐색 이분 탐색
    • 🧩 코딩 테스트 정복기 @21#B*06
    greenhelix
    greenhelix
    개발에 관한 것들과 개인적인 것을 담는 블로그

    티스토리툴바