지난 학기들의 기록59 [강의노트] 그래프 순회 -2 (BFS) 그래푸 순회 - 2(BFS) 지난 포스트에서는 DFS에 다루어보았고, 이번에 배울것은 BFS 너비우선탐색이다. 마찬가지로 그래프 순회 기법이다. BFS - 너비우선탐색 너비우선탐색에서 가장 핵심적인 단어를 꼽자면 level 이라고 생각한다. 이 얘기는 뒤에 몇번 더 언급하겠다. BFS는 트리의 level 별로 순회를 한다. 즉 트리에서 루트노드를 기준으로 자식노드로 계속 내려가는 것을 깊이우선탐색이라고 한다면, 기준노드에서 형제노드를 우선적으로 탐색하는 것이 너비우선탐색이다. DFS와는 탐색의 방향성 측면에서 어떻게 보면 반대의 개념이라고도 생각할 수 있다. BFS를 확장해서 해결 가능한 문제를 살펴보자. 두개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾을 수 있다고 한다. 그래프 내 싸이클을 .. 2021. 11. 17. [강의노트] 그래프 순회 - 1 (DFS와 싸이클찾기) 그래프 순회 - 1 그래프를 구현하는 문제에 대해서 지난 시간에 해결해보았다. 이번에 배울것은 그래프 순회이다. 깊이우선탐색과 너비우선탐색은 내가 알고리즘을 공부하기전에도 매우 자주 듣던 익숙한 단어이다. 그만큼 중요한 개념이니 꼼꼼하게 공부해두자. 그래프 순회 문제 상황을 그래프로 표현했으면, 그 데이터를 효과적으로 이용하기 위해서는 순회하는 과정이 꼭 필요하다. 그래프를 순회한다는 것은 정점과 간선을 순회한다는 것이므로, 이를 이뤄낼 수 있는 어떤 체계적인 절차가 필요하다. 대표적인 두가지 절차인 깊이우선탐색과 너비우선탐색을 배워보게 된다. 깊이우선탐색(DFS) 먼저 DFS에 대해서 알아보자. DFS 는 depth-first search 의 준말로 그래프를 순회하는 일반적인 기법이다. DFS순회로 가.. 2021. 11. 10. [강의노트] 무방향 그래프 구현 - 3 (가중치 수정) 보호되어 있는 글 입니다. 2021. 11. 7. [강의노트] 무방향 그래프 구현 - 2 그래프 구현 - 2 이번 포스트에서는 실제로 그래프를 구현해보는 작업을 할 것이다. 인접리스트를 이용한 상세구현(연결리스트 사용) 아래의 그림은 인접리스트와 인접행렬의 상세구현 방법을 보여주고 있다. 내가 실제로 구현해볼 그래프의 모습은 아래와 같다. 위의 그림을 참고해서 아래의 그래프를 구현해볼 것이다. 그림을 토대로 먼저 구조체 틀을 짜보자 간선에 대한 구조체 struct edge 1. 시작 정점(시점)에 대한 포인터 2. 끝 정점(종점)에 대한 포인터 3. 가중치 정보 (또는 간선이 담고있는 정보, 그림에선 a 또는 b) 4. 다음 간선을 가리키는 포인터 typedef struct edge { int weight; // 가중치 정보 struct edge *next ; //다음 간선을 가리키는 포인터.. 2021. 11. 6. 이전 1 2 3 4 5 ··· 15 다음
