C언어 알고리즘 - 그래프 개요, 정의, 종류

그래프 개념

큐와 스택은 대개 선형으로 구성된 자료를 프로그램으로 표현하기 위해 고안되었고, 앞 발표에서 다룬 트리는 선형으로 표현하기 힘든 구조인 계층 구조를 표현하기 위해 고안된 자료 구조입니다. 그러나 그래프는 부모 자식 관계에 제약이 없기 때문에 좀 더 일반적이고 현실 세계의 문제를 푸는 데 유용하게 사용됩니다.

현실 세계의 문제는 보통 도로망, 사람 관계, 웹사이트 링크 관계 등등이 있습니다.

그래프 정의

>어떤 자료나 개념을 표현하는 정점들의 집합과 정점을 연결하는 간선들의 집합으로 구성된 자료 구조<

일단 정의는 이런데 여기서 유의할 것은 정의에 정점의 위치 정보나 간선의 순서가 포함되지 않아서 아래 그래프들은 모두 같다고 할 수 있습니다.

그래프 사용 예

한 붓 그리기 – 깊이 우선 탐색으로 가능

외환 거래 – 만원을 유로로 바꾸고 엔으로 바꾸고 다시 한화로 바꿨을 때 만원보다 큰 돈을 버는 것을 아비트러지라고 하는데 그래프로 환율 목록에서 어디서 아비트러지가 존재하는지 알 수 있음. 최단 거리 알고리즘

소셜 네트워크 분석 – 몇 다리를 건너면 문재인이랑 내가 아는 사이인지. 너비 우선 탐색

그래프 종류

>무방향 그래프

간선에 방향성이 없다

화살표가 없는 간선들로 이루어져 있으며 순서가 없다

커플

>방향 그래프

각 간선에 방향이 있는 그래프

짝사랑, 일방 통행 도로

>루프 그래프

한 노드에서 출발한 간선이 다시 돌아오는 상태를 가진 그래프

>완전 그래프

모든 노드가 연결되어 있음

간선=n

간선의 수 = n(n-2) / 2

>다중 그래프 

노드들 사이에 간선이 두 개 이상인 그래프

>종속 그래프

어떤 한 그래프에 모든 정점과 간선들이 완벽하게 겹쳐지는 그래프

g랑 g1은 종속

g2와 g3는 종속

>가중치 그래프

간선에 가중치가 부여된 그래프