빼미의 개발일기

깊이 우선 탐색 (Depth First Search - DFS) - 시작 정점을 기준으로 '더 들어갈 길이 보이지 않을 때까지 깊이 들어가는 방식'의 그래프 탐색 알고리즘 ◆ DFS의 동작 방식 시작 정점을 시작으로 정점에 '방문했음' 을 표시 정점의 인접 정점 중에 방문하지 않은 곳을 선택하고 해당 정점이 방문하지 않았다면 이를 시작정점으로 설정 후 다시 DFS를 시작 (1번의 동작을 다시 실행) 정점에 더 이상 방문하지 않은 인접 정점이 없다면 이전으로 돌아가서 2번을 실행 이전 정점으로 돌아가도 더 이상 방문할 인접 정점이 없다면 그래프의 모든 정점을 방문 했으므로 탐색 종료. 깊이 우선 탐색 구현 - 이전 글의 vertex 구조체에서 없던 Visited를 추가한다. typedef struct ta..

그래프란? - 지점을 나타내는 정점(Vertex)의 모음과, 정점간을 잇는 간선(Edge)의 모음과의 결합. - 간선으로 연결 되어 있는 두 정점을 가리켜 '인접(Adjacent)'하다고 한다. Ex) A - C는 인접해있고, A - B는 인접해있지만, A - D는 인접해있지 않고, D - E는 인접해 있지 않다. - 한 정점에서 다른 정점으로 가는 동안 지나게 되는 간선의 집합을 '경로(Path)' 라고 한다. Ex) A부터 D까지 가기 위해 A - B - D로 가는 경로 또는 A - C - D로 가는 경로가 있다. - 어느 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 이를 '사이클(Cycle)'이라고 한다. Ex) 위의 그래프의 경우 (A - C - B - A), (B - C - D - B)..