토폴로지 (TOP) 정렬

3848 단어 해제데이터 구조알고리즘제목.문제 집
오늘 이야기 하고 자 하 는 것 은 도 론 에서 매우 중요 한 것 중 하나 인 토폴로지 정렬 이 라 고도 부 르 고 top 정렬 이 라 고도 부른다. 그러나 우 리 는 먼저 AOV 망 을 소개 해 야 한다.공식 학술 언어 를 알 고 싶 은 사람 이 있 으 면 여기에 찔러 라.여기 서 편 의 를 위해 우 리 는 간단 한 정 의 를 사용한다. 즉, 정점 으로 활동 을 표시 하고 활동 의 선후 순 서 를 나타 내 는 방향 도 를 사용한다.토폴로지 정렬 이란 AOV 네트워크 에서 모든 점 을 그들의 논리 적 관계 에 따라 선형 서열 로 배열 하 는 것 을 말 하 는데 모든 점 의 전구 가 그 앞 에 배열 되 어 top 서열 이 라 고 부른다.방법 은 다음 과 같다.
4. 567917. 입 도 를 0 으로 하 는 점 을 선택 하여 top 번 호 를 주 십시오
4. 567917. 이 점 과 그 모든 아웃 사 이 드 를 삭제 합 니 다
4. 567917. 1, 2 를 반복 하여 입도 가 0 인 점 이 하나 도 없 을 때 까지 반복 한다.검사: top 시퀀스 의 포인트 가 총 포인트 라면 top 성공!그렇지 않 으 면 동그라미 가 하나 생 길 것 이다.프로그램
in 배열 로 각 점 의 입도 개 수 를 표시 하고 g 배열 로 임의의 두 점 이 연결 되 어 있 는 지 없 는 지 를 표시 하 며 총 점 수 는 n 으로 표시 합 니 다.
do{
        i++;j=1;
        while(j<=n && in[j])j++;
        if(j>n)break;
        ans[i]=j;in[j]=1;
        for(k=1;k<=n;k++)
            if(g[j][k])
                in[k]--;
    }while(i

지금 우 리 는 예 제 를 보 자. 병사 들 이 줄 을 서 라.이것 은 누 드 top 정렬 이기 때문에 템 플 릿 만 설치 하면 됩 니 다. 자세 한 내용 은 코드 를 보십시오!
using namespace std;
int g[110][110],in[110],ans[110],q[110];
void out(int tail){
    printf("%d",ans[1]);
    for(int i=2;i<=tail;i++)
        printf(" %d",ans[i]);
    puts("");
}
int main(){
    int i,j,k,n,m,a,b;
    scanf("%d",&n);
    while(scanf("%d %d",&a,&b)==2){
        g[a][b]=1;in[b]++;
    }
    i=0;
    do{
        i++;j=1;
        while(j<=n && in[j])j++;
        if(j>n)break;
        ans[i]=j;in[j]=1;
        for(k=1;k<=n;k++)
            if(g[j][k])
                in[k]--;
    }while(iif(in)printf("Impossible
");
    else out(i);
    return 0;
}

구체 적 인 top 은 구체 적 인 문제 와 분석 해 야 합 니 다. 템 플 릿 문 제 는 비교적 적 고 중심 은 활용 입 니 다!
CleanCode 6장 객체와 자료구조
Gradle (2) - 자신의 응용 프로그램을 실행합니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage