BFS1 [알고리즘/C++] - 그래프/BFS 와 DFS 이전 글에 이어서 그래프의 종류 중 하나인 BFS,DFS를 알아보도록 하겠습니다.사실 이야기하자면 DFS와 BFS는 그래프보다는 그래프 탐색기법이라고 생각하셔야 합니다.먼저 이전시간에서 그래프의 정의만 알아보고 그래프를 구현하는 방법에 대해서 알아보지 않았었는데, 그래프를 구현하는 구조 세가지를 알아보도록 하겠습니다. 연결선 리스트:간선을 중심으로 그래프를 나타내는 방식입니다.각 노드에 대해 인접한 노드들의 리스트를 유지하는 구조입니다.간선 수에 비례하여 공간을 사용하므로 희소 그래프에 자주 활용됩니다.각 간선을 (u,v)형태로 저장하며 그래프의 간선들을 리스트로 표현하기에 단순한 구조를 가집니다.그래프의 간선 개수가 중요할 때 사용되며, 간선 기반 연산에 유리합니다.반두 노드의 연결 여부를 확인하기 .. 2024. 9. 6. 이전 1 다음
