[알고리즘] Graph (그래프) 용어와 표현 방법, 종류와 예시

Graph

• 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것
• Graph G = (V, E)
  • V : 정점 집합
  • E : 간선 집합
• 두 정점이 간선으로 연결되어 있으면 인접하다고 한다.
  • 인접 = adjacent
  • 간선은 두 정점의 관계를 나타낸다.

그래프 용어

• 정점(vertex, node), 이음선(edge, arc)
• 방향 그래프(directed graph)
• 가중치(weight), 가중치 포함 그래프(weighted graph)
• 경로(path), 단순경로(simple path) - 같은 정점을 두번 지나지 않음
• 순환(cycle) - 한 정점에서 다시 그 정점으로 돌아오는 경로
• 순환 그래프(cyclic graph) vs 비순환 그래프(acyclic graph)
• 길이(length)

그래프의 표현 방법

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

• NXN 행렬로 표현
  • N : 정점의 총 수
  • 원소 (i, j) = 1 : 정점 i 와 정점 j 사이에 간선이 있음
  • 원소 (i, j) = 0 : 정점 i 와 정점 j 사이에 간선이 없음
• 유향 그래프의 경우
  • 원소 (i, j)는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄
• 가중치 있는 그래프의 경우
  • 원소(i, j)는 1 대신에 가중치를 가짐

무향 그래프의 예

가중치가 있는 무향 그래프의 예

유향 그래프의 예

가중치가 있는 유향 그래프의 예

유향 그래프의 다른 예

가중치가 있는 그래프의 다른 예

Adjacency List

• N개의 연결 리스트로 표현
• i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓음
• 가중치 있는 그래프의 경우
  • 리스트는 가중치도 보관한다

무향 그래프의 예

가중치가 있는 무향 그래프의 예