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

그래프

그래프는 node(N) | vertex(V)와 그 노드를 연결하는 간선(E, edge)으로 표현된 자료구조이다.

• 연결되어 있는 노드들 간의 관계를 표현할 수 있는 자료구조이다.

• 그래프는 여러 개의 Isolated Subgraphs로 구성될 수도 있다.

그래프의 용어

• 정점(Vertex, Node): 데이터가 저장되는 위치

• 간선(Edge): 위치 간의 관계. 즉, 노드를 연결하는 선으로 link, branch라고도 부른다.

• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점

• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 각 정점의 차수의 합 = 그래프의 간선 수의 2배

• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수

• 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
  • 방향 그래프에 있는 정점의 진입 차수와 진출 차수의 합 = 방향 그래프의 간선의 수

• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수

• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우

• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 종류

무방향 그래프 vs 방향 그래프

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

• 방향 그래프 (Directed Graph)
  • 간선에 방향성이 존재하는 그래프
  • A -> B로만 가는 간선은 <A,B>로 표현한다.
    • 방향성이 있기 때문에 <A,B>는 <B,A>와 다르다.

가중치 그래프

• 가중치 그래프 (Weighted Graph)
  • 간선에 비용이나 가중치가 할당된 그래프
  • 네트워크라고도 부른다.

연결 그래프 VS 비연결 그래프

• 연결 그래프 (Connected Graph)
  • 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 경우
  • 무조건 도달할 수 있다.
• 비연결 그래프 (Disconnected Graph)
  • 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않을 경우

순환 그래프 (사이클) VS 비순환 그래프

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

• 비순환 그래프 (Acyclic Graph)
  • 사이클이 없는 그래프

완전 그래프

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

그래프의 구현

인접 리스트 (Adjacency List)

인접 리스트는 그래프의 노드들을 리스트로 표현한 것이다. 각각의 노드에 대해 직접 연결이 있는 노드를 해당 노드의 인덱스에 삽입해준다.

무방향 그래프일 경우 직접 연결된 두 노드의 인덱스 각각에 서로의 노드를 삽입한다.

인접 리스트의 장단점

• 인접 리스트의 장점
  • 정점들의 연결 정보 (인접 노드)를 탐색할 때 O(n)의 시간이면 가능하다.
  • 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.
• 인접 리스트의 단점
  • 특정 두 정점이 연결되어 있는지 확인하려면 인접 행렬에 비해 시간이 오래걸린다.
    • O(E)만큼의 시간이 소요된다. E는 Edge
  • 구현이 비교적 어렵다.

그래프 내에 적은 숫자의 간선을 가지는 희소 그래프의 경우 유리하다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 그래프의 노드가 N개일 경우 N * N인 2차원 배열로 만들고 노드들 간의 직접 연결이 되어있으면 1을, 아니면 0을 넣어 행렬을 완성 시키는 것이다.

예를 들어 matrix[i][j] == True일 경우 i -> j의 간선이 있다는 뜻이다.

무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭 행렬(Symmetric Matrix)가 된다.

인접 행렬의 장단점

• 인접 행렬의 장점
  • 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보(간선 정보)를 조회할 때 O(1)의 시간복잡도면 가능하다.
  • 인접 리스트에 비해 구현이 간단하다.
  • 정점의 차수를 O(N) 안에 알 수 있다.
    • 인접 행렬의 i번째 행 또는 열을 모두 더한다.
• 인접 행렬의 단점
  • 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n^2)의 시간복잡도가 소요된다.
  • 무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다.
    • 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다.
  • 인접 행렬은 간선 정보만 담겨져 있기 때문에 인접 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.

그래프 내에 간선이 많이 존재하는 밀집 그래프일 경우 유리하다.

그래프의 탐색

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

임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 즉, 넓게 탐색하기 전에 깊게 탐색하는 방식이다.

너비 우선 탐색(BFS)보다 좀 더 간단하지만 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.

주로 모든 노드를 탐색해야 할 때 깊이 우선 탐색을 사용한다.

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

임의의 노드에서 시작해서 깊게 탐색하기 전에 인접한 노드를 먼저 탐색하는 방식이다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

Related Posts

[알고리즘] 탐색 알고리즘 DFS/BFS

References

Honcoding

Heee’s Development Blog