그래프1 [Algorithm] 그래프(Graph) 1. 그래프(Graph)란? 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조 (1) 간선(Edge) 종류 무방향 방향 가중치 (2) 정점의 차수(Degree) 정점 x에 연결된 간선의 수 deg(x) := 정점 x의 차수(degree) (3) 차수의 성질 모든 정점의 차수의 합 = 간선의 개수의 2배 2. 그래프(Graph)를 저장하는 방법 (1) 인접 행렬 (Adjacency Matrix) int[][] adj = int new[V][V] O(V^2) 만큼의 공간 필요 A에서 B로 이동 가능? 가중치 얼마? => O(1) 정점 A에서 갈 수 있는 정점들은? => O(V) ex) V=10만, E=50만 => V^2 = 100억 = 10GB (2) 인접 리스트 (Adjacency List) A.. 2022. 2. 12. 이전 1 다음 반응형
