티스토리 뷰

공부자료

[알고리즘] 그래프 Graph

임다솜 임다솜 2016.11.30 11:51

그래프의 개념적 정의

그래프는 자료구조

연결되어 있는 객체의 관계를 표현하는 자료구조



그래프의 수학적 정의

그래프 : G = (V, E)

V(G) : 정점 (set of vertices)

E(G) : 간선 (set of edges, 정점을 연결하는 선)



그래프의 종류


무방향 그래프(Undirected Graph)

정점을 연결하는 선에 방향이 없다. 즉, (Vi, Vj) == (Vj, Vi) 이다.



방향 그래프(Directed Graph)

정점을 연결하는 선에 방향이 있다. 즉, (Vi, Vj) != (Vj, Vi) 이다.




가중치 그래프(Weighted Graph)

간선이 값을 가지는 그래프.


     



비가중치 그래프(Unweighted Graph)

간선이 값을 가지지 않는 그래프





그래프 알고리즘의 실생활 사용


쿠팡맨이 물류센터를 들렀다가, 본사를 들른 뒤 고객에게 도착할 때 가장 빠른 경로는?



--> 가중치, 무방향그래프



양재역에서 역까지 가장 빠르게 도착할 수 있는 경로는? 혹은 환승을 가장 적게 할 수 있는 경로는?


--> 최단 가중치 경로 : 가중치, 무방향 그래프(?)

--> 최소 정점 경로 : 비가중치, 무방향 그래프(?)



지도에 나라별로 색칠을 하려고 한다. 단, 인접한 나라는 같은 색을 사용하지 않는다. 이 때 필요한 색의 최소 가지수는?




청소차가 도로를 청소해야 한다. 모든 도로를 한번씩만 지나도록 효율적으로 청소차를 운행하는 방법은?


--> 한붓그리기! 무방향, 비가중치 그래프



게임에서 스킬 트리를 구성할 때 어떻게 구성할까?



--> Directed Acyclic Graph 라는 그래프 이론을 사용한다.











댓글
댓글쓰기 폼
공지사항
Total
41,170
Today
70
Yesterday
59
링크
TAG
more
«   2018/07   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함