dfs 관련하여 질문있습니다.

void dfs(int v) {
	nodePointer w;
	visited[v] = TRUE;
	printf("%5d", v);
	for (w = graph[v]; w; w = w->link)
		if (!visited[w->vertex])
			dfs(w->vertex);
}

최근 자료구조 복학하기전에 독학중입니다. 그래프부분에서 재귀를 이용한 그래프에서 dfs탐색을 해보았습니다. 이걸 스택을 사용하여 처리하는 dfs로 바꾸려고 하는데 모르는 부분을 구글링해보았는데 잘이해가 가지 않습니다. 대충 어떤식으로 바꾸어야할까요?

어떤 부분이 이해가 안가나요

push pop을 어떤 순서로 구현해야할지 모르겠어요.

안녕하세요.

재귀로 따지자면 함수를 호출하는게 push, 함수를 리턴하는게 pop입니다.

함수를 리턴하는 부분이 없는데 알려 주실수 있나요?

함수 끝나면 리턴하지요.

자 DFS가 뭡니까, 깊이 우선탐색이지요. 즉 쭉 한우물만 팠다가 더 갈곳이 없으면 한칸씩 뒤돌아오면서 갈곳이 있나 두리번두리번 하는겁니다.

일단 탐색을 할 수 있으면 그 노드를 push합니다. 하나의 노드에 여러 노드가 연결되어 있어도,
그냥 그중에 하나 골라서 push하면서 진행합니다.

그러다가 더이상 탐색을 진행하지 못하는 때가 옵니다. 현재 노드에서 연결된 노드가 없거든요.
그때 pop을 해서 하나씩 뒤로가면서 탐색을 할 수 있는지 확인하면 됩니다. 할수있으면 push하면서 진행하고, 할 수 없으면 pop해서 한칸 뒤로 가는거죠.

모든 노드가 다 탐색될때까지요.

1 Like

아하!! 이해했습니다. 감사합니다.