[알고리즘/C++] - 그래프

그래프

: 노드와 노드를 연결하는 간선으로 구성된 자료구조

 

그래프를 살피기 전에 먼저 용어부터 알아봅시다

 

• 정점(Vertex): 그래프의 노드입니다.
• 간선(Edge): 두 정점을 연결하는 선을 부르는 용어입니다.
• 가중치(Weight): 간선에 부여된 값으로, 거리나 비용 등을 의미할 수 있습니다.
• 경로(Path): 정점들의 순서로, 각 연속적인 정점 쌍 사이에 간선이 있는 경우 나타낼 수 있습니다.

특징

• 순환 혹은 비순환 구조입니다.
• 방향이 있을 수도 있고 없을 수도 있습니다..
• 부모 자식 관계가 없습니다.
• 2개 이상의 경로가 가능합니다.
• 그래프는 연결되어 있을 수도 있고, 연결되어 있지 않을 수도 있습니다. 이 여부에 따라 연결 그래프와 비연결 그래프로 나뉘기도 합니다.

그래프의 종류

• 가중 그래프: 가중치가 존재하는 그래프
• 무향 그래프: 그래프의 모든 정점이 서로 연결되지 않은 경우
• 유향 그래프: 모든 그래프가 서로 연결되어 방향이 있는 경우
• 완전 그래프: 특수 그래프 중 하나로모든 정점 쌍 간에 간선이 존재할 때

이 외에도 다중 그래프, 유향 다중 그래프 등 다양한 그래프들이 존재합니다.

우리는 자세히 종류에 대해서 알기보다는 그래프 자체에 초점을 두고 그래프의 특징을 알고 넘어갑시다.

 

모든 트리는 그래프라는 점을 잊지마세요!!(반대는 성립x)

그래프의 활용

그래프 탐색 알고리즘 : DFS,BFS

그래프 응용: 최소 신장 트리(MST), 다익스트라 알고리즘, 교통망 등

 

광범위한 개념을 가지고 있는 그래프기에 그래프에 대한 설명은 이정도로만 짧게 마치고,

조금 더 세부적으로 들어가 해당 그래프에 대한 개념을 살펴보는 방식으로 진행하겠습니다.

반응형