그래프 (Graph)

 

Graph

그래프는 객체 간의 관계를 표현하는 자료구조입니다.

엣지(edge)라는 개념을 사용하여 노드(node)라고 불리는 객체를

연결하여 저장하고 효율적으로 검색할 수 있도록 합니다.

 

 

엣지로 두 노드를 연결할때 방향성이나 가중치를 가질 수 있습니다.

하나의 방향으로 이동한다면 방향 그래프 (Directed Graph)

양방향으로 이동한다면 무방향 그래프 (Undirected Graph)

엣지에 가중치가 할당되었다면 가중 그래프(Weighted Graph)

Directed / Undirected / Weighted

 

 

그래프 표현방법

그래프를 표현하는 방법을 여러가지가 있지만

대표적으로 인접행렬(Adjacency Matrix)과 인접리스트(Adjacency List)가 있습니다.

 

 

 인접행렬 - Adjacency Matrix 

 

 인접 리스트 - Adjacency List 

 

 

 

데이터 탐색방법

데이터의 연결을 배열 또는 리스트로 저장하여

queue 또는 stack으로 자료를 검색하게 됩니다.

queue로 검색하는 방법을 BFS(Breadth-First Search)라고 하고,

stack으로 검색하는 방법을 DFS(Depth-First Search)라고 합니다.