그래프는 실제 세계의 현상이나 사물을 정점(Vertex)
또는 노드(Node)
와 간선(Edge)
로 표현하기 위해 사용되는 자료구조입니다. 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트(root)노드, 부모와 자식이라는 개념이 존재하지 않습니다.
다음 그림은 실생활에서 그래프의 예를 표현한 것입니다.
이처럼 집에서 회사까지 가는 최단 경로를 구한다는 것과 같이 알고리즘을 그래프로 구현할 수 있습니다. 그림에서 보이는 것과 같이 '집', '지하철', '버스' 그리고 '회사' 와 같이 원으로 표현된 것을 정점 또는 노드라고 부르고 방향을 나타내는 선을 간선이라고 부릅니다.
그래프를 본격적으로 설명하기 앞서 그래프와 관련된 용어를 정리해 보겠습니다.
그래프와 관련해서 더 많은 용어들이 있지만 지금은 학술적으로 deep하게 알려고 하는 것이 아닌 그래프를 이해하기 위함이기 때문에 그래프의 기본적인 용어들만 적었습니다.
그래프는 특성에 따라 여러가지 종류로 나누어집니다. 대표적인 그래프의 유형은 다음과 같습니다.
첫 번째는 무방향 그래프
와 이와 반대되는 방향 그래프
입니다.
간선에 비용 또는 가중치가 할당된 그래프로 예를 들어서 맨 왼쪽을 '집', 오른쪽을 '회사'라고 보면 '4'와 '5'의 비용을 들이는데 반해서 '2'와 '1'의 비용을 들이면 더 적게 든다는 것을 판단할 수 있습니다. 이를 위해서 간선에 가중치가 들어가 있는 그래프를 가중치 그래프
또는 네트워크
그래프라고 합니다.
연결 그래프
는 우선, 무방향 그래프이어야 하고 무방향 그래프에 있는 모든 노드가 연결할 수 있는 경로가 존재하는 그래프입니다. 반면에 특정 노드에 대해서 경로가 존재하지 않는 그래프는 비연결 그래프
라고 합니다.
예를 들면, 아래의 그래프와 같이 노드는 4개인데 오른쪽에 간선으로 연결되어 있는 노드는 접근이 가능하지만 다른 노드에서 왼쪽 노드로 갈 수 있는 존재하지 않습니다. 이런 경우에 비연결 그래프라고 합니다.
사이클
은 위의 용어 정리에서 볼 수 있듯이 단순 경로의 시작 노드와 종료 노드가 동일한 경우입니다. 그리고 그렇지 않은 경우를 비순환 그래프
라고 합니다.
예를 들어서 위의 예시로 있는 그래프는 딱 봐도 비순환 그래프인 것을 알 수 있습니다.
완전 그래프
는 그래프에 있는 모든 노드가 서로 연결되어 있는 그래프를 말합니다.
그래프가 무엇인지 설명했을 때 그래프는 트리와는 다르다고 설명했습니다. 트리는 그래프 중에 속한 특별한 종류라고 볼 수 있습니다. 즉, 그래프라는 큰 정의안에 트리가 들어가 있다라고 보시면 될 것 같습니다. 다음 표는 그래프와 트리의 특징을 나타낸 것입니다.
그래프 | 트리 | |
---|---|---|
정의 | 노드와 노드를 연결하는 간선으로 표현되는 자료 구조 | 그래프의 한 종류, 방향성이 있는 비순환 그래프 |
방향성 | 방향 그래프, 무방향 그래프 둘다 존재함 | 방향 그래프만 존재함 |
사이클 | 사이클 가능함, 순환 및 비순환 그래프 모두 존재함 | 비순환 그래프로 사이클이 존재하지 않음 |
루트 노드 | 루트 노드 존재하지 않음 | 루트 노드 존재함 |
부모/자식 관계 | 부모 자식 개념이 존재하지 않음 | 부모 자식 관계가 존재함 |
Reference