DFS (Depth First Search) - 깊이 우선 탐색
DFS (Depth First Search) - 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 - DFS는 스택 자료구조 (혹은 재귀함수)를 이용 원리 1. 탐색시작노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복 C++ 구현코드 #include #include using namespace std; int number = 7; //노드 개수 int c[8]; //방문 처리를 위한 배열 vector a[8]; //총 7개의 노드가 각각 인접한 노드를 가질 수 있도록 만들어줌 void dfs(int x) { if (c[x]) //이미 방문했다면..
PS/알고리즘
2023. 8. 18. 16:20