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

KYUNG HWAN·2021년 5월 3일
0

Data Structure

목록 보기
1/1
post-thumbnail

1. 그래프(Graph)란?

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)간선(Edge)로 표현하기 위해 사용되는 자료구조입니다. 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트(root)노드, 부모와 자식이라는 개념이 존재하지 않습니다.

다음 그림은 실생활에서 그래프의 예를 표현한 것입니다.

이처럼 집에서 회사까지 가는 최단 경로를 구한다는 것과 같이 알고리즘을 그래프로 구현할 수 있습니다. 그림에서 보이는 것과 같이 '집', '지하철', '버스' 그리고 '회사' 와 같이 원으로 표현된 것을 정점 또는 노드라고 부르고 방향을 나타내는 선을 간선이라고 부릅니다.

2. 그래프 관련 용어

그래프를 본격적으로 설명하기 앞서 그래프와 관련된 용어를 정리해 보겠습니다.

  • 노드(Node): 위치를 말함, 정점(Vertex)라고도 함
  • 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선(link 또는 branch 라고도 함)
  • 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점(또는 노드)
  • 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 진입 차수(In-Degree): 방향 그래프에서 외부로 향하는 간선의 수
  • 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수
  • 사이크(Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프와 관련해서 더 많은 용어들이 있지만 지금은 학술적으로 deep하게 알려고 하는 것이 아닌 그래프를 이해하기 위함이기 때문에 그래프의 기본적인 용어들만 적었습니다.

3. 그래프의 종류

그래프는 특성에 따라 여러가지 종류로 나누어집니다. 대표적인 그래프의 유형은 다음과 같습니다.

첫 번째는 무방향 그래프와 이와 반대되는 방향 그래프 입니다.

무방향 그래프(Undirected Graph)

  • 방향이 없는 그래프
  • 간선을 통해, 노드는 양방향으로 갈 수 있음
  • 보통 노드 A, B가 연결되어 있을 경우, (A, B) 또는 (B, A)로 표기

방향 그래프(Directed Graph)

  • 간선에 방향이 있는 그래프
  • 보통 노드 A, B가 A-> B로 가는 간선으로 연결되어 있을 경우로 방향 그래프는 <A, B>같이 '<', '>'로 표기 (<B, A>는 B-> A로 가는 간선이 있은 경우이므로 <A, B>와 다름

가중치 그래프 (Weighted Graph) 또는 네트워크(Network)

간선에 비용 또는 가중치가 할당된 그래프로 예를 들어서 맨 왼쪽을 '집', 오른쪽을 '회사'라고 보면 '4'와 '5'의 비용을 들이는데 반해서 '2'와 '1'의 비용을 들이면 더 적게 든다는 것을 판단할 수 있습니다. 이를 위해서 간선에 가중치가 들어가 있는 그래프를 가중치 그래프 또는 네트워크 그래프라고 합니다.

연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph)

연결 그래프는 우선, 무방향 그래프이어야 하고 무방향 그래프에 있는 모든 노드가 연결할 수 있는 경로가 존재하는 그래프입니다. 반면에 특정 노드에 대해서 경로가 존재하지 않는 그래프는 비연결 그래프 라고 합니다.

예를 들면, 아래의 그래프와 같이 노드는 4개인데 오른쪽에 간선으로 연결되어 있는 노드는 접근이 가능하지만 다른 노드에서 왼쪽 노드로 갈 수 있는 존재하지 않습니다. 이런 경우에 비연결 그래프라고 합니다.

사이클(Cycle)과 비순환 그래프(Acyclic Graph)

사이클은 위의 용어 정리에서 볼 수 있듯이 단순 경로의 시작 노드와 종료 노드가 동일한 경우입니다. 그리고 그렇지 않은 경우를 비순환 그래프라고 합니다.

예를 들어서 위의 예시로 있는 그래프는 딱 봐도 비순환 그래프인 것을 알 수 있습니다.

완전 그래프(Complete Graph)

완전 그래프는 그래프에 있는 모든 노드가 서로 연결되어 있는 그래프를 말합니다.

4. 그래프와 트리의 차이

그래프가 무엇인지 설명했을 때 그래프는 트리와는 다르다고 설명했습니다. 트리는 그래프 중에 속한 특별한 종류라고 볼 수 있습니다. 즉, 그래프라는 큰 정의안에 트리가 들어가 있다라고 보시면 될 것 같습니다. 다음 표는 그래프와 트리의 특징을 나타낸 것입니다.

그래프 트리
정의 노드와 노드를 연결하는 간선으로 표현되는 자료 구조 그래프의 한 종류, 방향성이 있는 비순환 그래프
방향성 방향 그래프, 무방향 그래프 둘다 존재함 방향 그래프만 존재함
사이클 사이클 가능함, 순환 및 비순환 그래프 모두 존재함 비순환 그래프로 사이클이 존재하지 않음
루트 노드 루트 노드 존재하지 않음 루트 노드 존재함
부모/자식 관계 부모 자식 개념이 존재하지 않음 부모 자식 관계가 존재함




Reference

  • 패스트 캠퍼스, 알고리즘/기술면접 완전 정복 올인원 패키지 Online.
profile
내가 그린 기린 그림

0개의 댓글