목록컴퓨터과학/자료구조&알고리즘 (4)

Blog For Me

[자료구조와 알고리즘] 그래프 순회 - 너비 우선 탐색 (bfs)

bfs 탐색 시작 정점 v를 방문한다. v에 인접한 모든 정점들을 방문한다. 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문한다. 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출의 구조를 갖는 Queue를 사용한다. bfs 탐색 예시 bfs 소스코드 class Graph{ private ArrayList edges; private boolean[] visited; public Graph(int size) { this.edges = new ArrayList(); this.visited = new boolean[size]; for(int i=0;i
컴퓨터과학/자료구조&알고리즘 2022. 1. 4. 22:16
[자료구조와 알고리즘] 그래프 순회 - 깊이 우선 탐색 (dfs)

그래프 순회 (graph traversal), 그래프 탐색 (graph search) 하나의 정점에서 시작하여 그래프에 있는 정점을 한번씩 방문하여 처리하는 연산 그래프 탐색 방법에는 깊이 우선 탐색(depth first search: DFS), 너비 우선 탐색(breadth first search: BFS) 가 있다. 깊이 우선 탐색 (dfs 탐색) 시작 정점 v를 결정하여 방문 정점 v에 인접한 정점 중에서 (1) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 2번의 과정을 반복 (2) 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 스택을 pop하여 받은 가장 마지막 장문 정점을 v로 하여 다시 2번 과정을 반복 스택이 공..
컴퓨터과학/자료구조&알고리즘 2021. 12. 29. 23:43
[자료구조와 알고리즘] 그래프 표현방법

인접행렬 (Adjacency Matrix) G=(V, E)는 정점의 수가 n인 그래프 인접행렬: n x n인 2차원 배열 행, 열 => 그래프의 정점 간선 (Vi, Vj) ∈ E(G) => a[i][j] = 1 (인접한 경우) 간선 (Vi, Vj) ∉ E(G) => a[i][j] = 0 (인접하지 않은 경우) 무방향 그래프 : 어떤 정점 i의 차수는 그 행 또는 열의 합 방향 그래프 : 행의 합은 진출차수, 열의 합은 진입차수 정점 0의 인접 정점 : 1, 2 정점 1의 인접 정점 : 0, 3 정점 2의 인접 정점 : 0. 3 정점 3의 인접 정점 : 1, 2 인접행렬 소스코드 import java.io.BufferedReader; import java.io.IOException; import java...
컴퓨터과학/자료구조&알고리즘 2021. 12. 16. 23:56
[자료구조와 알고리즘] 그래프(Graph) 개념

그래프 (Graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多 의 관계를 지니는 원소들을 표현하기 위한 자료구조 그래프 G 객체를 나타내는 정점 Vertex와 객체를 연결하는 간선 edge의 집합 G = (V, E) V : 그래프에 있는 정점들의 집합 E : 정점을 연결하는 간선들의 집합 그래프의 예 : 버스나 지하철 노선도, 인스타그램의 following/follower 관계 지도 그래프의 종류 1. 무방향 그래프 (undirected graph) 두 정점을 연결하는 간선의 방향이 없는 그래프 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미 간선을 나타내는 정점의 쌍에는 순서가 존재하지 않는다. V(G) = {A, B,..
컴퓨터과학/자료구조&알고리즘 2021. 12. 16. 20:18
Prev 1 Next