루프 없 는 토폴로지 정렬 (DFS 구현)
5021 단어 컴퓨터 알고리즘 설계 및 분석
// enDegree ，
// graph ， ，graph[i][j] i j
// ，i j ， j， i
int topSort(vector<vector<int>>& relayVec, vector<int>& enDegree) {
queue<int> myQueue;
for (int i = 0; i < enDegree.size(); ++i) {
if (enDegree[i] == 0){
myQueue.push(i);
}
}
while(!myQueue.empty()){
int top = myQueue.front();
for(int i = 0;i<relayVec[top].size();++i){ // top 1， 0，
if(--enDegree(relayVec[top][i])==0)
myQueue.push(relayVec[top][i]);
}
}
2. 알고리즘 복잡 도 분석 상기 토폴로지 정렬 에서 처음으로 입 도 를 0 으로 하 는 정점 을 대기 열 에 추가 한 다음 에 복잡 도 는 O (n) 이다. 그 다음 에 순환 에서 한 노드 가 튀 어 나 올 때마다 이 노드 에 의존 하 는 노드 의 입 도 를 1 번 줄 이 고 의존 관 계 를 한 번 방문 하 는 것 을 찾는다. 즉, 한 변 을 방문 하 는 것 이다. 전체 절차 에서 모든 정점 과 그 인접 한 변 은 1 번 만 방문 된다.따라서 전체 시간 복잡 도 는 O (m + n) 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
컴퓨터 알고리즘 설계 및 분석 1 - 5 최대 간극 문제적어도 한 구간 은 비어 있 고, 가장 큰 인접 간극 은 좌우 구간 중간 에 빈 상태 에서 발생 하 며, 한 구간 이 아 닌 다음 구간 의 왼쪽 경 계 를 찾 아 이전 구간 의 오른쪽 경계 최대 치 를 빼 면 된다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
