bfs

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.그래프는 연결 관계를 표현하는 자료구조이다. 네트워크, 운영체제 등 다양한 분야에서 범용적으로 사용하며, 알고리즘 분야에서도 자주 나오는 굉장히 중요한 자료구조라고 할 수 있다. 한 번 알아보자.1. 그래프의 종류와 구현그래프란 정점(vertex)이라 불리는 데이터를 간선(edge) 혹은 링크(link)로 연결한 형태의 자료구조를 의미한다. 이전 시간에 학습했던 트리구조 역시 노드와 노드를 간선으로 연결했었던 그래프의 일종으로, 노드 간의 상하 관계를 고려한 그래프라고 할 수 있다. 일반적인 그래프는 사이클(어떤 정점에서 다시 돌아올 경로가 있는 경우)을 형성하거나, 이웃한 정점끼리 별도의 상하 관계를 가지지 않는다.그래프는..

1. 그래프란? 그래프는 '노드 (Node) 와 각각의 노드를 연결하는 간선(Edge)'으로 구성된 자료구조이다. 쉽게 설명하면 각각의 객체들과 그것을 잇는 선들의 집합이라고 생각하면 된다. 실생활에서 우리가 대표적으로 보는 그래프 형태의 이미지는 지하철 노선도를 떠올릴 수 있다. 각각의 역과 역을 잇는 선들의 집합으로 그래프의 형태를 이루고 있다고 이해하면 알기 쉽다. 그래프는 또한 다음과 같은 다양한 특성을 지닌다. 노드(Node)는 다른 이름으로 정점(Vertex)라고도 불린다. 연결 방향에 따라서 양방향, 단방향, 무방향이 될 수 있다. 넓은 범위에서는 트리 역시 그래프의 일종이다. 인접 : 두 개의 노드가 간선으로 직접 연결되어 있는 상태를 말한다. 가중치 : 간선에 따라 할당된 값 또는 비용을..