Developer Cafe

그래프 순회 - 하나의 정점에서 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색 이라고 한다. - 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색이 있다. 1. 깊이 우선 탐색 깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 함으로써 모든 정점을 방문하는 쉰회 방법이다. 스택을 사용한다. (1) 시작 정점 v를 결정하여 방문한다. (2) 정점 v에 인접한 정점 중에서 ⓐ 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 w를 방문한다. 그리고 w를 v로 설정하고 (2) 반복. ⓑ 방문하지 않은 ..

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다. 원 하나를 노드로 그 노드는 정점이라 부르고, 정점간 관계인 선은 간선이라 부른다. 또한 그래프는 트위터 팔로우 기능처럼 화살표로 표현된 것을 방향 그래프, 페이스북처럼 상호작용하는 그래프는 무방향 그래프라한다. 위 그림에서 앨리스는 밥과 직접 커넥션이 있으나 신시아와 직접 커넥션이 없다. 비직접적인 커넥션을 포함해 앨리스 전체 네트워크를 찾으려면 두가지 방법이 있다. 1. 너비 우선 탐색 2. 깊이 우선 탐색 여기선 너비 우선 탐색만 포스팅하고 깊이 우선 탐색은 차후 업데이트하거나 따로 비교포스팅하겠다. 너비 우선 탐색 1. 현재 정점과 인접한 각 정점을 방문한다. 이전에 방문한 적 없는 정점이면 방문했다 표시하고 큐에 추..