[자료구조] DFS구현

C 구현

 

DFS를 재귀로 구현해보자

물론 이는 C에서이다.

C는 파이썬과 같이 딕셔너리가 없기때문에 재귀를 이용하기 위해서는

matrix로 구현하는게 가장 쉽다

역시 쓰레기언어

---

[ DrawGraph ]

void DrawGraph(int fromV, int toV) {
	matrix[fromV][toV] = 1;
}

 

---

[ DFS ]

void DFS(int num) {
	printf("%c\n", num+65);
	for (int i = 0; i < SIZE; i++) {
		if (visitInfo[i] == 0 && matrix[num][i] == 1) {
			visitInfo[i] = 1;
			DFS(i);
		}
	}
}

 

---

[ main ]

enum { A,B,C,D,E,F,G,H,I,J };

int visitInfo[SIZE] = { 0, };
int matrix[SIZE][SIZE] = { 0, };

void DrawGraph(int fromV, int toV);
void DFS(int num);

int main() {
	DrawGraph(A, B);
	DrawGraph(A, C);
	DrawGraph(B, D);
	DrawGraph(B, E);
	DrawGraph(C, F);
	DrawGraph(C, G);
	DrawGraph(D, H);
	DrawGraph(F, I);
	DrawGraph(G, J);

	DFS(A);
}

 

---

---

Python 구현

 

파이썬은 딕셔너리를 제공하기 때문에 
이를 통해 key값에 fromV노드를 넣고
value값으로 toV노드들을 리스트형으로 저장하면 된다.
물론 matrix로도 할 수 있다.
 

---

[ stack_DFS ]

def stack_DFS(graph,root) :
    visited=list() #방문정보 담을 배열
    stack = [root] #방문추적

    while stack :
        root = stack.pop()
        
        # 첫방문이면 
        if root not in visited :
            visited.append(root)
            stack.extend(reversed(graph[root]))
        # 방문이미 했으면 그냥 pop만
        else:
            continue

    return visited

재귀를 사용하지 않는대신 while문을 사용한 코드이다.
따라서 방문경로를 추적하기 위해 stack이 필요하다
 

stack.extend(reversed(graph[node]))

 
이 코드가 가장 중요하다.
 
만약 방문하지 않은 node라면 visitInfo에 저장하고
해당 node의 value값들을 stack에 거꾸로 집어넣어
하나씩 뽑아가며 DFS를 진행한다.
 
여기서 거꾸로 집어넣는 이유는 DFS이기 때문이다!
 
이때 주의해야할 것이 stack.extend(reversed(graph[node]))를 진행한다면
이미 visit한 노드들도 스택에 들어갈 수 있다는 얘기다.
 
즉 스택에 한 정점이 여러개 쌓여 들어갈 수 있다는 말인데 
이는 else : continue 문을 통해 자동으로 pop되어 skip할 수 있게 하였다.
 
아래는 stack의 변화과정을 나타낸 그림이다.
그냥 pop만 이라는 뜻은 이미 visited된 정점으로 stack에서 빼주기만 하면 되기 때문이다.
파란색 정점들은 어떤 정점을 빼고 새로 스택에 추가된 정점들이다.
 

 
참고로 append와 extend 함수의 차이점은 다음과 같다.
stack.append(x) : 리스트 끝에 변수 x 자체를 그대로 넣는다.
stack.extend(x) : 리스트 끝에 가장 바깥쪽 iterator의 모든 항목을 넣는다.
 
만약 여기서 stack.append(reversed(graph[root]))를 했으면 
[ 'A' , [ 'C' , 'B' ] ] 이런 식으로 스택에 들어가지만
우리는 [ 'A', 'C', 'B' ] 이걸 의도하는 것이므로 extend 함수를 써야한다.
 

---

[ recursive_DFS ]

 

def recursive_DFS(graph,root,visited) :
    # 첫방문이면 무조건 탐색
    if root not in visited :
        visited.append(root)
        for node in graph[root] :
            recursive_DFS(graph,node,visited)

    # 방문한 적있으면 아무것도 안함
    return visited

이건 재귀를 사용한 코드이다.
재귀는 stack이 필요없다.
왜냐하면 재귀호출이 stack처럼 쌓이면서 호출되는 과정이기 때문이다.
 
일반적인 재귀함수를 떠올리면 된다.

---

[ main ]

 

graph = { 'A':['B','C'],
          'B':['A','D','E'],
          'C':['A','F','G'],
          'D':['B','H','I'],
          'E':['B','J'],
          'F':['C'],
          'G':['C'],
          'H':['D'],
          'I':['D'],
          'J':['E']
        }

print(stack_DFS(graph,'A'))
print(recursive_DFS(graph,'A',[]))
print(stack_DFS(graph,'C'))
print(recursive_DFS(graph,'C',[]))

 

---