728x90 자료구조7 [graph] 너비 우선 탐색(BFS, Breadth First Search) 너비 우선 탐색(BFS, Breadth First Search) 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법 인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출(First-IN First-Out) 구조인 큐(Queue) 사용 BFS 수행순서 큐가 공백이 될 때까지 빨간 상자 부분을 반복한다. BFS 과정 표현 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Queue가 비었으므로 탐색 종료 결과 : 1 → 2 → 4 → 3 → 5 인접 행렬로 구현한 그래프 BFS static void BFS(int[][] graph, int v) { /.. 2023. 3. 7. [graph] 깊이 우선 탐색(DFS, Depth First Search) 그래프 순회(Graph Traversal) 또는 그래프 탐색(Graph Search) 란? 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것 깊이 우선 탐색(DFS, Depth First Search) 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회방법 마지막 갈림길로 되돌아가야하므로 후입선출(Last-IN-First-Out) 구조인 스택(Stack) 사용 사실상 백트래킹과 똑같은 개념을 사용한다. DFS 수행 순서 스택이 공백이 될 때까지 빨간 상자 부분을 반복한다. DFS 과정 표현 ↓ ↓ ↓ ↓ ↓ ↓ ↓ .. 2023. 3. 6. [graph] 인접 리스트로 방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 앞선 무방향 그래프 구현한 게시글과 마찬가지로 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성된다. 정점 i의 진출 차수 = i의 노드의 수 ex) 정점 2의 진출 차수 = 2 JAVA 자료구조 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; class Node { int vertex; //정점 Node link; //다음 연결되어 있는.. 2023. 3. 4. [graph] 인접 리스트로 무방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 각 정점에 대한 인접 정점들을 연결 리스트로 만드는 것 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성된다. 어떤 정점의 연결 리스트는 그 정점에 인접한 정점의 수(= 정점의 차수)만큼 노드가 연결되어 있다. 정점 i의 차수 = i에 연결되어 있는 노드 수 ex) 정점 2의 차수 = 3 JAVA 자료구조 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTo.. 2023. 3. 4. [graph] 인접 배열로 방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 앞의 무방향 그래프를 구현한 게시글과 마찬가지로 n X n 이차원 배열(정점의 수에 대한 정방행렬)을 사용하여 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 저장한다. 행렬의 대각선 값은 항상 0이다. 그러나 ≠ 이므로 대칭을 이루지는 않는다. 행 i의 합 = 정점 i의 진출 차수 열 i의 합 = 정점 i의 진입 차수 ex) 정점 2의 진출 차수 = 0 + 0 + 1 + 1 = 2 정점 2의 집입 차수 = 1 + 0 + 0 + 0 = 1 JAVA 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java... 2023. 3. 4. [graph] 인접 배열로 무방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 그래프를 구성하는 정점에 대해서 두 정점을 연결하는 간선의 유무를 저장하는 방법 n X n 이차원 배열(정점의 수에 대한 정방행렬)을 사용하여 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 저장한다. 이때, 하나의 정점에서 자기 자신으로 간선(=자체 간선)은 존재할 수 없으므로 행렬의 대각선 값은 항상 0 무방향 그래프의 경우 행렬의 (i, j)와 (j,i)의 값이 같으므로 대각선을 중심으로 대칭을 이룬다. 무방향 그래프에서 행 i의 합 = 열 i의 합 = 정점 i의 차수 ex) 정점 2의 차수 = 2행의 합(=1+0+1+1) = 2열의 합(=1+0+1+1) = 3 JAVA로 구현한 코드 import java.io.BufferedReader;.. 2023. 3. 4. [graph] 기본 개념 정리 1. 그래프 G = (V, E) V(vertex) 정점 : 연결할 객체를 나타내는 것 E(edge) 모서리 : 한쌍의 정점을 이은 것 graph란? 연결되어있는 원소간의 관계를 표현한 자료구조 즉, 정점과 간선의 집합 2. 그래프의 종류 종류 설명 무방향 그래프(undirected graph) 간선에 방향이 없는 그래프 임의의 모서리 (x, y)∈E 이면 (y, x)∈E 를 만족한다. 즉, (x, y)와 (y, x)는 같은 간선을 나타낸다. 방향 그래프(directed graph) = 다이그래프(digraph) 간선에 방향이 있는 그래프 = i → j = 로 표현 임의의 모서리 (x, y)∈E 이면 (y, x)∈E 를 만족하지 않는다. 완전 그래프(complete graph) 한 정점에서 다른 모든 정점.. 2023. 3. 3. 이전 1 다음 728x90
