Graph 이론에서 그래프

출처 : https://www.geeksforgeeks.org/graph-and-its-representations/

Graph and its representations - GeeksforGeeks

 

안녕하세요 besforyou 입니다

 

이번 글에서는 그래프 알고리즘 문제들을 풀기 위한 기초에 대해 소개해보겠습니다.

 

---

그래프가 무엇인가

 

그래프는 다음 두 가지로 구성된 자료 구조이다.

 

1. 노드라고 불리는 정점들로 이루어진 유한 집합

2. edge라고 ( u, v ) pair들이 정렬되어 이루어진 유한 집합

 

( u , v ) pair는 (v, u) pair와 동일하지 않기 때문에 ( 방향 있는 그래프를 나타낼수도 있으므로 )

정렬되어 이루어져있다.

 

pair ( u , v )는 정점 u에서 정점 v로 가는 edge가 존재함을 나타낸다.

edge는 weight/value/cost (무게/값/비용)등을 갖고 있을 수 있다.

 

 

그래프는 실생활 응용 앱들을 표현하기 위해 사용된다. 예로 그래프는 네트워크를 표현하기 위해 사용되기도 한다.

네트워트들은 도시 속의 경로, 전화 네크워크 (전화망), 순환 네트워크를 포함할 수도 있다. 

 

그래프는 페이스북, linkedIn과 같은 소셜 네트워크에도 사용된다. 

 

예로, 페이스북에서 각 사람은 vertex(node, 정점)으로 표현된다.

각 노드는 구조화 되어있고 사람 id, 이름, 성별, 지역과 같은 정보를 담고 있다.

 

다음은 5개의 vertices로 이루어진 undirected graph이다.

 

못난 그림 죄송합니다

 

 

다음 2개는 그래프로 가장 많이 표현된다.

 

1. Adjacency Matrix

2. Adjacencey List

 

Incidence Matrix와 Incidence List 또한 표현 가능하다.

 

그래프 표현 사용 여부는 상황에 따라 다르다. 거의 수행 연산의 종류와 사용 편의성에 따라 갈린다.

 

 

1. Adjacency Matrix ( 인접행렬 )

 

한글로는 인접행렬이라고 불린다.

인접행렬은 그래프의 정점이 V개일때 V * V개의 크기를 가지는 이차원 배열로 표현된다.

 

이차원 배열을 adj[][] 이라고 하자. 

adj[i][j] = 1 는 정점 ( vertext) i에서 정점 j로 가는 경로 (edge) 가 1개 있다는 의미하다.

 

 

장점 : 표현과 구현이 쉽다.

단점 : 메모리 사용량이 O(V^2)이다. 그래프에 경로가 별로 없어도 경로를 추가하는데 O(V^2) 시간이 든다.

 

 

 

2. Adjacency List ( 인접 리스트 )

 

배열의 각 원소가 리스트로 되어있는 배열이 이용된다.

배열의 크기가 정점의 개수와 동일하다.

배열[i]는 i번째 정점(vertex)와 이어진 정점들을 리스트로 표현한다.

이 방식으로 가중 그래프(weight graph)를 표현할 수도 있다.

경로의 무게는 pair의 리스트로 표현될 수 있다.