[자료구조] 그래프(Graph)

코딩밥상 2023. 1. 18. 02:01

그래프(Graph) 란?

그래프는 '정점의 모음'과 정점을 잇는 '간선의 모음'이 결합한 것입니다. 즉

"정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G = (V,E)이다." 라고 정의할 수 있습니다.

정점 자체는 아무의미가 없지만 이들이 간선을 통해 서로 연결되면 '관계'가 형성되고 그로 인해 그래프가 만들어집니다.

간선으로 연결된 두 정점을 서로 '인접(Adjacent)' 또는 '이웃 관계'에 있다고 말합니다. 정점 끼리 간선으로 연결 되어 있을 때 이 정점들은 '경로(Path)'를 이루고 경로의 '길이'는 정점과 정점 사이에 있는 간선의 수로 정의됩니다.

어느 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 그 경로를 일컬어 '사이클(Cycle)'이라고 합니다.

간선은 그래프의 성격 자체를 바꾸기도 하는데, 간선에 방향성이 있으면 방향성 그래프(Directed Graph), 방향성이 없다면 무방향성 그래프(Undirected Gragh)라고 합니다.

무방향성 그래프 내의 두 정점 사이에 경로가 존재하면 이 두 정점은 연결되어 있다고 합니다. 그리고 그래프 내의 각 정점이 다른 모든 정점과 연결되어 있다면 이 그래프는 연결되었다고 합니다.

-인접행렬(Adjacency Matrix)

정점끼리의 인접 관계를 나타내는 행렬입니다.

그래프의 정점 수를 N이라고 했을 때 N*N 크기의 행렬을 만들어 한 정점과 또 다른 정점이 인접해 있는 경우 행렬의 각 원소를 1로 표시하고, 인접해 있지 않은 경우 0으로 표시합니다.

각 정점은 자기 자신과의 인접 관계를 만들 수 없으므로 주대각 성분들은 0이 되고 무방향성 그래프의 인접 행렬은 이 주대각선을 기준으로 대칭을 이루는 것이 특징입니다.

방향성 그래프를 인접행렬로 나타낼 때에는 정점 자신이 직접 간선을 통해 가리키고 있는 정점에 대해서만 인접해 있다고 표현합니다.

-인접 리스트(Adjacency List)

그래프 내 각 정점의 인접 관계를 표현하는 리스트입니다.

말 그대로 각 정점이 자신과 인접한 모든 정점의 목록을 리스트로 관리하도록 하는 기법입니다. 따라서 각 정점들이 리스트의 헤드가 되고 인접한 모든 정점들을 리스트로 연결하여 표현합니다.

이 때 방향성 그래프는 마찬가지로 직접 간선을 통해 가리키고 있는 정점에 대해서만 인접해 있다고 표현합니다.

-두 표현방법의 비교