그래프3 [알고리즘] [15] 그래프 순회 1. 그래프 순회 비선형 구조인 그래프의 모든 정점을 빠짐없이 탐색하는 것 너비 우선 탐색과 깊이 우선 탐색으로 순회할 수 있다. 2. BFS (Breadth First Search) 탐색 시작점의 인접 정점을 모두 방문한 이후, 방문한 정점을 시작점으로 하여 차례로 방문한다. 그래프는 계층형 구조가 아니기 때문에 루트의 개념이 없어 임의의 정점에서 시작 가능하다. 선입선출 형태의 큐를 활용한다. 2024. 2. 16. [알고리즘] [14] 그래프 1. 그래프 아이템 (사물 또는 추상적 개념)들 사이의 연결 관계를 표현한 것 정점 (Vertex) : 그래프의 구성 요소로 하나의 연결점 간선 (Edge) : 두 정점을 연결하는 선 차수 (Degree) : 정점에 연결된 간선의 수 그래프는 정점과 간선의 집합으로 구성된 자료구조 선형 자료구조나 트리 자료구조로 표현하기 어려운 N 대 N 관계의 원소들을 표현하기 용이하다. 그래프 유형 무향 그래프(Undirected Graph) : 최대 간선의 개수는 V*(V - 1) / 2이다. 유향 그래프 (Directed Graph) 가중치 그래프 (Weighted Graph) 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph) 완전 그래프 : 정점들에 대해 가능한 모든 간선을 가지는 .. 2024. 2. 15. [알고리즘] [3] BFS 1. 그래프 탐색 그래프는 노드 (Node)와 간선 (Edge)으로 이루어진 자료구조이다. 그래프 탐색은 그래프에서 특정 조건을 만족하는 노드를 찾거나, 모든 노드를 방문하는 데 사용한다. BFS와 DFS는 가장 일반적인 그래프 탐색 알고리즘이다. 2. BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 특정 노드에서 인접한 노드를 모두 방문한 다음, 다음 레벨의 인접 노드로 이동하는 방법 자료구조 큐(Queue)를 사용하여 구현한다. BFS는 재귀적으로 작동하지 않는다. BFS는 어떤 노드의 방문 여부를 반드시 검사해야 한다. DFS는 무한한 길이를 가지는 경로에 도달했을 시 탐색 목표가 현재 경로에 있지 않다면 무한 루프에 빠질 수 있.. 2024. 1. 18. 이전 1 다음
