1. 그래프의 개요
non-linear data structure로
이런식으로 생긴 걸 말한다. 위의 각 점들을 node 혹은 vertex라고 하고, 잇는 선을 edge라고 한다. degree는 각 node의 edge의 개수를 얘기한다.
edge가 양방향이면 undirected, 방향성이 있으면 directed graph or di-graph 라고 한다. 우측 directed 의 파란색 node를 보면 자기 자신에게 방향을 쏘는데 이를 self-loop이라 한다.
좌측의 그래프의 빨간색 화살표처럼 사이클을 돌아서 같은 node를 1번이상 get하게 될 때도 있는데 이를 cyclic node라 한다.
다른 글에서 또 다룰 tree란 data structure는 acyclic undirected graph 라고 할 수 있다.
그래프에서 isolated된 node가 있으면 disconnected, 모든 node가 1개 이상의 edge를 가지고 있으면 connected, 모든 node가 다른 모든 node들과 edge로 연결돼 있으면 complete graph이라 한다.
2. 그래프 적용
각각의 edge가 values/cost 를 가지고 있을때 이를 weighted graph라 한다.
weighted graph가 적용되는 예를 들자면,
비행기 교통
Node/vertex = 공항
Edges = 두 공항 사이를 직접 다니는 항공
Weight = 공항 사이 거리
GPS Navigation
Node = 길의 교차로
Edge = 길
Weight = 교차로 끼리 걸리는 시간
Networks routing
Node = 서버
Edge = data 연결
Weight = 연결 스피드
이 밖에도 graph가 적용되는 예는
Electronic circuits
Flight reservations
Driving directions
Telcom: Cell tower frequency planning
Social networks. E.g., Facebook uses a graph for suggesting friends
Recommendations: Amazon/Netflix uses graphs to make suggestions for products/movies
Graphs help to plan the logistics of delivering goods
등이 있다.
3. 그래프의 표현
Graph는 Adjacency matrix나 Adjacency list 로 표현하는데
Adjacency matrix는 아래와 같이 표현되는 걸 얘기하고,
Adjacency list는 아래와 같은 식으로 표현되는 걸 얘기한다.
4. 함수
https://adrianmejia.com/data-structures-for-beginners-graphs-time-complexity-tutorial/
5. Breadth-first search (BFS)
6. Depth-first search (DFS) — Graph search
Reference: https://adrianmejia.com/data-structures-for-beginners-graphs-time-complexity-tutorial/
