그래프 Graph

그래프는 단순히 정점(vertex, node)과 간선(edge)으로 구성된 자료구조이다.
도로로 연결된 여러 마을을 표시한 지도를 생각해보자.
지도도 일종의 그래프라고 할 수 있다.
지도에서 각 마을은 정점이며 도로가 간선이다.
간선은 (v1, v2)와 같은 쌍으로 정의하며, 여기서 v1, v2는 그래프의 정점이다.

간선의 방향 유무에 따라 무방향 그래프와 방향 그래프로 나뉜다.

간선에서 정점의 순서를 따지는 그래프를 방향성 그래프라고 한다.
방향성 그래프에서는 화살표로 간선을 표시한다.
이 간선은 정점 간의 흐름을 의미한다.
방향성이 없는 그래프를 무방향 그래프 또는 그래프라고 한다.

용어

• Vertex(정점)
  • 그래프의 각 정점을 vertex 또는 node라고 한다. 위치의 개념.
  • 정점에는 데이터가 저장된다.
  • 위의 그래프에서는 0, 1, 2 총 3개의 노드가 존재한다.
• Edge(간선)
  - 위치 간의 관계.
  • 노드와 노드 사이를 이어주는 선.(link, branch)
  • 위의 그래프에서는 총 3개의 간선이 존재한다.
• complete graph(완전 그래프)
  • 그래프의 모든 정점들 사이에 직접 연결된 간선이 존재하는 그래프.
    • n개의 정점을 가진 무방향 그래프 : 간선 수가 n*(n-1) / 2인 경우 완전 그래프.
    • n개의 정점을 가진 방향 그래프 : 간선 수가 n*(n-1)인 경우 완전 그래프.
• subgraph(부분 그래프)
  • 원본 그래프의 일부인 그래프를 부분 그래프라고 한다.
  • 부분 그래프의 정점과 간선은 원래 그래프의 정점과 간선의 부분 집합이다.

G2는 G1의 부분그래프다.

• adjacent(인접)
  • 무방향 그래프에서 정점 A, B 사이에 간선이 존재한다면 정점 A는 정점 B에 인접한다.
• incident(부속)
  • 무방향 그래프에서 정점 A, B 사이에 간선이 존재한다면 간선(A, B)는 정점 A, B에 부속한다.
• path length(경로 길이)
  • 경로를 구성하는데 사용된 간선의 수.
• simple path(단순 경로)
  • 경로 중에서 반복되는 정점이 없는 경우.
• cycle(사이클)
  • 단순 경로의 시작 정점과 종료 정점이 같은 경로.(closed path)
• degree(차수) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수.
  • in-degree(진입차수) : 방향 그래프에서 정점을 향해 들어오는 간선의 수.
  • out-degree(진출차수) : 방향 그래프에서 정점으로부터 나가는 방향의 간선의 수.

특징

• 그래프는 네트워크 모델이다.
  • 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다.
• 2개 이상의 경로가 가능하다.
  • 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• 간선의 유무는 그래프에 따라 다르다.
• 순환(Cyclic) 혹은 비순환(Acyclic)이다.
• 순회는 DFS나 BFS로 이루어진다.
• 루트 노드라는 개념이 없다.
• 부모-자식 관계라는 개념이 없다.

그래프 종류

무방향 그래프(Undirected Graph)

• 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
• 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
  • (A, B)는 (B, A) 동일
• Ex) 양방향 통행 도로

방향 그래프(Directed Graph)

• 간선에 방향성이 존재하는 그래프
• A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
  • <A, B>는 <B, A>는 다름
• Ex) 일방 통행

연결 그래프(Connected Graph)

• 무방향 그래프에 있는 모든 정점 쌍에 대해서 항상 경로가 존재하는 경우.
• Ex) 트리(Tree) : 사이클을 가지지 않는 연결 그래프.

비연결 그래프(Disconnected Graph)

• 무방향 그래프에서 특정 정점 쌍 사이에 경로가 존재하지 않는 경우.

사이클

• 단순 경로의 시작 정점과 종료 정점이 동일한 경우.
  • 단순 경로(Simple Path) : 경로 중에서 반복되는 정점이 없는 경우.

비순환 그래프

• 사이클이 없는 그래프.

완전 그래프

• 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프.
• 무방향 완전 그래프
  - 정점 수 : n이면 간선의 수 : n * (n-1) / 2
  

그래프의 구현

그래프의 구조를 표현하는 것은 간선이므로 실제 정보는 간선에 저장된다.

1. 인접 리스트(Adjacency List)

• 모든 정점(노드)을 인접 리스트에 저장한다.
• 각 정점에 인접한 정점들을 리스트로 표현한 것.
• 인접한 각 정점의 배열 리스트에 정점을 인덱스로 이용해 간선을 저장한다.
• 리스트는 공간을 동적으로 할당하므로 공간 활용도가 높다는 장점이 있다.
• 두 정점의 연결유무를 확인하기 위해 배열보다 오랜 시간(O(n))이 소모된다.
• 구현이 배열에 비해 비교적 어렵다.

2. 인접 행렬(Adjacency Matrix)

• 두 정점 간의 간선이 존재하는지 여부를 알려주는 요소를 포함하는 2차원 배열.
• 정점을 연결하는 노드에 다른 노드들이 인접 정점이라면 1, 아니면 0을 넣어준다.

if(간선 (i, j)가 그래프에 존재)
  matrix[i][j] = 1;
else
  matrix[i][j] = 0;

• 구현이 비교적 간단하다.
• 배열에 그래프 간선 정보가 저장되기 때문에 두 정점의 연결유무를 빠르게 조회할 수 있다.(O(1))
• 모든 간선에서 모든 간선에 대한 정보를 2차원 배열에 저장하므로 구현 시 O(n^2) 시간 복잡도를 갖는다.
• 무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다.
  • 간선이 없다는 정보도 따로 저장.
  • 무방향 그래프의 경우 간선 정보가 2번 저장된다.

그래프의 탐색

첫 정점에서부터 그래프에 존재하는 모든 노드들을 모두 한번씩 방문하는 것을 그래프 탐색이라고 한다.
그래프 탐색의 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

깊이 우선 탐색(DFS, Depth-First Search)

• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것.
• 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 노드로 돌아가는 방식으로 그래프를 순회한다.
• 모든 노드를 방문하고자 하는 경우 사용한다.
• BFS보다 좀 더 간단하다.
• 간단히 재귀 호출을 사용하여 구현하거나 스택을 사용하여 구현한다.

너비 우선 탐색(BFS, Breadth-First Search)

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• 일반적으로 큐를 사용해서 구현한다.