그래프

BFS이란? BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄 DFS와 BFS의 차이점 DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다. 이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. → 스택 BFS 는 현재 인접한 노드 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. → 큐 구현 (Python) 1. 루트 노드를 큐에 넣는다. 2. 현재 큐의 노드를 빼서 visited 에..

DFS란? DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수를 이용함 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 위 과정을 반복한다. 구현 (Python) from dfs_bfs.prac import dfs_recursive, dfs_stack # 테스트 코드 assert dfs_recursive(1, []) == [1, 2, 5, 6, 7, 3, 4] # dfs로 방문한 경우 assert dfs_stack(1) == [1, 4, 3,..

그래프란? 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조 자료구조는 크게 비선형구조, 선형구조로 구분된다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있다. 그래프에서 사용되는 용어 노드(Node): 연결 관계를 가진 각 데이터를 의미 . 정점(Vertex)이라고도 함. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 그래프의 종류 그래프는 유방향 그래프와 무방향 그래프 두가지가 있다. 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간..