자료구조-그래프

그래프란?

노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조

즉 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.

 

용어 정리

정점,노드(Vertex,Node)	데이터가 저장되는곳
간선	정점,노드를 연결하는 선으로 Link ,branch 라고도 불림
인접 정점	간선에 의해 직접 연결된 정점 ex(1,4 는 인접 정점)
단순 경로	경로 중에서 반복되는 정점이 없는 경우 ex)한붓그리기와 같이 같은 간선을 지나지 않는경로
차수	무방향 그래프에서 하나의 정점에 인접한 정점의 수 (1의 차수는 3)
진출 차수	방향 그래프에서 외부로 향하는 간선의 수
진입 차수	방향 그래프에서 외부에서 들어오는 간선의 수
경로 길이	경로를 구성하는데 사용된 간선의 수
사이클	단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

그래프의 종류

이름	설명	이미지
무방향 그래프	두 정점을 연결하는 간선에 방향이 없는 그래프
방향 그래프	간선에 방향이 있는 그래프
완전 그래프	한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프
부분 그래프	기존 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프
가중 그래프	정점을 연결하는 간선에 가중치를 할당한 그래프
유향 비순환 그래프	방향 그래프에서 사이클이 없는 그래프
연결 그래프	떨어져 있는 정점이 없는 그래프
단절 그래프	연결되지 않는 정점이 있는 그래프

그래프 구현

그래프를 구현하기 위해서는 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 한다.

그래프를 표현하는 방법은 순차 자료구조 방식을 이용한 2차원 배열의 인접 행렬 방법과

연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있다

 

인접 행렬그래프 자체를 2차원 배열 형태로 나타낸 것으로연결되어있으면 1 아니면 0으로 표현한 행렬이다.

2차원 배열에 모든 정점들의 간선 정보가 있기 때문에 두 정점을 연결하는 간선을 조회할 때 O(1) 시간 복잡도로 가능하다.정점의 차수를 구할 때는 O(n)의 시간 복잡도를 가진다

 

n개의 정점을 가지는 그래프를 n*n인접 행렬로 표현하면 간선의 개수에 상관없이 항상 n*n개의 메모리를 사용한다그래프에 간선이 많은 경우에는 큰 문제가 없겠지만 정점의 개수에 비해 간선의 개수가 적은 희소 그래프인 경우에는메모리 낭비 문제가 발생한다

 

모든 간선의 수를 알아내려면 인접 행렬 전체를 확인해야 하므로 O(n^2)의 시간 복잡도를 가짐