그래프 1

그래프

점이 있고 이 점이 선으로 연결된 형태를 그래프라고 한다. 이러한 점은 각각 vertex, 정점, 노드라고 불리며 연결한 선은 edge 혹은 간선이라고 부른다. 이전에 트리는 순환 형태가 없는 그래프를 말했지만, 그래프는 순환 형태가 있는 것, 순환 형태가 없는 것을 모두 통칭해서 말한다.

종류

그래프의 종류는 크게 두 종류로 나뉜다.

무방향성 그래프 (Undirected Graph)

방향성이 없는 그래프로 노드 u와 노드 w로 나타내는 에지가 있을 때 <u,w>건 <w,u>건 같은 에지이다.

방향성 그래프 (Directed Graph)

방향성이 없는 그래프로 노드 u와 노드 w로 나타내는 에지가 있을 때 <u,w>는 u에서 w로 향하는 에지고, <w,u>는 w에서 u로 향하는 에지이기 때문에 다른 에지이다.

용어

완전 그래프 (Complete graph)

간선 수가 최대로 연결된 그래프를 완전 그래프라고 한다. 이때 방향성 그래프냐 무방향성 그래프냐에 따라 간선의 수가 달라지는데 무방향성 그래프의 최대 간선 수는

노드 개수가 n일때
n (n-1) / 2

방향성 그래프의 최대 간선 수는

노드 개수가 n일때
n (n-1)

방향성 그래프의 경우 u->w와 w->u를 다른 간선으로 취급하기 때문에 무방향성 그래프의 최대 간선 수의 2배이다.

인접 (Adjacent)

무방향성 그래프에서 노드 u,w가 간선으로 연결되어있다면 노드 u와 w는 인접해있다고 말한다.
방향성 그래프에서 노드 u,w가 간선 <u,w>로 연결되어있다면 u는 w에 인접한 것이고 간선 <w,u>로 연결되어있다면 w는 u에 인접한 것이다.

부속 (Incident)

노드 u,w가 간선 a로 연결되어있다면 간선 a는 노드 u,w에 부속되어있다고 한다.

부분 그래프 (Subgraph)

그래프 G의 노드 집합 V(G), 간선 집합 E(G)이고
그래프 G’의 노드 집합 V(G’), 간선 집합 E(G’)일 때 아래의 조건을 만족하면 그래프 G’는 그래프 G의 부분 그래프이다.

  V(G')⊆V(G), E(G')⊆E(G)

이 말인 즉슨 그래프 G안에 있는 노드와 간선만으로 그래프가 구성되어있다면 그 그래프는 그래프 G의 부분이라는 말이다.

경로

노드 V와 W가 있을 때 V에서 W까지 갈 때 필요한 간선을 말한다. 그리고 V에서 W까지 가는데 필요한 간선의 개수를 경로의 길이라고 말한다.

단순 경로

간단히 말해서 경로긴 경로인데 동일한 노드를 거치지 않는 경로를 말한다.

사이클

노드 A가 있을 때 A로 돌아오는 단순 경로가 있으면 사이클이라고 말한다.

차수

이전에 트리에서 설명했듯이 노드에 연결된 간선 개수를 차수라고 하는데 무방향성 그래프의 경우 노드에 연결된 간선의 개수만 세면 되지만 방향성 그래프의 경우 노드로 들어오는 간선이 다르고, 나가는 간선이 다르기 때문에 따로 세어야한다.

구현

인접 행렬

행렬을 통해서 인접한 그래프를 구하는 방식이다. 가령 NODE 1,2,3이 있고 다음과 같은 그래프가 있다고 가정해보자.

이러한 그래프를 행렬을 통해서 나타내려면 다음과 같이 나타낼 수 있다. 1은 간선이 있는 것이고, 0은 없는 것이다. 열의 경우 왼쪽부터 NODE 1,2,3이고 행의 경우 위에서부터 아래로 NODE 1,2,3을 나타낸다면

  0 1 0
  1 0 1
  0 1 0

무방향성 그래프의 경우 (n,n)을 기준으로 선을 나눴을 때 대칭으로 나타난다. <1,2>나 <2,1>이나 동일하기 때문이다. 하지만 방향성 그래프의 경우 꼭 대칭이 아닐 수도 있다.

또한 NODE의 개수는 많으나 간선의 개수가 적을 경우 사용하는 메모리에 비해 데이터 양이 많지 않아 낭비되는 메모리가 너무 크다. 그래서 간선을 표기하는데 필요한 메모리만 쓰자는 생각으로 나온게 바로 인접 리스트 방식이다.

인접 리스트

인접 리스트의 방식은 기본적으로 모든 노드를 표현한 배열이 하나 있고 해당 배열의 위치에 각 노드에 달린 간선을 표현하기 위한 연결리스트가 달려있다. 위에서 썼던 예시를 인접리스트 방식으로 그대로 표현해보겠다.

노드에 대한 배열이 있고 그 배열에 1,2,3이 있다. 이 노드에 대해서 연결된 노드를 오름차순으로 달아 둔 것이다.

방향성 그래프일때는 상관이 없지만 무방향성 그래프의 경우 데이터가 중복으로 들어가게된다. 때문에 메모리 낭비가 있다. 이런 문제를 해결하기 위해 나온게 인접 다중 리스트 방식이다.

인접 다중리스트

인접 다중리스트는 인접 리스트와는 비슷해보이나 방법이 좀 다르다.
먼저 그래프의 노드를 나타내는 배열은 그대로 있으나 간선을 나타내는 방식이 좀 다르다. 이전에 노드와 연결된 노드를 모두 나열했던 방식과는 달리 이번에는 간선을 나타내는 노드를 달게되는데 이 간선을 나타내는 노드에는 아래와 같은 구조체로 되어있다.

struct adjacency_multilist{
  bool marked;
  int i;
  int j;
  struct adjacency_multilist *i-link; // node i에 대한 인접 리스트 위치
  struct adjacency_multilist *j-link; // node j에 대한 인접 리스트 위치
}

예를 들어 설명해보자면 노드 1,2,3,4,5로 이루어진 다음과 같은 그래프가 있다고 할때 인접 다중 리스트의 모습은 아래와 같다.

가령 노드 3에 연결된 간선들을 알고 싶다고하면 Nodes 배열에서 3이 edge index 3을 가리키고 있으니 그쪽으로 이동하여 탐색한다. 해당 link의 marked bit를 0으로 바꾸고 거기서 3은 j에 있으니 j-link에서 가르키는 edge index 6으로 이동한다. 해당 edge에도 marked를 1로 세팅하고 3이 i에 있으니 i-link를 확인해본다. i-link가 null이니 탐색이 종료되는데 그 과정에서 2개의 edge(3,6)을 거쳤으므로 3에 연결된 간선은 2개이며 각각 <2,3>, <3,5>인 것을 알 수 있다.

참고 자료

• 학부생시절 자료구조 강의 자료
• 블로그스키