Graph2 너비 우선 탐색(bfs) bfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32를 참고 하자. 너비 우선 탐색(bfs) BFS(Breadth First Search) 이름 뜻 그대로 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 장점 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다. 단점 재귀 호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색할 노드들을.. 2022. 3. 11. 그래프(Graph) 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현한 것 일반적이고 강력한 자료구조 정점(Node or Vertex)과 간선(Edge or Branch)으로 구성 G=(V, E)로 표현 가능 , V: 정점 집합 / E: 간선 집합 주요 용어 정리 경로 Path 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것 단순 경로: 경로 중 한 정점을 최대 한 번만 지나는 경로 의미(일반적) ex) A --> E로 가는 경로 A --> B --> E A --> B --> C --> E A --> B --> D --> E 사이클 cycle 시작한 점에서 끝나는 경로 a.k.a. ‘회로’ 단순 사이클: 같은 정점을 두 번 이상 방문하지 않는 사이클 (일반적 / 시작점 제외) ex) 단순 사이클 A --> B -.. 2022. 3. 11. 이전 1 다음
