[자료구조] 그래프(Graph)

정의

정점과 두 정점을 잇는 간선으로 이루어진 자료구조. 자료 사이의 연결 관계를 설정해야 하는 상황에서 유용하게 활용된다.

 

특징

• 방향성 : 방향성의 유무에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉜다.
  • 무방향 그래프의 간선이 양방향 도로라면, 방향 그래프의 간선은 일방통행 도로이다.
  • 즉, 방향 그래프에서 A  -> B로의 간선이 있다면 B <- A로는 갈 수 없다.
• 차수(Degree) : 한 정점이 가진 간선의 개수.
  • 방향성 그래프에서는 나가는 방향인 진출차수(Outdegree), 들어오는 방향인 진입차수(Indegree)로 나뉜다.
• 사이클(Cycle) : 임의의 한 정점에서 출발해 자기 자신에게 돌아올 수 있는 경로가 있는지 여부에 따라 순환 그래프(Cycle Graph)와 비순환 그래프(Acyclic Graph)로 나뉜다.

 

종류

• 완전 그래프(Complete Graph) : 모든 정점 쌍들이 각각 간선으로 연결된 그래프. 한 정점이 다른 모든 정점과 연결되어 있다.
• 연결 그래프(Connected Graph) : 임의의 두 정점 사이에 경로가 항상 존재하는 그래프. 똑 떨어진 정점이 없다.
• 단순 그래프(Simple Graph) : 두 정점 사이의 간선이 1개 이하이고 루프(본인에서 출발해 본인으로 돌아오는 간선)가 존재하지 않는 그래프

 

표현법  < 정점 V(vertex), 간선 E(edge)>

• 인접 행렬 : V x V 의 2차원 행렬을 사용해 연결된 두 정점은 1로, 연결되지 않은 두 정점은 0으로 그래프를 표현하는 방법.
  • 어떤 두 점의 연결 여부를 O(1)에 알 수 있다. 가로 세로가 각각 V인 2차원 배열이 필요하므로 O(V^2)의 공간이 필요하다.
  • 어떤 점에 연결된 모든 정점의 목록을 알아내는 데 O(V)가 걸린다.
  • 때문에 두 점의 연결 여부를 자주 확인하고, 간선이 매우 많을 때 (E가 V^2에 가까울 때) 효율적이다.
• 인접 리스트 : V개의 리스트를 사용해 각 리스트에 자신과 연결된 정점을 넣어 그래프를 표현하는 방법.
  • 정점과 간선의 개수만큼 공간을 차지한다. 즉 총 O(V+E)의 공간이 필요하다.
  • 특정 정점에 연결된 모든 정점을 자주 확인하고, 정점이 많고 간선이 상대적으로 적은 상황(E << V^2)에서 효율적이다.