CS, Data Structure- Graph

🍁 What is Graph🤔?

그래프는 정점(Vertex = Node, 노드라고도 함)과 간선(Edge = Arcs, 링크라고도 하며 노드간의 연결)으로 이루어진 자료구조입니다.

🍁 그래프의 종류

• 방향 그래프(Directed graph) : 두 노드간 연결된 간선(Edge)의 방향(🔴 → 🟢)이 존재, 방향으로만 움직일 수 있음(🔴 → 🟢 : ⭕️, 🔴 ← 🟢 : ❌).
• 무방향 그래프(Undirected graph) : 두 노드간 연결된 간선의 방향이 존재하지 않음(🔴 ⏤ 🟢), 양방향을 움직일 수 있음(🔴 → 🟢 : ⭕️, 🔴 ← 🟢 : ⭕️).
• 가중치 그래프(Weighted graphs): 두 노드간 이동시 비용이 발생(🔴 - 5 - 🟢).
  etc.

🍁 그래프의 표현 방법

• 인접 행렬(Adjacency matrix)

  그래프를 n*n의 행렬로 표현하는 방법으로 이동가능 하면 1, 아니면 0으로 표현한 곳으로, 구현이 비교적 간편하지만 O(n²) 의 시간복잡도가 소요됨.

• 인접 리스트(Adjacency list)

  그래프의 노드별로 Array를 만들어 표현한 것으로, 노드들의 연결을 탐색할 때 O(n) 의 시간이면 가능하지만 특정 두 노드가 연결 되었는지 확인하려면 인접 행렬에 비해 시간이 오래 걸림.