그래프란?

<aside> 🥕

연결 관계를 표현하는 자료구조

</aside>

![트리는 그래프에 속하는 하위개념

• 트리 : 계층 관계를 표현하는 자료구조, 사이클 형성 X, 상하 관계(부모-자식 관계) 존재
• 그래프 : 보다 일반적인 연결 관계를 표현하는 자료구조, 사이클 형성 가능, 상하 관계 X](attachment:4cc1343a-223f-4480-b274-dcdd74fe99d5:image.png)

트리는 그래프에 속하는 하위개념

• 트리 : 계층 관계를 표현하는 자료구조, 사이클 형성 X, 상하 관계(부모-자식 관계) 존재

• 그래프 : 보다 일반적인 연결 관계를 표현하는 자료구조, 사이클 형성 가능, 상하 관계 X

• 정점(데이터)를 간선(링크)로 연결한 형태의 자료구조

  • 정점(Vertex) : 그래프의 노드. 객체 하나 하나를 의미
  • 간선 or 링크(Edge) : 정점 간의 관계나 연결을 의미

그래프의 종류

• 그래프 = 연결관계를 표현하는 자료구조
  • 즉, 간선이 중요한 역할을 담당(간선이 연결관계를 표현하는 것이기 때문)
• 간선이 어떠한 형태로 정점을 연결하느냐에 따라 그래프의 종류가 달라짐(대표적으로 아래 4가지)
  • 무방향/방향 그래프
  • 무가중치/가중치 그래프
  • 연결/비연결 그래프
  • 서브 그래프

1. 무방향/방향 그래프

무방향 그래프

방향 그래프

• 무방향 그래프 : 두 정점을 연결하는 간선에 방향이 없는 그래프
  • 즉, 그냥 연결되어있다를 의미(무조건 양방향)
• 방향 그래프 : 두 정점을 연결하는 간선에 방향이 존재하는 그래프
  • 즉, 간선이 가리키는 방향으로만 이동 가능(단방향 or 양방향)

2. 무가중치/가중치 그래프

무가중치 그래프

가중치 그래프

• 가중치 그래프 : 간선에 가중치가 부여된 그래프
  • 비용 : 간선에 부여된 값인 가중치
  • 즉, 연결되어있다고 해도 비용에 차이가 있음
    • EX : 통행료의 차이, 거리의 차이 등등
• 무가중치 그래프 : 간선에 가중치가 부여되지 않은 그래프
  • 즉, 그냥 연결되어있음을 의미

3. 비연결/연결 그래프

G1 : 연결 그래프 G2 : 비연결 그래프(0에서 다른 정점으로 가는 경로가 없음) G3 : 비연결 그래프(0에서 2로 가는 경로가 없음)

• 연결 그래프 : 임의의 두 정점 사이를 잇는 경로가 있는 그래프
  • 아무 두 정점을 골라 경로를 확인했을 때, 경로가 있으면 연결 그래프
• 비연결 그래프 : 임의의 두 정점 사이를 잇는 경로가 없는 그래프
  • 아무 두 정점을 골라 경로를 확인했을 때, 경로가 없으면 연결 그래프