void DFS(void){
int i, x, y;
bool chk[1001] = {};
s.push(S);
while(!s.empty()){
x = s.top(); s.pop();
if(!chk[x]){
printf("%d ", x); chk[x] = 1;
for(i=graph[x].size()-1;i>=0;i--){
y = graph[x][i];
if(!chk[y]){
s.push(y);
}
}
}
}
printf("\n");
}
제가 말한건 3이라는 노드가 출력 되기 전에는 스텍에 들어가지 않는 걸 말한건데,
예를 들어 1 2 3 4 / 총 4개의 노드가 있고 6개의 간선? 으로 모두가 연결 되어 있다면
DFS 의 출력 순서는 1 2 3 4가 될것입니다.
1번 부터 시작한다고 가정 첫번째엔
스텍 s : 1
이고, 두번째 스텍엔
스텍 s :2 3 4
세번째 스텍엔
3 4 3 4
네번째 스텍엔
4 4 3 4
가 들어 갈 텐데
방문 되지 않은 노드는 계속 입력이 되어야 합니다.
이런 노드의 방문 없이 코드를 짤 수 없을까요?
(스텍안에 한 노드의 id가 한번씩만 입력 되게 dfs를 설계할 수는 없나요?)
1. visited 만들면 되나요? 아니요
2. 나머지는 밑에 댓글에 설명했으니 그대로 하세요
void DFS(void) { int start[1001] = { 0, }; int i, x, y; bool chk[1001] = {}; s.push(S); while (!s.empty()) { x = s.top(); if (!chk[x]) printf("%d ", x); chk[x] = 1; for (i = start[x]; i < graph[x].size(); i++) { y = graph[x][i]; if (!chk[y]) { s.push(y); start[x] = i + 1; break; } } if (i == graph[x].size()) s.pop(); } printf("n");}
가독성무엇; 이렇게 하면 되지 않을까
배열 하나 더만들어서 반복문 잠시 중단할 수 있게 마들고 반복문 끝났을때 pop하게 만듦
아 내가 착각한듯 ㅈㅅ 개념을 잘못이해함 미안