탐색(DFS/BFS)

1)DFS

:Depth-First Search, 깊이우선탐색,그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

• 탐색 시작노드를 스택에 삽입하고 방문처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 위의 과정을 더이상 수행할수 없을때까지 방문한다.

<코드-파이썬>

#DFS 메서드의 정의
def dfs(graph,v, visited):
  #현재 노드를 방문 처리
  visited[v]=True
  print(v,end=' ')
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)
#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph=[
  [],
[2,3,8], #1번노드의 인접노드
[1,7],   #2번노드의 인접노드
[1,4,5], #3번노드의 인접노드
[3,5],   #4번노드의 인접노드 
[3,4],   #5번노드의 인접노드
[7],     #6번노드의 인접노드 
[2,6,8], #7번노드의 인접노드 
[1,7]    #8번노드의 인접노드
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*9
#정의된 Dfs 함수 호출
dfs(graph,1,visited)

[결과] : 1,2,7,6,8,3,4,5(노드방문순서)

방문노드
				6->인접노드 : 7(방문0)		8->인접노드 :1,7 (방문0)
			7	7	7	7	7
		2	2	2	2	2	2	2		3
	1	1	1	1	1	1	1	1	1	1
반복횟수	1	2	3	4	5	6	7	8	9	10

 

 

방문노드
		5
	4	4
	3	3
	1	1
반복횟수	11	12	13

2)BFS

:Breadth First Search, sjql우선탐색,  가까운 노드를 우선적으로 탐색하는 알고리즘

• 탐색 시작노드를 큐에 삽입하고 방문처리를 한다.
• 큐에서 노드를 꺼내 해당노드의 인접노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
• 위의 과정을 더이상 수행할수 없을때까지 방문한다.

<코드-파이썬>

from collections import deque

def bfs(graph,start,visited):
  queue = deque([start])
  visited[start]=True
#큐가 빌때까지 반복
  while queue:
    #큐에서 하나의 원소를 뽑아 출력
    v=queue.popleft()
    print(v,end=' ')
    #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
      #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
      if not visited[i]:
        queue.append(i)
        visited[i]=True
#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9
#정의된 BFS 함수 호출
bfs(graph,1,visited)

방문노드
						6	6	6
				5	5	5	5
				4	4	4
			7	7	7
		8	8	8
		3	3
		2
	1
반복횟수	1	2	3	4	5	6	7	8	9