유혁스쿨

다익스트라 그래프에서 최단 거리를 구하는 알고리즘 기능 특징 (제약조건) 시간 복잡도 (노드 수: V, 엣지 수:E) 출발 노드와 모든 노드간의 최단 거리 탐색 엣지는 모두 양수 O(ElogV) 핵심이론 5단계로 구현한다 [그래프] ８ 15 ① → ② → ⑤ ↓3 ↓4 ↗2 ③ → ④ 13 Step 01) 인접 리스트로 그래프 구현 ① → [ ②, 8 ] [ ③, 3 ] ② → [ ④, 4 ] [ ⑤, 15 ] ③ → [ ④, 13 ] ④ → [ ⑤, 2 ] ⑤ 그래프 데이터를 자료구조 ArrayList 에 저장한다 다익스트라 알고리즘은 인접 행렬로 구현해도 좋으나 시간복잡도 측면 N의 크기가 클 것을 대비해 인접리스트를 선택하여 구현하는 것이 좋다. Step 02) 최단거리 배열 초기화 최단거리 배열 ..

위상정렬 사이클이 없는 방향에서 노드 순서를 갖는 정렬 기능 특징 시간복잡도 (노드수: V, 엣지수: E) 노드간 순서 결정 사이클이 없어야 함 O(V+E) 항상 유일한 값으로 정렬되지 않음 사이클 존재시 노드간 순서를 명확하게 정의 불가 (위상정렬 적용 불가) 핵심 이론 인접리스트 , 진입차수배열 , 위상정렬배열 세가지를 구현한다. 1. 그래프를 인접리스트로 구현 2. 구현된 인접리스트의 진입차수를 계산하여 진입차수 배열에 저장 3. 진입차수배열에서 진입차수가 0인 노드 선택 4. 선택된 노드 위상정렬 배열에 저장 5. 저장된 노드가 가리키는 노드들의 진입차수를 -1 연산 후 저장(선택) 된 노드의 다음노드를 진입차수 배열에서 다시 선택 6. 3 ~ 5 과정을 반복하며 모든 노드가 정렬될 경우 종료 [..