그래프 탐색
그래프는 정점과 간선으로 이루어진 자료구조의 일종으로, 정점은 각 출발점과 도착점을 의미하고 간선은 그 정점간 연결된 관계를 나타낸다.
그래프 탐색의 목적은 모든 정점을 한번씩 방문하는 것이고, 어떻게 방문할건지에 따라 DFS와 BFS로 나뉜다.
DFS (Depth First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로, 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
깊게(deep) 탐색하는 방식으로 모든 노드를 방문하고자 하는 경우에 이 방법을 선택하며, 너비 우선 탐색(BFS)보다 좀 더 간단하지만 검색 속도는 느리며 어떤 노드를 방문했었는지 여부를 검사하지 않으면 무한루프에 빠질 수 있다.
#리스트 안에 모든 vertex를 포함시킨다.
vertexList = ['0', '1', '2', '3', '4', '5', '6']
#undirect
edgeList = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4)]
#vertexList와 edgeList를 사용해서 인접 리스트를 생성한다.
adjacencyList=[[] for vertex in vertexList]
for edge in edgeList:
adjacencyList[edge[0]].append(edge[1])
->
[[], [], [], [], [], [], []]
(0, 1) 0 1
[[1], [], [], [], [], [], []]
(0, 2) 0 2
[[1, 2], [], [], [], [], [], []]
(1, 0) 1 0
[[1, 2], [0], [], [], [], [], []]
(1, 3) 1 3
[[1, 2], [0, 3], [], [], [], [], []]
(2, 0) 2 0
[[1, 2], [0, 3], [0], [], [], [], []]
(2, 4) 2 4
[[1, 2], [0, 3], [0, 4], [], [], [], []]
(2, 5) 2 5
[[1, 2], [0, 3], [0, 4, 5], [], [], [], []]
(3, 1) 3 1
[[1, 2], [0, 3], [0, 4, 5], [1], [], [], []]
(4, 2) 4 2
[[1, 2], [0, 3], [0, 4, 5], [1], [2], [], []]
(4, 6) 4 6
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [], []]
(5, 2) 5 2
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], []]
(6, 4) 6 4
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
adjacencyList = [
[1,2], #vertex 0
[0,3], #vertex 1
[0,4,5], #vertex 2
[1], #vertex 3
[2,6], #vertex 4
[2], #vertex 5
[4] #vertex 6
]
#DFS 실행
stack = [0]
visitedVertex = []
while stack:
current = stack.pop()
for neighbor in adjacencyList[current]:
if not neighbor in visitedVertex:
stack.append(neighbor)
visitedVertex.append(current)
return visitedVertex
-> [0, 2, 5, 4, 6, 1, 3]BFS (Breadth First Search)
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 넓게(wide) 탐색한다.
방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 Queue(FIFO)를 사용하며, 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
#리스트 안에 모든 vertex를 포함시킨다.
vertexList = ['0', '1', '2', '3', '4', '5', '6']
#undirect
edgeList = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4)]
#vertexList와 edgeList를 사용해서 인접 리스트를 생성한다.
adjacencyList=[[] for vertex in vertexList]
for edge in edgeList:
adjacencyList[edge[0]].append(edge[1])
adjacencyList = [
[1,2], #vertex 0
[0,3], #vertex 1
[0,4,5], #vertex 2
[1], #vertex 3
[2,6], #vertex 4
[2], #vertex 5
[4] #vertex 6
]
#BFS 실행
queue = [0]
visitedList = []
while queue:
current = queue.pop()
for neighbor in adjacencyList[current]:
if not neighbor in visitedList:
queue.insert(0, neighbor)
visitedList.append(current)
return visitedList
-> [0, 1, 2, 3, 4, 5, 6][REF]
https://namu.wiki/w/BFS
https://namu.wiki/w/DFS
https://www.youtube.com/watch?v=BLc3wzvycH8
https://www.youtube.com/watch?v=0v3293kcjTI
https://www.youtube.com/watch?v=zaBhtODEL0w&t=229s
