지난 학기들의 기록/알고리즘28 [강의노트] 그래프 순회 - 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 그래프 - 1 알고리즘에서 정말 중요한 추상 자료형인 그래프를 배워보자 그래프 ADT 그래프 추상 자료형은 정점과 간선 정보쌍을 가지고 있는 자료형이다. 아래 그림을 통해 이해하면, 정점은 공항도시의 이름 간선은 정점사이의 거리를 저장하게 된다. 이때 정점은 vertex 의 V로, 간선은 edge의 E라고 앞으로 칭할 것이다. 그래프는 간선의 방향성에 따라서 방향간선과 무방향 간선으로 구분된다. 아래의 예시는 정점 인천과 LA, 그리고 두 정점을 있는 간선을 보여주고 있다. 첫번째 예시는 간선에 방향이 있고, 두번째 예시는 방향이 없다 이때 방향이 있는 간선을 방향간선 그래프라고 한다. 정점에 방향성이 추가되었으므로 시작 정점을 시점 도착 정점을 종점이라고 부른다. 예시에서는 인천에서 LA로 가는 비행기.. 2021. 11. 5. 이전 1 2 3 4 5 ··· 7 다음
