목록DFS (1)

hyeonzzz's Tech Blog

[이코테] 5. DFS/BFS - DFS

DFS DFS : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색이라고도 부른다. 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색한다 그래프 노드(정점)와 간선으로 표현된다 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 두 노드가 인접한다 = 두 노드가 간선으로 연결되어 있다 그래프를 표현하는 2가지 방식 인접 행렬 : 2차원 배열에 각 노드가 연결된 형태를 기록 INF = 99999999 # 무한의 비용 선언 #2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) [[0, 7, 5], [7, 0, 9..
Algorithm 2024. 2. 12. 19:19
이전 Prev 1 Next 다음