23. 그래프(Graph) - 깊이 우선 검색(depth first search)

1. 재귀

방문한 노드는 마크합니다.
따라서 마크용 셋을 미리 만들어야 합니다. 

 

마크용으론 리스트보다 set이 좋은 경우가 많은데
set은 해시를 이용해서 검색 시 속도가 빠르기 때문입니다. 
https://wiki.python.org/moin/TimeComplexity

 

재귀적이지만 비교적 단순한 알고리듬입니다. 
스택으로도 만들 수 있습니다. 

 

for 문 내부에 재귀가 있습니다. 
그렇기 때문에 하나의 노드에서 재귀로 깊이 우선 검색을 먼저 하게 되고, 
for 문으로 다음 노드로 넘어가서 또 깊이 우선 검색을 하게 되는 반복 구조입니다. 

class Graph:
    def __init__(self):
        self.graph = dict() # {}
        self.marked = set()

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        for node in self.graph:
            print(node, '->', self.graph[node])

    def init_marked(self):
        self.marked.clear()

    def dfs(self, v):
        self.marked.add(v)
        print('Visited vertex:', v)
        for w in self.graph[v]:
            if w not in self.marked:
                self.dfs(w)

g = Graph()
g.add(0, 1)
g.add(0, 3)
g.add(1, 2)
g.add(3, 4)
g.add(1, 3)

g.show()

print('--')
g.dfs(0)
g.init_marked()

print('--')
g.dfs(1)

0 -> {1, 3}
1 -> {0, 2, 3}
3 -> {0, 1, 4}
2 -> {1}
4 -> {3}
--
Visited vertex: 0
Visited vertex: 1
Visited vertex: 2
Visited vertex: 3
Visited vertex: 4
--
Visited vertex: 1
Visited vertex: 0
Visited vertex: 3
Visited vertex: 4
Visited vertex: 2

 

2. 스택

스택으로 코딩해 봅니다. 

class Graph:

    def __init__(self):
        self.graph = {}

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        for node in self.graph:
            print(node, '->', self.graph[node])

    def dfs(self, start):
        stack = [start]
        marked = {start}
        while stack:
            v = stack.pop()
            print('Visited vertex:', v)
            for w in self.graph[v]:
                if w not in marked:
                    stack.append(w)
                    marked.add(w)

재귀가 아닌 스택으로 작성되었기 때문에 marked 리스트를 메서드 내부에 넣을 수 있습니다. 
marked 리스트를 메서드 내부에 넣으니 self. 도 안 써도 되고, marked를 별도로 clear 하는 부분도 필요 없어졌습니다.
깔끔해졌네요. ^^

g = Graph()
g.add(0, 1)
g.add(0, 3)
g.add(1, 2)
g.add(3, 4)
g.add(1, 3)

g.show()

print('--')
g.dfs(0)

print('--')
g.dfs(1)

0 -> {1, 3}
1 -> {0, 2, 3}
3 -> {0, 1, 4}
2 -> {1}
4 -> {3}
--
Visited vertex: 0
Visited vertex: 3
Visited vertex: 4
Visited vertex: 1
Visited vertex: 2
--
Visited vertex: 1
Visited vertex: 3
Visited vertex: 4
Visited vertex: 2
Visited vertex: 0

두 예의 결괏값은 다릅니다.
이 차이는 오른쪽(?) 왼쪽(?) 노드 중 뭘 먼저 탐색했냐의 차이일 뿐이고 둘 다 정답이 맞습니다. 

 

* 스택 편에서 말씀드렸지만...  list를 스택으로 사용하는 것은 비효율적입니다.

 

3. for 문 제거

class Graph:

    def __init__(self):
        self.graph = {}

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        for node in self.graph:
            print(node, '->', self.graph[node])

    def dfs(self, start):
        stack = [start]
        marked = set()  # marked를 비운 상태로 시작합니다.
        while stack:
            v = stack.pop()
            if v not in marked:
                print('Visited vertex:', v)
                marked.add(v)
                stack.extend(self.graph[v].difference(marked))


g = Graph()
g.add(0, 1)
g.add(0, 3)
g.add(1, 2)
g.add(3, 4)
g.add(1, 3)

g.show()

print('--')
g.dfs(0)

print('--')
g.dfs(1)

파이썬의 반복문은 빠르지 않기 때문에..
이렇게 작성하면 조금 더 빠를 수 있습니다. 

 

파이썬은 C언어로 작성되어 있고, 
C언어로 작성된 부분들을 이용하면
속도 향상에 도움이 됩니다. 

0 -> {1, 3}
1 -> {0, 2, 3}
3 -> {0, 1, 4}
2 -> {1}
4 -> {3}
--
Visited vertex: 0
Visited vertex: 3
Visited vertex: 4
Visited vertex: 1
Visited vertex: 2
--
Visited vertex: 1
Visited vertex: 3
Visited vertex: 4
Visited vertex: 0
Visited vertex: 2