DFS(Depth First Search) / DFS to find cycle in graph

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

     

vertexList = ['0', '1', '2', '3', '4', '5', '6'] 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)] 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

          

- 인접 리스트 까지 만들면 DFS를 실행 시킬 수 있다.

Stack [0] while stack: current = stack.pop() for neighbor in adjacencyList[current]: if not neighbor in visitedVertex: stack.append(neighbor) visitedVertex.append(current) return visitedVertex

- 깊이 우선 탐색이 언제 쓰일까?

  - 게임 같은 곳에서 많이 쓰인다. (e.g.)체스의 경우의 수를 따질때)

  - 인터뷰에서 깊이 우선 탐색이 응용문제로 많이 쓰인다. 

    그래프가 주어지고 cycle이 있는지 없는지 확인해봐!! 이때 DFS를 사용하면 좋다!! 

== DFS to find cycle in graph ==

Git에 더 상세히 기록함!! 

source-code : The-G

---

reference :  상상개발자