상용 데이터 구조 도 - 토폴로지 정렬

원본 링크:http://www.cnblogs.com/Spground/p/8536159.html
상용 데이터 구조 도 – 토폴로지 정렬
 

상용 데이터 구조 도 토폴로지 정렬

그림

그림 의 저장 소

토폴로지 정렬

코드 예시

 
그림.
수학 에서 하나의 그림 (Graph) 은 물건 과 물건 간 의 관 계 를 나타 내 는 수학 대상 으로 도 론의 기본 적 인 연구 대상 이다.
그림 은 매우 중요 한 데이터 구조 로 실제 생활 의 응용 에 자주 활용 된다.생활 에서 흔히 볼 수 있 는 문제, 예 를 들 어 교통 노선 도, 임무 지정 분배, 공사 기한 계산, 항공 네트워크 등 은 모두 그림 과 관련 된 이론 으로 모델 을 구축 할 수 있다.
다음은 그림 에 대한 몇 가지 정의 이다.
하나의 그림 (Graph) G = (V, E) 은 정점 (vertex) 집합 과 가장자리 (Edge) 집합 E 로 구성 된다.각 변 은 하나의 점 대 (v, w) 이 고 그 중에서 v, w 는 집합 V 에 속한다.때로는 가장자리 엣 지 를 호 (arc) 라 고도 부른다.점 쌍 이 질서 가 있다 면 그림 은 질서 가 있 는 것 (directed) 이 라 고 합 니 다.방향 이 있 는 그림 을 때때로 방향 이 있 는 그림 이 라 고 부른다.정점 v 와 w 인접 (adjacent) 이 적당 하고 (v, w) 만 E 에 속 합 니 다.변 (v, w) 을 가지 고 변 (w, v) 을 가 진 무 방향 그림 에서 w 와 v 가 인접 하고 v 와 w 도 인접 합 니 다.때로는 세 번 째 성분 을 가지 고 있 는데 권 (weight) 이나 값 (cost) 이 라 고 한다.
그림 의 저장 소
간단 한 저장 도 방식 은 인접 행렬 이 라 고 불 리 는 2 차원 배열 a[i][j] 을 사용 하고 배열 의 크기 는 n * n 이 며 n 는 그림 의 정점 개수 이다.그 중에서 정점 i 가 정점 j 로 연결 되면 a[i][j] = 1 그렇지 않 으 면 a[i][j] = 0.이런 저장 방식 의 장점 은 간단 하고 직관 적 이 며 편리 함 을 실현 하 는 것 이다.단점 도 뚜렷 하고 필요 한 저장 공간 이 크다.
n 개의 정점 을 포함 한 그림 G 의 대부분 정점 이 연결 되 지 않 으 면 n * n 인접 행렬 에 대량의 요소 가 0 이라는 것 을 의미한다. 즉, 이때 인접 행렬 은 희소 행렬 이다.
또 다른 흔히 볼 수 있 는 저장 방식 은 인접 표 (adjacent list) 라 고 하 는데 이런 방식 은 n 크기 의 배열 head, 배열 요소 head[i] 를 신청 하고 정점 i 의 모든 인접 맨 밑 으로 구 성 된 링크 의 머리 주 소 를 저장 하 는 것 이다.이런 저장 방식 의 장점 은 앞의 방식 에 비해 저장 공간의 크기 가 현저히 줄어든다.그러나 직관 적 이지 않 고 인 코딩 이 어렵 다 는 단점 이 있다.
토폴로지 정렬
토폴로지 정렬 은 동그라미 가 없 는 그림 의 정점 에 대한 정렬 입 니 다. Vi 에서 Vj 까지 의 경로 가 존재 한다 면 정렬 Vj 에서 Vi 뒤에 나타 나 야 합 니 다.
간단 한 토폴로지 정렬 알고리즘 은 먼저 임의의 입 도 를 0 으로 하 는 정점 을 찾 는 것 이다.그런 후에 우 리 는 이 정점 을 출력 하고 그것 을 가장자리 와 함께 그림 에서 삭제 합 니 다.그리고 그 인접 한 정점 의 입 도 를 1 로 줄인다.그리고 상기 과정 을 반복 하면 직통 도 는 완전히 삭 제 됩 니 다.
알 수 있 듯 이 이 알고리즘 은 먼저 외층 순환 n 회 이 고 그 다음은 내부 순환 에서 입 도 를 0 으로 하 는 정점 을 선택 할 때 내부 순환 n 회 이다.따라서 전체적인 시간 복잡 도 는 n * n 에 이 를 것 이다.
또 다른 좋 은 개선 방법 은 모든 입 도 를 0 인 정점 을 특정한 스 택 에 눌 러 넣 은 다음 에 매번 바닥 요소 A 를 출력 한 후에 A 의 모든 인접 정점 의 입 도 를 1 로 줄 이 는 것 이다. 만약 에 특정한 인접 정점 의 입 도 를 0 이 라면 계속 스 택 에 넣 는 것 이다.반복 상소 작업 지도 창고 비 움.
입 도 0 의 정점 마다 스 택 에 들 어 가 는 작업 n 회 를 실 행 했 고 n 은 정점 임 을 알 수 있다.스 택 에서 나 오 는 요소 A 에 대해 서 는 정점 과 인접 한 입 도 를 1 로 줄 인 다음 에 스 택 에 들 어 가 는 작업 을 최대 m 회 실 행 했 고 m 는 그림 의 개수 이다.따라서 전체적인 시간 복잡 도 는 선형 O(n) 이다.
코드 예제

#include 
#include 


struct Node {
    int value;
    int indegree;
    struct Node *next;
};

//      
struct Node* initAdjList(int n) {
    struct Node* headers;
    headers = (struct Node*)malloc(sizeof(struct Node) * n);
    int i = 0;
    for(i; i < n; i++) {
        headers[i].next = NULL;
        headers[i].value = 0;
        headers[i].indegree = 0;
    }
    return headers;
}

void addAdj(struct Node* header, int m, int n) {
    struct Node* p = &header[m];
    p->value++;
    while(p->next != NULL)
        p = p->next;
    p->next = (struct Node*)malloc(sizeof(struct Node));
    p->next->value = n;
    p->next->next = NULL;
}

//     
void printAdjList(struct Node* header, int n) {
    int i = 0;
    for(i; i < n; i++) {
        struct Node* p = &header[i];
        printf("Number of %d' adj : %d\t", i, p->value);
        while(p->next!= NULL) {
            printf("%d --->%d\t", i, p->next->value);
            p = p->next;
        }
        printf("
");
    }
}

//    
int* topSort(struct Node* headers, int n) {
    int* zeroStack = (int*)malloc(sizeof(int) * n);
    int* result = (int*)malloc(sizeof(int) * n);
    int count = 0;
    int pIndex = -1;
    int i = 0;
    while(i < n) {
        struct Node* p = &headers[i];
        //   0，    
        if(p->indegree == 0)
            zeroStack[++pIndex] = i;
        i++;
    }

    while(1) {
        // top      Node Index
        int zeroIndex = zeroStack[pIndex--];
        result[count++]  = zeroIndex;
        struct Node* zeroNode = &headers[zeroIndex];
        // zeroNode    ，          
        while(zeroNode->next != NULL) {
            struct Node* q = &headers[zeroNode->next->value];
            if(--q->indegree == 0)
                zeroStack[++pIndex] = zeroNode->next->value;
            zeroNode = zeroNode->next;
        }
        //  
        if(pIndex < 0)
            break;
    }

    return result;
}

int main()
{
    int a[7][7] = { {0,1,1,1,0,0,0},
                    {0,0,0,0,1,1,0},
                    {0,0,0,0,0,0,1},
                    {0,0,1,0,0,1,1},
                    {0,0,0,1,0,0,1},
                    {0,0,0,0,0,0,0},
                    {0,0,0,0,0,1,0}
                    };
    int n = 7;
    struct Node* headers = initAdjList(n);
    int i = 0;
    int j = 0;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++) {
            if(a[i][j] == 1)
                addAdj(headers, i, j);
    }

    //     indegree
    for(i = 0; i < n; i++) {
        struct Node* p = &headers[i];
        while(p->next != NULL) {
            headers[p->next->value].indegree++;
            p = p->next;
        }
    }

    int* q = topSort(headers, n);
    printAdjList(headers, n);
    for(i = 0; i < n; i++) {
        printf("%d 
", *q++ + 1);
    }
    return 0;
}

다음으로 전송:https://www.cnblogs.com/Spground/p/8536159.html