유혁스쿨

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

그래프 노드와 엣지로 구성된 집합. 예) 트리 노드 데이터 표현 단위 엣지 노드를 연결할 때 사용 그래프 알고리즘 종류 유니온 파인드 위상 정렬 다익스트라 벨만-포드 플로이드-워셜 최소 신장 트리 유니온 파인드 그래프의 `사이클 생성 유무`를 판단하는 알고리즘 그래프에서만 쓰이는 알고리즘은 아님 사용 예) `집합에서 대표 노드 탐색` 혹은 `각 원소들을 유니온 하여 하나의 집합으로 통합` ex) 3개의 노드와 2개의 엣지로 구성되었다고 가정했을 때 엣지를 추가할 경우 현재 그래프에 사이클이 생성되는가 → 유니온 파인드로 사이클 생성 여부를 도출한다. 위상 정렬 그래프의 각 노드들을 선형으로 정렬하는 알고리즘 알고리즘 사용 선 조건 사이클이 없어야 한다. 방향(간선)이 있는 그래프이다. ⓐ → ⓑ → ⓒ ..