유혁스쿨

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

그래프의 표현 그래프를 표현할때는 대표적으로 엣지리스트, 인접행렬, 인접리스트 3가지 방법으로 표현한다. 그래프 예 ① → ② → ⑤ ↓ ↓ ↗ ③ → ④ 엣지리스트 엣지를 중심으로 그래프를 표현한다. 배열에 출발,도착 노드를 각각 저장하여 엣지를 표현한다. 가중치가 있는 노드의 경우 배열에 가중치를 추가 행으로 함께 저장한다. 가중치 없는 그래프 표현 출발, 도착 2개의 노드만 2개의 배열행을 구성하여 표현한다. ex) 첫번째 행을 [1, 2]로 표현하며 1에서 2로 뻗어가는 엣지를 뜻한다. ⓢ ⓔ 1 2 1 3 3 4 2 4 2 5 4 5 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 노드를 배열에 저장하여 엣지를 표현하므로 엣지리스트 라고 한다. 방향이 없는 그..