자료구조

그래프

뚜sh뚜sh 2024. 3. 5. 21:13

그래프

  • 객체들의 집합과 이 객체들을 연결하는 선들의 집합으로 이루어진 수학적 구조이다.
  • 그래프는 정점(Vertex) 또는 노드(Node)라고 불리는 객체들과, 이 정점들을 연결하는 간선(Edge) 또는 링크(Link)로 구성된다.
  • 그래프는 복잡한 관계나 네트워크를 모델링하는 데 유용하다.

 

 

 

그래프의 기본 용어

  • 정점(Vertex) : 그래프의 기본 단위로, 위치를 나타낸다. 때로는 노드(Node)라고도 한다.
  • 간선(Edge) : 두 정점을 연결하는 선이다. 간선은 방향이 있거나 없을 수 있다.
  • 방향 그래프(Directed Graph) : 간선에 방향성이 있는 그래프. 간선이 (A, B)라면, A에서 B로의 연결을 나타낸다.
  • 무방향 그래프(Undirected Graph) : 간선에 방향성이 없는 그래프. 간선이 A와 B를 연결한다면, A에서 B로, B에서 A로의 양방향 연결이 모두 가능하다.
  • 가중치(Weight) : 간선에 부여된 비용 또는 가중치. 거리, 시간, 비용 등을 나타낼 수 있다.
  • 경로(Path) : 정점들의 연속적인 순서로, 각 정점은 간선으로 연결된다. 경로는 시작 정점에서 끝 정점까지의 연결을 나타낸다.
  • 사이클(Cycle) : 시작 정점과 끝 정점이 같은 경로. 무방향 그래프에서는 간선의 순서를 고려하지 않지만, 방향 그래프에서는 방향을 고려한다.

 

 

 

그래프의 종류

  • 단순 그래프(Simple Graph) : 루프(자기 자신으로 연결된 간선)와 다중 간선(동일한 두 정점을 연결하는 간선이 여러 개 있는 경우)이 없는 그래프.
  • 다중 그래프(Multigraph) : 두 정점 사이에 두 개 이상의 간선이 허용되는 그래프.
  • 완전 그래프(Complete Graph) : 그래프의 모든 쌍의 정점이 서로 연결된 그래프. 개의 정점을 가진 완전 그래프는 개의 간선을 가집니다(무방향 그래프의 경우).
  • 연결 그래프(Connected Graph): 모든 정점 쌍 사이에 경로가 존재하는 그래프(무방향 그래프의 경우). 방향 그래프에서는 강하게 연결된 그래프(Strongly Connected Graph)와 약하게 연결된 그래프(Weakly Connected Graph)로 나뉜다.
  • 트리(Tree): 사이클이 없는 연결된 무방향 그래프. 트리는 정확히 n개의 간선을 가진 개의 정점을 가진다.

 

 

 

 

 

 

연결된 그래프(Connected Graph)

  • 그래프 내의 모든 정점 쌍 사이에 경로가 존재하는 그래프를 의미한다.
  • 즉, 그래프의 어떤 두 정점을 선택해도, 그 두 정점을 연결하는 간선들의 시퀀스(경로)가 반드시 존재한다는 것을 의미한다.

 

 

 

연결된 그래프의 특징

  • 단일 컴포넌트 : 연결된 그래프는 단 하나의 컴포넌트로 이루어져 있으며, 이는 그래프의 모든 정점이 서로 연결되어 있음을 의미한다.
  • 경로의 존재 : 모든 정점 쌍 사이에는 적어도 하나의 경로가 존재한다.
  • 사이클의 가능성 : 연결된 그래프는 사이클을 포함할 수 있다. 사이클의 유무는 그래프가 트리(사이클이 없는 연결된 그래프)인지 아니면 일반적인 연결 그래프인지를 결정한다.

 

 

 

연결된 그래프의 유형

1. 단순 연결된 그래프(Simply Connected Graph)

  • 어떤 두 정점 사이에도 정확히 하나의 단순 경로(같은 정점을 두 번 이상 지나지 않는 경로)만 존재하는 그래프이다.
  • 모든 트리는 단순 연결된 그래프의 한 예이다.

2. 강하게 연결된 그래프(Strongly Connected Graph)

  • 방향 그래프에서 사용되는 개념으로, 모든 정점 쌍 사이에 양방향으로 경로가 존재하는 그래프를 의미한다.
  • 즉, 그래프의 모든 정점에서 다른 모든 정점으로 이동할 수 있는 경로가 있어야 한다.

 

 

 

비연결 그래프(Disconnected Graph)

  • 최소한 하나의 정점 쌍 사이에 경로가 존재하지 않는 그래프이다.
  • 비연결 그래프는 두 개 이상의 독립적인 컴포넌트로 구성될 수 있으며, 각 컴포넌트는 연결된 그래프일 수 있다.

 

 

그래프의 표현

그래프를 구현하는 3가지 방법(에지 리스트, 인접 행렬, 인접 리스트)을 알아보자.

 

 

 

에지 리스트

  • 에지 리스트는 에지를 중심으로 그래프를 표현한다.
  • 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.
  • 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
  • ex) 가중치가 없는 경우 - A[N][2] = {{1, 2}, {3, 4}} => 1에서 2로 뻗는 에지 + 3에서 4로 뻗는 에지
  • ex) 가중치가 있는 경우 - A[N][3] = {{1, 2, 8}, {3, 4, 2}} => 1에서 2로 향하며 가중치가 8인 에지 + 3에서 4로 향하며 가중치가 2인 에지
  • 에지 리스트는 구현하기 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다.
  • 에지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

 

 

 

인접 행렬

  • 인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
  • 인접 행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.
  • ex) 가중치가 없는 경우 - 1에서 2를 향하는 에지 => 1행 2열에 1을 저장(가중치가 없기 때문에 1을 저장)
  • ex) 가중치가 있는 경우 - 1에서 2를 향하며 가중치가 8인 에지 => 1행 2열에 8을 저장
  • 인접 행렬을 이용한 그래프 구현은 쉽고 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 것이 장점이다.
  • 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
  • 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다.(노드가 3만 개가 넘으면 자바 힙 스페이스 에러가 발생)

 

 

 

인접 리스트

  • 인접 리스트는 ArrayList로 그래프를 표현한다.
  • 노드 개수만큼 ArrayList를 선언한다.
  • 인접 리스트에는 N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼의 배열을 연결하는 방식으로 표현한다.
  • ex) 가중치가 없는 경우 - 노드 1과 연결된 2, 3 노드 => ArrayList[1]에 [2, 3]을 연결
  • ex) 가중치가 있는 경우 - (도착 노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용 => ArrayList[1]에 [(2, 8), (3, 3)]을 연결
  • 다른 방법에 비해 구현은 복잡한 편이지만, 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.