코딩테스트 - 그래프

그래프란, 자료구조의 하나로 정점(vertex 혹은 node)와 간선(edge)로 이루어져 있다.

• 그래프 관련 용어

용어	뜻
정점	데이터를 저장하는 위치
간선	정점을 연결하는 선
인접 정점	간선으로 연결되어있는 정점
단순 경로	경로 중에서 반복되는 정점이 없는 경우 한붓그리기와 같이 중복된 간선을 지나지 않는 경로
경로길이	경로를 구성하는 데 사용한 간선의 수
사이클	경로의 시작 정점과 종료 정점이 일치하는 경우

1. 무방향 그래프
   정점을 연결하는 간선에 방향이 없는 그래프

2. 방향 그래프
   간선에 방향이 있는 그래프

3. 가중치 그래프
   간선에 가중치가 할당되는 그래프

4. 완전 그래프
   한 정점에서 다른 모든 정점과 연결되어 있어서 간선이 최대를 갖는 그래프

5. 연결 그래프
   떨어져 있는 정점이 없는 그래프

6. 단절 그래프
   떨어져 있는 정점이 있는 그래프

7. 구현 방법
   파이썬에서 그래프를 구현하는 방법에 대해서 설명하려 한다. 공부를 해보니 크게 인접 행렬과 인접 리스트 방법이 있는 것 같다.

• 인접 행렬
  그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 간선이 있으면 1, 없으면 0으로 표현한다.

장점은 구현이 쉽다는 점이다. 하지만 단점으로는 배열을 만드는 과정에서 시간이 오래 걸린다. 항상 2차원 배열의 형태로 구현되므로 메모리 낭비가 크다고 한다.

• 인접 리스트
  장점은 필요한만큼(연결된 만큼)만 공간을 사용하므로 메모리 낭비가 적다. 두 정점의 연결여부를 확인하기 위해서 오래걸린다. 구현이 인접 행렬에 비해 어렵다.

인접 행렬과 인접 리스트를 코드로 구현하는 것에는 여러 방법이 있을 지도 모르겠다.
나는 python에서 인접 행렬은 이차원 리스트로 구현하고, 인전 리스트는 딕셔너리로 구현한다.