그래프 - 개념/ 주요 용어 정리

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

 

1. 그래프의 정의

: 객체 사이의 연결 관계를 표현하는 자료구조

ex. 지하철 노선도, 전기회로, 운영체제 프로세스와 자원 그래프, 트리

 

2. 그래프의 구조

그래프(G; graph) = 정점(V; vertex) + 간선(E; edge) <==> G = (V,E) 

- V(G): 그래프 G의 정점들의 집합

- E(G): 그래프 G의 간선들의 집합

- 정점 = vertex = node

- 간선 = edge = link

 

3. 그래프의 종류

1) 무방향 그래프 undirected graph

- 간선을 통해서 양쪽 방향으로 갈 수 있음.

- 정점 A,B 연결하는 간선 ==> (A,B) = (B,A)

 

2) 방향 그래프 directed graph

- 간선을 통해서 한쪽 방향으로만 갈 수 있음.

- 정점 A-->B 간선 ==> <A,B> =/= <B,A>

 

3) 가중치 그래프 weighted graph

- 네트워크

- 간선에 가중치 또는 비용이 할당된 그래프

 

4) 부분 그래프 sub graph

- 어떤 그래프의 정점의 일부 + 간선의 일부

 

5) 연결 그래프 connected graph

- 모든 정점쌍에 대해 항상 경로가 존재할 때

--> 트리: 사이클을 가지지 않는 연결 그래프

 

6) 완전 그래프 complete graph

- 모든 정점이 서로 연결되어 있는 그래프

   @무방향 그래프 -> 정점 수 = n --> 간선의 수 = n*(n-1)/2

 

4. 그래프의 주요 용어 정리

1. 인접정점 adjacent vertex

- 간선 하나만 건너면 바로 있는 정점

 

2. 정점의 차수 degree

1) 무방향 그래프

: 그 정점에 인접한 정점의 개수

2) 방향 그래프

- 진입 차수 in-degree

: 특정 정점을 기준으로, '나'에게 들어오는 화살표 개수 

- 진출 차수 out-degree

: 특정 정점을 기준으로, '나'로부터 나가는 화살표 개수

 

3. 경로

정점 a부터 z까지의 경로 ==> (a,b) (b,c) (c,d) ... (x,y) (y,z) 

- 단순경로 simple path: 경로 내에 반복되는 간선이 없는 경우 

- 사이클 cycle: 단순경로의 시작정점과 종료정점이 동일한 경우