[Algorithm] Graph 표현과 정의

그래프의 정의

그래프 G(V, E)는 어떤 자료나 개념을 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 잡합 E로 구성된 자료구조이다.

정의만 보면 어렵게 느껴질 수 있지만 그래프라는 건 결과 하나 혹은 여러 개의 오브젝트(물체)와 그들간의 연결 상태를 나타내는 자료구조라고 생각하시면 됩니다.

왼쪽(무향 그래프) 오른쪽(방향그래프)

그래프의 종류

• 무방향 그래프(undirected graph) : 간선이 양쪽 모두를 향해 연결되어 있는 그래프
• 방향 그래프(directed graph) : 간선에 방향이라는 속성이 존재하는 그래프
• 가중치 그래프(weighted graph) : 간선에 가중치라고 불리는 value가 존재하는 그래프

이 밖에도 여러가지 그래프가 있지만 가장 대체로 사용하는 그래프는 위에 나타난 것과 같습니다.

 

그래프의 경로

그래프에서 경로는 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것입니다.

위에 있는 그림 중 오른쪽 방향 그래프에서는 (1,3)(3,4)는 2개의 간선으로 이루어진 하나의 경로라고 할 수 있습니다.

만약 (1,3)(3,4)(4,1)처럼 시작 정점과 끝 정점이 일치한다면 사이클 혹은 회로라고 할 수 있습니다.

 

그래프의 표현 방법

 

그렇다면 이러한 그래프를 표현하는 방법은 어떻게 할 수 있을까요?

 

1. 인접 리스트 표현 : 인접 리스트에서 그래프의 표현은 각 정점마다 다른 정점으로 연결된 간선의 목록을 저장해서 그래프를 표현합니다.
2. 인접 행렬 표현 : 2차원 배열을 이용해 그래프의 간선 정보를 저장합니다.