종류: Undirected, Directed, Weighted Graph
표현방식: 인접행렬(Adjacency Matrix), 인접리스트(Adjacency List)

그래프 기본 용어

정점(vertex)

그래프를 구성하는 데이터나 객체를 저장하는 하나의 객체. 수학에서는 노드를 정점이라고 표현한다. 정점=노드

노드(node)

그래프를 구성하는 데이터나 객체를 저장하는 하나의 객체. 컴퓨터과학에서는 정점을 노드라고 주로 표현한다. 노드=정점

간선(edge)

두 정점을 연결하는 선.

아크(arc)

방향성이 있는 간선.

그래프 종류

무방향 그래프 (undirected graph)

노드를 연결하는 간선의 방향이 존재하지 않는 그래프로
사실상 모든 노드의 연결된 간선이 양쪽 방향으로 이동할 수 있다는 걸 의미합니다.

방향 그래프 (directed graph)

두 노드를 연결하는 간선에 방향이 있는 그래프로
간선의 방향은 단방향,양방향이 섞은 형태의 그래프를 의미합니다.

가중 그래프 (Weighted Graph)

그래프 중에서 간선에 가중치에 부여된 그래프를 뜻한다.
두 노드 사이를 이동하는데 이동거리,비용등이 소모된다는 걸 의미한다.

그래프 표현 방식

인접행렬(Adjacency Matrix)

그래프를 표현하는데 있어서 2차원 배열로 표현하는 방식이다.
matrix[출발노드][도착노드] = 간선의 가중치 형태로

인접리스트(Adjacency List)

그래프를 표현하는데 있어서 연결리스트로 표현하는 방식이다.
예를 들어 1부터 5까지의 정점이 있는 그래프라면
리스트[출발노드] = [도착노드,가중치] 이런식으로 저장한다.
리스트[출발노드] = [[도착노드1, 가중치1], [도착노드2, 가중치2], ...]
이런 식으로 출발노드 인덱스에 간선과 가중치를 리스트로 묶어
여러 간선의 데이터가 저장되는 방식으로 표현한다.