알고리즘 : 그래프 (Graph) (1)

본 포스팅에서는 그래프의 기본 용어만 다룹니다. 인접행렬 및 인접리스트 관련 내용을 원한다면 (2)를 읽어주세요.

그래프(Graph)

정점(Node/Vertex, 노드)과 간선(Edge, 엣지)으로 이루어진 자료구조이다.

 

 

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

 

정점 A에서 B로 이동할 수 있는 방법을 경로(Path)라고 한다. 그래프 내에서 정점끼리의 path는 여러 개여도 된다. 또 두 정점 간 경로가 존재하지 않을 수도 있다. 정점 A에서 B로 가는 Path가 존재하면 정점 B는 정점 A로부터 reachable하다고 한다.

노드가 겹치지 않는 경로를 elementary하다고 하며 길이(length)는 엣지의 수를 나타낸다.

 

간선으로 연결되어 있는 두 노드는 서로 인접(adjacent)해 있다고 한다. 경로 1-2-3-4 사이에는 간선이 총 3개가 있으므로 길이가 3이라고 할 수 있다.

 

간선 위에 이와 같이 숫자가 써져있다면 이는 가중치(Weigh)이다. 가중치가 없는 그래프는 모두 동일한 가중치를 가진 것이며 해당 간선을 타고 이동할 때 필요한 비용 등을 표현한다.

각 정점에 연결된 간선의 수를 차수(Degree)라고 한다. 혹은 간선 가중치의 합을 뜻한다. 해당 정점에서 나가는 간선은 out-degree, 해당 정점으로 들어오는 간선은 in-degree이다. 즉, out-degree + in-degree는 그 정점의 차수가 된다.

 

<1, 2, 4, 5, 6>과 같이 중복되는 노드가 없다면 simple path라고 한다. <1, 2, 4, 1>은 simple path가 아니다. Self loop 또는 Multiple Edge를 가지지 않는 그래프를 Simple Graph라고 한다.

 

모든 쌍의 정점이 연결가능한 그래프를 connected graph라고 한다.

 

그래프가 경로를 따라 동일한 정점으로 돌아올 수 있는 경우를 사이클(Cycle)이라고 한다.

돌아오는 경로에서 중복된 노드가 시작점(끝점) 이외에 발생하지 않는 경우는 Simple Cycle이다. 

그래프에 싸이클이 없는 경우는 acyclic graph라고 한다.

 

간선이 방향을 가지고 있으면 방향성 그래프(Directed Graph)가 되고, 방향성이 없으면 무방향성 그래프(Undirected Graph)가 된다. 방향이 있다면 방향에 따른 이동만 가능하고, 방향성이 없다면 양방향 이동이 가능한 것이다.

 

 

정점에서 자기 자신으로 돌아오는 간선을 Self-loops라고 한다. 

 

노드의 수보다 엣지의 수가 적으면 Sparse Graph라고 한다. 노드 수보다 엣지 수가 많다면 Dense Graph이다. 

 

임의의 그래프 G= (V, E)가 주어졌을 때 G' = (V', E')는 G의 부분 그래프(subgraph)가 된다.

서브그래프 G'에 속하는 정점들의 집합은 그래프 G의 정점들의 부분집합이어야 한다. 또한 서브그래프 G'에 속하는 간선들의 집합은 그래프 G의 간선들의 부분집합이어야 한다. E'에 속하는 모든 간선들은 V'의 정점들만을 이용해야 한다.

마지막 문장은, 노드랑 노드를 연결하는 간선만 존재한다는 뜻이다.

 

 

그래프 표현 방식

그래프의 표현방식에 대해서는 (2)에서 좀 더 구체적으로 다룰 예정이다. 그 전에 간단하게 어떤 것을 다룰 것인지 설명하도록 하겠다.

 

그래프를 컴퓨터가 처리하게 만들기 위해서는 그래프를 적절한 자료구조로 변환해 주어야 한다.

표현 방식에는 인접행렬(adjaceny matrix)와 인접리스트(adjaceny list)가 있다.

이와 같이 가중치가 없는 방향 그래프를 인접행렬로 표현할 수가 있다. 1은 둘 사이에 간선이 있다는 뜻이 된다.

 

인접리스트로 표현하는 방식은 이와 같다. 

https://shine-slowly.tistory.com/42

알고리즘 : 자료구조(4) 리스트 (List)

리스트를 잘 모른다면 위 포스팅을 간단하게 읽고오는 것을 추천한다.

 

 

 

참고 티스토리

https://ratsgo.github.io/data%20structure&algorithm/2017/11/18/graph/

그래프 기본 용어 · ratsgo's blog

https://ttl-blog.tistory.com/954#%F0%9F%A7%90%C2%A0Simple%20Graph%C2%A0-1

[알고리즘] 그래프 (1) - 그래프의 기본 용어

https://www.leafcats.com/77

그래프 알고리즘(Graph Algorithm)의 기초 용어 정리