DFS (Depth-First Search) BFS (Breadth-First Search) 개념

이 포스트는 SwiftAlgorithmClub DFS, BFS  내용을 정리한 글입니다.

 

DSF (Depth-First Search)

DFS 코드에서 확인할 수 있습니다.

깊이 우선 검색 (DFS)은 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기위한 알고리즘입니다.

소스 노드에서 시작하여 가장 깊은 단계까지 추적합니다.

깊이 우선 검색은 유 방향 그래프와 무향 그래프 모두에 사용할 수 있습니다.

 

위에 탐색하는 과정을 그림으로 표현하면 아래와 같습니다. 

 

 

A -> B -> D -> B 로 다시 돌아가면서 이미 방문한 적이 있다면 다른 간선 E 로 탐색을 합니다.

 

DFS 코드에서 확인할 수 있습니다.

 

let graph = Graph()

let node0 = graph.addNode("0")
let node1 = graph.addNode("1")
let node2 = graph.addNode("2")
let node3 = graph.addNode("3")

graph.addEdge(node0, neighbor: node1)
graph.addEdge(node0, neighbor: node2)
graph.addEdge(node1, neighbor: node2)
graph.addEdge(node2, neighbor: node0)
graph.addEdge(node2, neighbor: node3)
graph.addEdge(node3, neighbor: node3)

let nodesExplored = depthFirstSearch(graph, source: node2)
print(nodesExplored)

 

func depthFirstSearch(_ graph: Graph, source: Node) -> [String] {
	현재 노드를 방문한 것으로 표시합니다
    for 시작 노드에서 인접 노드가 있을 때 까지 반복합니다. {
    	if  노드를 방문한적이 없다면 {
        	인접 노드는 재귀로 탐색을 합니다. depthFirstSearch()
        }
    }
    
}

 

 

BFS (Breadth-First Search)

BFS 코드에서 확인할 수 있습니다.

너비 우선 검색 (BFS)은 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기위한 알고리즘입니다.

소스 노드에서 시작하여 다음 인접 이웃으로 이동하기 전에 먼저 인접 이웃 노드를 탐색합니다.

너비 우선 검색도 마찬가지고 유, 무향 그래프 모두에서 사용할 수 있습니다.

 

 

위에 탐색하는 과정을 그림으로 표현하면 아래와 같습니다. 

인접 노드를 저장하기 위해서 Queue 를 사용합니다. 회색으로 표시되는 영역이 Queue에 Push 되는 인접 노드입니다.

 

let graph = Graph()

let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")

graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeD)
graph.addEdge(nodeB, neighbor: nodeE)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeG)
graph.addEdge(nodeE, neighbor: nodeH)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeG)

let nodesExplored = breadthFirstSearch(graph, source: nodeA)
print(nodesExplored)

 

func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] { 
	최초 시작 위치를 Queue 에 담습니다.
	최초 노드를 방문한 것으로 표시합니다.
    
	while Queue 가 비어있지 않다면? let node = Queue 에서 Node 꺼냅니다. {
    	let neighbor = node 의 첫 인접노드 하나를 가져옵니다.
		
        if neighbor를 방문한 적이 없다면 {
         	Queue 에 neighbor를 추가합니다.
            neighbor를 방문했다고 표시합니다.
        }
        
    }
}

 

 

 

 

BFS 코드에서 확인할 수 있습니다.

 

참조: 

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Breadth-First%20Search

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Depth-First%20Search