전체 글
-
BFS (Breadth First Search) : 너비 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:12
BFS, 너비 우선 탐색이란, 그래프 상에 존재하는 정점을 방문할 때마다 그 다음으로 주변의 인접한 정점들을 우선적으로 탐색해나가는 탐색 방법을 말한다. 반복문과 큐를 이용하여 구현할 수 있다. 수도코드 bfs(int i){ queue q; q.push(i); visited[i] = true; while(!q.empty()){ int v = q.pop(); for(i in adjacent vertices of v){ if(!visited[i]){ q.push(i); visited[i] = true; } } } } 노드를 방문할 때마다 방문하지 않은 주변 노드들이 큐에 들어간다. 큐에 한번 들어가는 순간 방문이 예정되어 있으므로 방문 표시를 한다. (그래야 중복 방문이 제대로 방지된다.) 큐에 들어간 순서..
-
DFS (Depth First Search) : 깊이 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:01
DFS, 깊이 우선 탐색이란, 그래프 상에 존재하는 정점에서 인접한 정점 중에 방문하지 않은 정점이 없을 때까지 계속 인접한 다른 임의의 정점으로 이동하며 탐색한다. 인접한 정점 중에 방문하지 않은 정점이 없으면 이전 정점으로 이동한 뒤 다른 정점으로 이동하는 과정을 반복한다. 구현 방법은 재귀함수를 이용한 것과, 반복문과 스택을 이용한 것으로 2가지가 있다. 수도코드 - 재귀함수로 구현 dfs(int v){ visited[v] = true; for(u in adjacent vertices of v){ if(!visited[u]){ dfs(u); } } } 인접한 노드를 하나씩 연이어서 계속 방문한다. 그러다가 방문할 노드가 없으면 이전 노드의 인접 노드를 탐색하게 된다. 수도코드 - 반복문과 스택으로 ..
-
그래프Computer Science/자료구조&알고리즘 2021. 2. 13. 21:41
그래프 : 정점(Vertex)과 간선(Edge)의 집합. 트리는 사이클이 허용되지 않는 일종의 그래프이다. Undirected Graph : 간선이 방향을 갖지 않는 그래프. 무향 그래프. Directed Graph (Digraph) : 간선이 방향을 갖는 그래프. 유향 그래프. Degree (차수) : 각 정점에 연결된 간선의 개수 Outdegree : 유향 그래프에서 정점으로부터 밖으로 나가는 간선의 개수 Indegree : 유향 그래프에서 정점으로 들어가는 간선의 개수 가중치 그래프(Weight Graph) : 간선에 가중치 정보를 둔 그래프. 부분 그래프(Sub Graph) : 어떤 그래프의 부분집합에 해당하는 그래프 (해당 그래프의 정점과 간선들 중 일부만 가지고 있는 그래프) 그래프의 구현 방..