그래프6 [Javascript] 그래프 이번에 구현할 자료구조는 그래프입니다. 그래프는 트리와 비슷하면서도 다른 성질의 자료구조 입니다. 2021.10.04 - [Programming/자료구조] - 그래프 Graph 그래프 Graph 리스트와 스택, 큐는 1:1 구조의 자료구조, 트리는 1:다의 자료구조였습니다. 그렇다면 다:다 관계를 가진 자료구조도 존재할 것 같다는 생각이 듭니다. 그래프는 이처럼 다:다의 관계를 가진 자 bamtory29.tistory.com 2021.10.05 - [Programming/자료구조] - 그래프 구현2 - 인접 리스트로 그래프 구현하기 그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프.. 2021. 11. 22. 그래프 탐색 - 너비 우선 탐색 BFS 이번에는 그래프 탐색의 다른 방식인 BFS에 대해서 소개해드리겠습니다. 1. 너비 우선 탐색 Breadth First Search, BFS 지난번에 본 깊이 우선 탐색(DFS)는 한 정점에서 시작해서 갈 수 있는 정점까지 방문한 후에 방문하지 않은 인접 정점이 있는 정점으로 돌아와서 진행하는 방식이었습니다. 이번에 배울 너비 우선 탐색은 정점에 인접한 정점들을 모두 한 번씩 방문하고 나서 방문했던 정점들의 인접한 정점들을 다시 한 번씩 방문하는 방식입니다. 또한 정점들마다 너비 우선 탐색을 수행하기 위해서 큐를 이용합니다. 이점도 DFS와 차이점을 보이고있습니다. DFS와 마찬가지로 배열과 큐를 이용하는데 배열에는 방문 정보를 담고 큐에는 방문 기록을 남기기 위해 사용합니다. A에서 시작하도록 하겠습니다.. 2021. 10. 9. 그래프 탐색 - 깊이 우선 탐색 DFS 그래프의 탐색 혹은 그래프의 순회라고 불리우는 개념은 그래프의 모든 정점을 반드시 한 번은 방문하는 것을 말합니다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 종류가 있는 그중에서 깊이 우선 탐색 부터 알아보겠습니다. 1. 깊이 우선 탐색 Depth First Search, DFS 깊이 우선 탐색은 한 정점에서 시작하여 한 방향으로 진행해 갈 수 있는 정점까지 최대한으로 탐색합니다. 그러다가 더이상 진행할 수 없다면 가장 최근에 만난 갈림길이 있는 정점으로 돌아가서 다른 방향의 간선으로 진행할 수 있는지 탐색하는 방식입니다. 깊이 우선 탐색에서는 탐색한 경로의 정보를 담기 위해서 스택을 이용하고, 정점에 대해 방문한 정보를 기록하기 위해서배열을 이용합니다. 말로했을 때.. 2021. 10. 8. 그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프를 구현해보도록 하겠습니다. 1. 인접 리스트 인접 리스트 방식은 한 정점에 대해서 인접한 리스트를 연결 리스트로 연결한 것입니다. 다음과 같은 그래프를 인접 리스트로 표현해보면 다음과 같습니다. 그림을 보고나면 대충 감이 잡히실겁니다. 각 정점에 대해서 노드는 간선의 갯수만큼 연결되어있습니다. 맨 처음의 A, B, C, D 노드를 헤드 포인터라고 하며, 이 헤드 포인터는 그래프의 정점의 갯수만큼을 필요로합니다. 즉, 무방향 그래프의 노드의 수 만큼의 연결 리스트가 만들어지고 각 연결 리스트는 정점이 가진 간선의 갯수(차수, degree)만큼의 길이를 가지게 됩니다. 만약 방향 그.. 2021. 10. 5. 그래프 구현 1 - 인접 행렬로 그래프 구현하기 모든 자료구조가 그래왔듯이 그래프를 구현하는 방식에는 순차 자료구조를 이용하는 방식과 연결 자료구조를 이용하는 방식 두가지가 있습니다. 그래프에서도 마찬가지이지만 이름을 조금 다르게 부릅니다. 순차 자료구조를 이용해서 구현하는 것을 인접 행렬 기반 그래프, 연결 자료구조를 이용해서 구현하는 것을 인접 리스트 기반 그래프 라고합니다. 오늘은 첫 번째 순차 자료구조를 이용한 방식인 인접 행렬을 이용한 그래프를 구현해보겠습니다. 1. 인접 행렬 Adjacent Matrix 인접 행렬은 그래프에서 정점이 어떤 간선으로 연결되었는지를 나타내는 행렬입니다. 정점 n개의 그래프에 대해서 nXn행렬을 이용합니다. 이때 정점끼리 연결되어 있다면 행렬의 값을 1로, 연결되어있지 않다면 행렬의 값을 0으로 이용합니다. 예시.. 2021. 10. 4. 그래프 Graph 리스트와 스택, 큐는 1:1 구조의 자료구조, 트리는 1:다의 자료구조였습니다. 그렇다면 다:다 관계를 가진 자료구조도 존재할 것 같다는 생각이 듭니다. 그래프는 이처럼 다:다의 관계를 가진 자료구조 입니다. 1. 그래프 지하철 노선도 처럼 한 역에서 찍어서 다른 역에 도달하는 방법까지는 수많은 방법이 있습니다. 그리고 한 역은 하나의 역만 연결될 수도 있고 수많은 역과 연결되어 있을 수도 있습니다. 이 지하철 노선도가 그래프를 가장 잘 나타내주고 있습니다. 그래프는 다:다의 관계를 가진 정점과 간선으로 이루어진 자료구조입니다. 정점은 객체(Vertex)를 나타내고 간선(Edge)은 객체끼리의 연결을 의미합니다. 이때 그래프 G는 G=(V, E)와 같은 형태로 정의합니다. 간선 V는 객체i와 2. 그래프.. 2021. 10. 4. 이전 1 다음 300x250
