DFS/BFS

# 재귀 이용 def dfs(v): print(v, end=" ") # 현재 노드와 인접한 노드들 체크 for i in graph[v]: # 방문하지 않은 노드 일때만 dfs재귀 if visited[i] == 0: visited[i] = 1 # 노드 방문처리 dfs(i) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [0] * 9 visited[1] = 1 dfs(1) # 1 2 7 6 8 3 4 5

# 스택 이용 def dfs(v): stack = [v] # 현재 노드 스택에 추가 while stack: cur = stack.pop() if visited[cur] == 0: # 방문하지 않은 노드일 때 visited[cur] = 1 # 방문처리 print(cur, end=" ") # 인접노드들 뒤집어서 extend (작은노드들부터 먼저 방문하기 위해) stack.extend(graph[cur][::-1]) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [0] * 9 dfs(1) # 1 2 7 6 8 3 4 5

from collections import deque def bfs(start): q = deque([start]) # 시작노드 큐에 넣고 시작 visited[start] = 1 # 시작노드 방문처리 # bfs 메인로직 while q: v = q.popleft() # 큐에서 노드 하나 pop(실제 방문) print(v, end=" ") for node in graph[v]: # pop한 노드와 인접한 노드들 체크 if visited[node] == 0: # 인접노드가 미방문노드일 때만 visited[node] = 1 # 방문처리 q.append(node) # 큐에 추가 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [0] * 9 bfs(1) # 1 2 3 8 7 4 5 6

class myGraph: def __init__(self): self.graph = {} def addInfo(self, startV, endVs): self.graph[startV] = endVs def addEdge(self, startV, endV): self.graph[startV].append(endV) def addVertex(self, V): self.graph[V] = [] def bfs(self, startV): q = [startV] visited = [startV] while q: # 자료양이 커지면 deque.popleft()를 쓰는게 시간이 빠르다. nowV = q.pop(0) for nextV in self.graph[nowV]: if nextV not in visited: q.append(nextV) visited.append(nextV) return visited def dfs(self, startV): s = [startV] visited = [] while s: nowV = s.pop() if nowV not in visited: visited.append(nowV) s.extend(self.graph[nowV][::-1]) return visited def dfs_recursive(self, startV, visited=[]): visited.append(startV) for nextV in self.graph[startV]: if nextV not in visited: self.dfs_recursive(nextV, visited) return visited g = myGraph() g.addInfo( 'A', ['B', 'E', 'I']) g.addInfo( 'B', ['A', 'C']) g.addInfo( 'C', ['B', 'D']) g.addInfo( 'D', ['C']) g.addInfo( 'E', ['A', 'F', 'H']) g.addInfo( 'F', ['E', 'G']) g.addInfo( 'G', ['F']) g.addInfo( 'H', ['E']) g.addInfo( 'I', ['A', 'J']) g.addInfo( 'J', ['I']) print(g.bfs('A')) print(g.dfs('A')) print(g.dfs_recursive('A')) # ['A', 'B', 'E', 'I', 'C', 'F', 'H', 'J', 'D', 'G'] # ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] # ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']