그래프(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가 실행되기 때문에, 하나로 해도 되는데 그냥..
DFS(Depth-First Search) : 깊이 우선 탐색 그래프 완전 탐색 : 모든 노드를 방문하고자 할때, 이 방법을 선택한다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후, 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 재귀함수 또는 Stack 자료구조를 이용한다. 재귀함수를 이용하므로 stack overflow에 유의해야 한다. 스택 오버플로우(stack overflow)는 지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다. 1. 시간복잡도 (노드 수: N, 에지 수 E) 인접 리스트 노드의 개수가 많고, 간선 수가 적을 때 유리하다. 인접 행렬 노드의 개수가 적고, 간선 수가 많을 때 ..
