[알고리즘 개념] 그래프 이론

그래프 이론이란?

객체들 간의 관계를 추상화한 자료 구조로, 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 구성되며, 정점은 객체를, 간선은 객체들 간의 관계를 나타낸다. 

 

 

그래프의 종류

1. 무방향 그래프(Undirected Graph)

간선에 방향이 없는 그래프로 간선을 통해 양방향으로 이동할 수 있다.

 

2. 방향 그래프(Directed Graph)

간선에 방향이 있는 그래프로 간선은 한 방향으로만 이동할 수 있다.

 

3. 가중치 그래프(Weighted Graph)

간선에 가중치가 할당된 그래프로 간선을 통과하는 비용이나 거리를 나타낼 수 있다.

 

 

그래프의 표현 방법

1. 인접 행렬(Adjacency Matrix)

2차원 배열을 사용하여 그래프를 표현한다. 간선의 존재 여부를 행렬의 값으로 표현할 수 있다.

 

2. 인접 리스트(Adjacency List)

각 정점마다 인접한 정점들을 리스트로 표현하여 그래프를 표현한다. 메모리를 효율적으로 사용할 수 있다.