그래프(Graph)

그래프(Graph)

    그래프는 노드(또는 정점) 사이에 연결(간선)을 이루어 만들어지는 자료구조이다.

    관련이 있는 사물 또는 개념을 서로 묶은 것이 바로 그래프이다.

그래프의 구성요소 및 용어

그래프는 2개의 집합으로 구성 된다.

 

바로 정점과 간선이다.

정점 == 꼭지점 == 노드 == Vertex

그래프를 구성하는 요소로, 연결점 에 해당한다.

간선 == 선분 == 변 == 연결선 == 가지 == (Arc, Edge, Link)

두 정점을 이어주는 선분, 간선에 의해 이어진 두 정점은 서로 인접한다.

 

 

용어

경로	하나의 정점에서 다른 정점까지의 일련의 간선들 두 개의 정점 사이를 잇는 간선들을 순서대로 나열함
단순 경로	경로 상에서 시작과 끝을 제외한 중복되는 정점을 지나지 않는 경로
사이클(순환)	정점 v1에서 정점 v1로 되돌아오는 경로를 의미한다.
단순 사이클	경로 내에 같은 정점을 두 번 이상 지나가지 않는 사이클을 의미한다.

 

그래프의 종류

가중치 그래프	간선마다 가중치 값을 할당하는 그래프를 가중치를 부여한다. 일반적으로 가중치가 의미하는 바는 정점사이를 이동하는데 필요한 비용 또는 거리이다.
무 방향 그래프	간선에 방향성이 없고, 어느 방향으로든 진행 할 수 있는 그래프이다. 정점 v와 u 사이의 연결선을 ( v, u )로 표시
방향성 그래프	간선에 방향이 있어서, 해방 방향으로만 진행이 가능하다. 정점 v와 u 사이의 연결선을 < v, u >로 표시
연결 그래프	그래프 내의 모든 정점들 사이에 경로가 존재함.(인접 x)
절단 그래프	갈 수 있는 경로가 존재하지 않는 정점이 1개 이상인 그래프
완전 그래프	모든 정점이 서로 인접한다.
트리	연결 그래프 중, 사이클(순환) 이 없는 그래프이다.

     

그래프 구현방법

 

그래프를 구현한다는 것은 각 정점간의 연결 상태를 나타냄을 의미한다.

 

그래프를 표현하기위한 방법은 두 가지가 있는데 바로 인접행렬 방식과 인접 리스트 방식이다.

 

 

 

인접 행렬 (Adjacency Matrix)

정점간의 연결 상태를 2차원배열에 저장한다.

 

정점 간에 연결된 간선이 있으면 1(True) 로, 없으면 0으로 둔다.

 

자기 자신과 대칭되는 가운데 대각선은 아무 값이나 채워둔다.

 

만약 가중치 그래프를 표현하고자 한다면, 1 대신 가중치 값을 넣으면 된다.

 

가중치란 일반적으로 정점간의 이동 비용이기 때문에 갈수 없는 경우 inf(무한대)로 둔다.

 

무방향 그래프의 경우, 위 그림처럼 대각선을 중심으로 배열의 모양이 대칭적이다.

 

따라서 배열의 반쪽만 사용하여 메모리 공간을 절약 할 수도 있다.

 

반면에 방향성 그래프의 경우 일반적으로 배열의 모양이 대칭이 아니다.

 

A -> B 로 갈 수는 있어도, B -> A 로 갈 수 있다는 보장이 없기 때문이다.

 

인접행렬로 그래프를 구현한다면, 해당 정점의 배열의 어떤 인덱스인지 알아내야하기 때문에

 

정점과 배열의 인덱스를 맵핑 시키는 테이블이 필요하다.

 

 

 

 

 

인접 리스트

 

그래프를 표현하는 두 번째 방법은 인접 리스트이다.

 

위 그림은 무방향성 그래프와 방향성 그래프를 인접리스트로 표현한 것이다.

 

일단 각각의 노드를 배열의 인덱스로 맵핑 하는 작업은 인접리스트도 동일하다.

 

각 배열의 요소는 리스트로서, 리스트의 각 요소는 해당 정점과 연결되어 있는 노드들이다.

 

리스트의 요소들이 해당 정점과 연결된 경로로 착각해서는 안 된다.

 

따라서 리스트에 들어가는 순서는 아무런 상관이 없다.

 

 

 

 

 

인접 행렬과 인접 리스트의 장단점

 

두 정점의 연결 관계 확인은 인접 행렬이 빠르다.

 

배열로 구성했기 때문에 인덱스 맵핑 작업을 제외하면, 으로 바로 알아 낼 수 있다.

 

반면에, 특정 정점에서 다른 정점으로 연결된 모든 간선 확인은 인접 리스트가 빠르다.

 

인접행렬 방식은 해당 정점과 연결된 다른 정점정보를 모두 확인해야 하지만,

 

인접 리스트는 리스트에 연결된 데이터들만 가져오면 끝나기 때문이다.

 

간선 수가 적은 희소 그래프(Sparse Graph) 의 경우 인접리스트가 유리하고

 

간선 수가 많은 조밀 그래프(Dense Graph) 의 경우 인접행렬이 유리하다.

 

정점간의 연결정보가 많지 않다면,  배열 크기가

크기로 할당된 배열의 거의 사용되지 않기 때문이다.

 

인접리스트는 필요한 만큼만 쓰기 때문에 상관이 없다.