🚀 What I Will Learn

• 그래프(Graph)의 개념에 대해 이해하기

그래프(Graph)란? 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

---

그래프(Graph)

✔️ 그래프(Graph)와 관련된 용어

• 정점(vertex): 위치라는 개념. (node 라고도 부름)
• 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
• 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
• 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

1️⃣ 그래프(Graph)란?

1) 그래프란 사물을 정점(Vertex)와 간선(Edge)으로 나타내기 위한 도구
2) 두 가지 방식으로 구현할 수 있다

• 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식
• 인접 리스트(Adjacency List): 리스트를 사용하는 방식

✔️ 인접 행렬(Adjacency Matrix)

인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식

• 예시) 0에서 1로 이동하는 데에는 가중치 3
• 1에서 2로 가는 것은 없으니까 무한

✔️ 무방향 비가중치 그래프와 인접 행렬

• 무방향 그래프: 방향성을 가지지 않고 단순히 연결되어 있는 그래프
• 비가중치 그래프: 모든 간선에 가중치가 없는 그래프

무방향 비가중치 그래프가 주어졌을 때, 연결되어 있는 상황을 인접 행렬로 출력할 수 있다

✔️ 방향 가중치 그래프와 인접 리스트

• 방향 그래프: 모든 간선이 방향을 가지는 그래프
• 가중치 그래프: 모든 간선에 가중치가 있는 그래프

무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다

---

✨ tl;dr

• 인접 행렬은

  • 모든 정점들의 연결 여부를 저장하여 𝑂(𝑉2)의 공간을 요구하므로 공간 효율성이 떨어지지만
  • 두 정점이 서로 연결되어 있는지 확인하기 위해 𝑂(1)의 시간이 필요

• 인접 리스트는

  • 연결된 간선의 정보만을 저장하여 𝑂(𝐸)의 공간을 요구하므로공간 효율성이 우수하지만
  • 두 정점이 서로 연결되어 있는지 확인하기 위해 𝑂(𝑉)의 시간이 필요