[알고리즘]그래프2 - 구현(feat. Java)
2차원 배열 2차원 배열을 사용하여 정점에서 다른 정점으로 가는 간선의 존재유무(1 : 존재, 0 : 없음)를 알 수 있다. 2차원 배열을 사용할 경우 연결된 정점을 찾기 쉽고 구현이 쉽다는 장점이 있지만 O(n^2)의 공간 복잡도를 가진다는 단점이 있다. 구현 코드 public static void main(String[] args) { int[][] edges = new int[][] { {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5} }; int n = 5; //정점의 개수 int[][] matrix = new int[n + 1][n + 1]; for(int[] edge : edges) { //무방향 그래프이기 때문에 양쪽 모두 1로 초기화 matrix[edge[..
2023. 9. 21.
[알고리즘] 그래프1 - 그래프란?
그래프란? 그래프는 정점(노드, Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 의미이다. 위의 그림에서, V(G) = {1, 2, 3, 4, 5}이고, E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} 이다. 그래프의 종류 무방향 그래프 이름 그대로 간선에 방향이 없는 그래프이다. 그렇기 때문에 정점 v와 정점 w를 잇는 간선 (v, w)가 있다고 하면 (w, v)도 같은 간선이 되는 것이다. 그러므로 정점이 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다. 방향 그래프 간선에 방향이 있는 그..
2023. 9. 21.
