[Coding_Test] Graph 설명

Graph

그래프 G(V,E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료구조이다.

그래프의 활용

현실 세계의 사물이나, 추상적인 개념 간의 연결 관계를 표현한다. 그래프는 현실의 문제를 해결하기 위한 도구로써 유용하게 이용된다.

• 도시들을 연결하는 도로망: 도시(vertex),도로망(edge)
• 지하철 연결 노선도: 정거장(vertex), 정거장을 연결한 선(edge)
• 컴퓨터 네트워크 : 각 컴퓨터와 라우터(vertex), 라우터간의 연결 관계(edge)
• 소셜 네트워크 분석: 페이스북 계정(vertex), follow 관계(edge)

그래프 표현방법

인접리스트(adjacency list) 인접행렬(adjacency matrix) 암시적 그래프(implicit graph)

그래프 순회(Traversal)

그래프 순회란 그래프 탐색(Search)라고도 불리고, 그래프의 각 정점을 방문하는 과정을 말한다. 그래프 순화에는 크게 깊이 우선탐색과 너비 우선탐색이 2가지 알고리즘이 있다.

너비 우선 탐색(Breadth-first search, BFS)

깊이 우선 탐색(Depth-first search, DFS)

참조 : 개발남노씨 자료구조