별의 공부 블로그 🧑🏻‍💻

🗒️ 깊이 우선 탐색 (2)

728x90
  1. 2022.06.04 [Python] 그래프(Graph)

    그래프(Graph) 그래프(Graph)의 기본 그래프의 개념 그래프(Graph) : 여러 노드가 서로 연결된 자료구조 루트에서 하위 노드 방향으로만 이어지는 트리와 달리, 여러 노드가 연결되어 있을 수 있다. 트리도 그래프의 일종이지만, 트리와 그래프를 구현하는 코드 등이 확연히 다르기 때문에 이 둘은 별도로 생각하는 편이 낫다. 그래프의 종류 그래프는 정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나눈다. 간선에 가중치(Weight)를 부여하여 가중치 그래프도 만들 수 있다. 무방향 그래프 트리의 노드(Node)에 해당하는 용어가 그래프에서는 정점(Vertex)이다. 정점을 연결하는 선은 간선(Edge)이므로 그래프는 정점과 간선의 집합으로 볼 수 있다. 그래프에서 정점은 V..

  2. 2021.06.30 깊이 우선 탐색(DFS, Depth-First Search)

    깊이 우선 탐색(DFS, Depth-First Search) 너비 우선 탐색(BFS, Breadth-First Search) 시작 장점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식 방문하지 않은 정점을 저장하기 위해 큐(Queue) 를 사용함. 선입선출(FIFO) 자료구조 큐에 있는 정점들은 큐에 들어갔던 순서대로 제거됨. 이러한 큐의 속성을 이용하여 시작 정점에 가까이 있는 정점들을 먼저 처리할 수 있음. 시간 복잡도 : O(V + E) 깊이 우선 탐색(DFS, Depth-First Search) 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식 더 방문할 정점이 없어지면, 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복함. 이러한 그래프 탐색 방..

728x90
📖 Contents 📖

티스토리툴바