[자료구조]그래프(Graph)란 무엇인가?

그래프(Graph)의 개념

-정점(vertex)과 간선(edge)으로 구성된 한정된 자료구조

-즉, 그래프는 정점과 정점 사이를 연결하는 간선으로 이루어져 있습니다.

-그래프는 흔히 G=(V, E)로 표현되며, V와 E는 각각 정점의 집합, 간선의 집합을 의미합니다.

 

그래프 예시

 

그래프의 유형

-그래프는 특징에 따라 여러 가지 유형이 있습니다. 

 

1. 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)

-간선에 방향성이 있냐 없냐에 따라서 방향 그래프와 무방향 그래프로 나뉩니다.

-방향 그래프의 간선에는 방향이 있고, 화살표로 표시가 됩니다.

-무방향 그래프의 간선에는 방향이 없고, 그냥 실선으로 표시가 됩니다.

 

2. 완전 그래프(Complete Graph)

-각 정점이 다른 모든 정점들과 연결되어 있는 그래프

-최대 간선 수를 가진 그래프이다.

-정점의 개수가 n개일 때,

• 방향 그래프는 n(n-1)개의 간선을 가지고,
• 무방향 그래프는 n(n-1)/2개의 간선을 가진다.

 

3. 부분 그래프(Subgraph)

-기존 그래프에서 일부 정점이나 간선을 제외한 그래프

 

4. 연결 그래프(Connected Graph)

-모든 정점들이 간선으로 연결된 그래프(하나의 덩어리)

 

5. 단절 그래프(Disconnected Graph)

-모든 정점들이 하나로 연결되지 않은 그래프

 

6.가중치 그래프(Weighted Graph)

-각 간선에 가중치가 부여되어 있는 그래프

 

7. 사이클이 없는 방향 그래프(Directed Acyclic Graph)

-말 그대로, 사이클이 없는 방향 그래프를 말한다.

 

 

 

 

그래프 관련 용어

1. 인접 : 두 정점을 연결하는 간선이 존재하면 두 정점은 서로 인접하다고 합니다.
2. 부속 : 어느 간선이 어느 정점을 연결하고 있으면 그 간선은 그 정점에 부속되어 있다고 합니다.
3. 차수(degree) : 어느 정점에 부속된 간선의 수를 그 정점의 차수라고 합니다.
4. 경로(path) : 그래프에서 간선을 따라 갈 수 있는 길을 경로라고 합니다. 
5. 경로 길이 : 경로를 구성하는 간선의 길이를 말합니다.
6. 단순 경로 : 모두 다른 정점으로 구성된 경로를 단순 경로라고 말합니다.
7. 사이클(cycle) : 단순 경로 중에서 시작 정점과 끝 정점이 같은 경로를 사이클이라 말합니다.