오늘 배운 것

자료 구조

1. Graph

그래프는 정점(vertex 또는 node)과 vertex와 vertex를 연결하는 간선(edge)로 구성되는 자료구조이다.

• 그래프는 서로 다른 정점(Vertex) 간에 여러 개의 간선(Edge)가 존재할 수 있다.
• 그래프는 방향성을 띄고 있는지에 따라 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉜다.
  • 방향 그래프(Directed Graph)의 정점 E의 경우, 2개의 진입 차수(In-degree)와 2개의 진출 차수(Out-degree)를 갖는다. 정점 B는 정점 E로 접근 할 수 있다. 하지만 반대는 가능하지 않다.(비대칭)
  • 무방향 그래프(Undirected Graph)의 정점 E의 경우, edge의 방향이 없기 때문에 단순히 4개의 차수(Degree)를 갖는다. 정점 B는 정점 E로 접근 할 수 있다. 또한 반대의 경우도 가능하다.(대칭)
• 트리(Tree)는 그래프의 특수한 형태이다. 트리는 하나의 부모 노드에서 아래 방향으로 내려오는 그래프인데, 이는 루트가 있고 진입 차수가 1인 방향 그래프라고 표현할 수도 있다. 아래의 비교표를 참고하자.

• 그래프의 구현은 크게 두 가지로, 인접 행렬 방식(Adjacency Matrix)과 인접 리스트 방식(Adjacency List)이 있다.

  • 인접 행렬 방식은 이차원 배열을 사용해 구현할 수 있다.
    • 두 정점을 연결하는 간선의 존재여부를 확인할 때 시간 복잡도는 O(1)이다. M[i][j](배열 =M, 확인하고자 하는 정점 = i, j)
    • 간선의 추가 삭제는 O(1)이다.
    • 정점의 차수를 확인 할 때의 시간 복잡도 O(N)이다. 인접 배열의 i번 째 행이나 열을 모두 더하면 된다.
    • 그래프에 존재하는 모든 간선을를 탐색할 때의 시간 복잡도는 O(N^2)이다. 따라서 정점의 수가 많아지면 많아질수록 복잡도는 기하급수적으로 늘어난다.
    • 따라서 정점의 추가 삭제가 적고, 간선의 추가 삭제가 많은 경우에 인접행렬방식을 이용하도록 하자.

• 인접 리스트 방식은 연결 리스트(Linked List)를 사용해 구현할 수 있다.

  • 두 정점을 연결하는 간선의 존재여부, 혹은 정점의 차수를 확인할 때의 시간 복잡도는 O(E)다. (E = 해당 정점의 차수)
  • 간선의 추가삭제 O(1)이나, 최악의 경우 O(E)이다.
  • 그래프에 존재하는 모든 간선을 탐색할 때 시간복잡도는 O(N+E)이다. (모든 정점(N)과 해당 정점의 인접리스트(E)탐색), 정점의 추가 삭제 패널티가 그리 크지는 않다.
  • 따라서 정점의 추가 삭제가 비교적 빈번한 경우 인접행렬방식보다는 인접리스트방식을 사용하도록 하자.