목록그래프의 순환 (1)

DNF LOVE

[자료구조 - 그래프의 순환] 코딩 테스트의 꽃 그래프의 순환 BFS와 DFS

그래프는 비선형 자료구조이기 때문에 배열처럼 단순한 반복으로 그래프를 조회하는 것은 비효율적이다. 그래프는 각 정점 간의 연결 관계를 사용해 조회하는 방법을 사용한다.(한 정점에서 연결된 다른 정점으로 이동하며 조회한다.) 깊이 우선 탐색(Depth First Search) 너비 우선 탐색(Breadth First Search) [깊이 우선 탐색 - DFS] 깊이 우선 탐색이란? 하나의 경로로부터 도달할 수 있는 모든 노드를 방문한 이후 다른 경로를 조회하는 방법이다. 한 노드로부터 발생하는 모든 경로를 탐색할 때까지 해당 노드 정보는 유지한다. 모든 경우의 수를 검사하거나, 규칙이 복잡한 경로를 탐색할 때 유리하다. 현재 정점에서 갈 수 있는 점들 중 한 곳을 우선적으로 끝까지 탐색한다. 한 번에 하나..
Computer Science/자료구조 2019. 9. 20. 19:52
이전 Prev 1 Next 다음