그래프(비선형자료구조)

그래프

• 데이터사이에 인접한 정보를 저장하는 자료구조
• 노드와 노드 사이를 연결하는 엣지로 이루어진 자료 구조
• 방향이 있는 그래프와 방향이 없는 그래프로 구분

 

1. 방향이 없는 그래프(Undirected Graph)

• 차수 : 자신의 이웃 개수
• 서브그래프 : 오리지널 그래프에서 일부 edge와 노드를 구분해서 가져온 것
• 경로 : 두 개 이상의 노드가 서로 연결된 엣지들의 집합. 간선의 방향이 없으므로 각 노드는 양 방향으로 연결
  • trivial path : 노드 자신만으로 이루어진 경로 (경로가 0)
  • 단순 경로 (simple path) : 처음과 끝을 제외하고 중복이 없는 경로
  • 사이클 (cycle) : 시작 노드와 끝 노드가 같은 경로
  • 단순 사이클 (simple cycle) : simple path를 만족하고 처음과 끝 노드가 같은 경로
  • 연결 요소 (connected component) : 연결된 그래프를 구성하는 서브그래프 중에서, 두 노드 사이에 경로가 존재하는 부분 그래프 
    • ex)두 개의 연결요소로 이루어진 그래프
      • [[0, 1, 2], [3, 4]]  => 연결요소는 [0, 1, 2]와 [3, 4]다.
  • 연결 그래프 (connected graph) : 하나 이상의 정점이 있고, 연결요소가 한 개인 그래프
  • 가중 그래프(weighted graph) : 엣지에 가중치 또는 비용을 할당한 그래프

 

트리와 그래프, 뭔가 비슷하다?

트리도 그래프의 한 종류입니다.

그러므로

connected graph를 만족하고 모든 경로가 유일하다면 그래프도 트리가 될 수 있습니다.

 

2. 방향이 있는 그래프

• 각각의 엣지가 방향을 가지고 있는 그래프
• 차수 :
  • indegree : 특정 노드로 들어오는 엣지의 개수 
  • outdegree : 특정 노드에서 나가는 엣지의 개수 
    • 위 그림을 예로 들면
    • v1의 indegree = 0
    • v4의 indegree = 2
    • v1의 outdegree = 1
    • v9의 outdegree = 1
  • sources : indegree가 0인 노드
  • sink : outdegree가 0인노드
• 경로 : 방향을 고려한 경로여야 한다.
  • 강한 연결성 (strongly connected) : 방향성을 고려했을 때 모든 경로가 존재하는 경우
  • 약한 연결성 (weakly connected) : 방향성을 고려하지 않았을 때에만 모든 경로가 존재하는 경우

• directed acyclic graphs(DAG) : 방향은 있지만 사이클이 존재하지 않는 그래프

 

 

그래프를 표현하는 방법

• Binary-relation list
  • 엣지들을 일렬로 나열한 것
  • 저장하려면 엣지 개수만큼 메모리가 필요
  • 두 노드 사이에 엣지가 있는지 체크하기 위해 최대 엣지개수만큼의 시간복잡도가 존재
  • 노드의 이웃을 찾기위해서도 엣지 수 만큼 탐색 해야함
• 인접 행렬 (Adjacency matrix)
  • 저장하려면 노드의 제곱개수 만큼의 메모리가 필요
  • 노드의 이웃을 찾기위해서 노드개수만큼의 시간복잡도 존재
  • 두 노드 사이에 엣지가 있는지 체크하기 위해서는 O(1)이 걸림
• 인접 리스트 (Adjacency list)
  • 일반적으로 알고리즘에서 가장 많이 사용하는 그래프 표현법
  • 노드 + 엣지개수 만큼의 메모리가 필요