그래프 탐색
- 목적 : 모든 정점을 1번씩 방문
- DFS : 깊이 우선 탐색, 최대한 깊숙히 많이 방문, 재귀 또는 stack 구현
- BFS : 너비 우선 탐색, 최대한 넓게 많이 방문, queue 구현, 모든 가중치가 1일 때 최단거리 구할 수 있음
One of the most popular areas of algorithm design within this space is the problem of checking for the existence or (shortest) path between two or more vertices in the graph.
Depth-First Search
def dfs():
stack = [start]
visitedList = []
blocked = False
while stack:
current = stack[len(stack) - 1]
if current not in visitedList:
visitedList.append(current)
adjacencyList[current].sort()
for neighbor in adjacencyList[current]:
if neighbor not in visitedList:
stack.append(neighbor)
visitedList.append(neighbor)
blocked = False
break
else:
blocked = True
continue
if blocked:
stack.pop()
return visitedVertex- 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 (stack에 push)
- 갈 수 없으면 이전 정점으로 돌아간다. (stack에서 pop)
- stack이 비면 탐색 종료
- 재귀 호출을 이용해서도 구현할 수 있다.
Breath-First Search
def bfs(graph, start):
vertexList, edgeList = graph
visitedList = [start]
queue = [start]
adjacencyList = [[] for vertex in vertexList]
for edge in edgeList:
adjacencyList[edge[0]].append(edge[1])
while queue:
current = queue.pop()
for neighbor in adjacencyList[current]:
if not neighbor in visitedList:
queue.insert(0,neighbor)
visitedList.append(neighbor)
return visitedList- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
- 큐에 넣을 때 방문했다고 체크
시간 복잡도
- 인접 행렬 : O(V^2)
- 인접 리스트 : O(V+E)
+
아 ㅠㅠ 이거 풀다가 머리가 나빠서 못푸나 싶어서 잠시 우울했다 ㅠㅠ
Resource
https://github.com/minsuk-heo/problemsolving/blob/master/graph/dfs.py http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/ https://www.youtube.com/watch?v=iaBEKo5sM7w