그래프(Graph)

그래프의 정의

그래프는 정점(노드)와 간선(엣지)의 집합으로 이루어진 자료구조를 의미한다. 간선은 한 쪽 방향으로만 이동 가능한 단방향 그래프와 양 방향으로 모두 이동 가능한 무방향 그래프로 나뉘어진다. 

ㅇ

 

그래프 용어

 

부그래프

그래프 G=(V,E)의 부그래프 G'=(V',E')은 V'는 V의 부분집합, G'는 G의 부분집합인 그래프를 의미한다. 

 

완전그래프

완전그래프는 모든 정점 사이에 엣지가 있는 그래프이다.

노드 수에 따른 완전 그래프

 

연결그래프

그래프의 정점들 중 임의의 두 정점 u1,u2에 대하여 u1부터 u2까지의 경로가 존재하는 그래프이다. 만약 그래프가 단방향그래프이고 u1부터 u2까지의 경로가 존재한다면 해당 연결그래프를 강연결그래프라고 한다.

 

 

그래프 표현

그래프의 정접 집합 V={v0, v1, v2 ... v(n-1)}에서, n개의 정점들을 정수 0부터 차례대로 대응시켜 표현한다.

 

인접행렬 표현

각 노드 번호에 따라 가는 엣지가 존재하는 경우는 1, 없는 경우는 0으로 행렬을 통해 표현한다. 무향그래프인 경우에는 N(row)==N(col)을 기준으로 대칭적이다.

 

인접리스트 표현

포인터 배열을 이용하여 Vi 노드에서 엣지로 연결된 노드들을 연결리스트로 표현한다.