Bài thực hành 4

Xếp hạng đồ thị

List ranking(Graph G){
    List d;
    List rank; 
    makeNullList(&rank);
    rank.Size = d.Size = G.n;
    for (int i = 1; i <= G.n; i++){ // ban đầu mọi rank là 0 và tính bậc phụ thuộc của các đỉnh
        int depend = degreeDepend(G,i);
        d.Data[i] = depend;
    }


    List L1;
    makeNullList(&L1);

    for(int i = 1; i <= G.n; i++){
        if(d.Data[i] == 0){
            insertList(i, &L1);
        }
    }

    int k = 0;
    while (L1.Size > 0){
        List L2;
        makeNullList(&L2);
        for(int i = 0; i < L1.Size; i++){
            int u = L1.Data[i];
            rank.Data[u-1] = k;
            for(int v = 1; v <= G.n; v++){
                if(G.A[u][v] != 0){
                    d.Data[v]--;
                    insertList(v, &L2);
                }
            }
        }
        copyList(&L2, &L1);
        k++;
    }
    return rank;
}	

Phân công công việc