그래프(Graph) 그래프는 정점 와 간선로 이루어진 자료구조이다. 이는 트리(Tree)와 같지만, 트리는 Acyclic(사이클 x)인 반면 그래프는 사이클이 존재한다. (Cyclic) 각 정점(Vertex)들이 간선(Edge)들로 연결되어, 연결된 정점 간의 관계를 표현할 수 있는 자료구조이다. 그래프의 구조(용어) 정점(Vertex) : 노드 간선(Edge) : 각 노드간의 연결 선 ( = link, branch) 인접 정점(Adjacent Vertex) : 간선 하나만을 통해 바로 연결되어 있는 정점 (정점 1과 정점 4는 인접정점 x) 무방향 그래프 정점의 차수(Degree) : 하나의 정점에 인접한 정점의 수 (정점 1의 차수는 2 ), (정점 A의 차수는 3) 무방향 그래프에서 모든 정점 차수..
Comments DFS와 BFS를 공부하는 중에, 쉬운 예제이지만 두개를 동시에 요구하는 문제가 있어서 한번 풀어봤다. 아래 코드가 길고 main은 초기화 / BFS메소드 / DFS 메소드로 딱 나뉘어져서 제목을 달아놨다. 0) static 변수들 각 노드에서 갈수 있는 노드를 인접리스트로 초기화 하는 것은 동일하지만, visited 배열은 따로 선언해야한다. - boolean[] dfsVisited / boolean[] bfsVisited ArrayList 형 배열 lists을 선언한다. Queue queue : BFS 알고리즘에서 사용할 Queue 자료구조 이다. 출력에 이용할 StringBuilder도 따로 선언했다. ( DFS가 모두 실행된 뒤에 BFS가 실행되기 때문에, 하나로 해도 되는데 그냥..
BFS(Breadth-First Search) : 너비 우선 탐색 그래프 완전 탐색 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. FIFO 탐색 -> Queue 자료구조를 이용한다. 목표 노드에 도착하는 경로가 여러개일 때 최단경로를 보장한다. 1. 시간복잡도 인접 리스트 노드의 개수가 많고, 간선 수가 적을 때 유리하다. 인접 행렬 노드의 개수가 적고, 간선 수가 많을 때 유리하다. 인접 리스트 인접 행렬 특정 간선 검색 O(degree(N) : 해당 노드의 차수 O(1) 정점의 차수 계산 O(degree(N)) O(N) 전체 노드 탐색 O(E) O(N^2) 메모리 N+E N^2 2. BFS 핵심 이론 1) 방문여부 확인용 배열 BFS도 DFS와 ..
