[Algorithm] DFS/BFS

❓DFS와 BFS

 

- 주어진 그래프에서 모든 노드를 방문하는 알고리즘

 

 

❓DFS

 

- Depth First Search (깊이 우선 탐색)

- 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문

 

def dfs(x):
	visited[x]=True
    for i in graph[x]:
    	if not visited[i]:
        	dfs(i)

 

 

❓BFS

 

- Breadth First Search (너비 우선 탐색)

- 임의의 정점에서 시작하여 이웃하는 모든 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 방문

 

def bfs(x):
	queue=[]
    visited[x]=True
    queue.append(x)
    while len(queue)!=0:
    	v=queue.pop(0)
        for i in graph(v):
        	if not visited[i]:
            	visited[i]=True
                queue.append(i)