Bài thực hành 5

Giải thuật Prim

⚠️ LƯU Ý

Sử dụng cho danh sách đỉnh đỉnh

:::

int prim(Graph G, Graph *T){
    int cost[MAX], parrent[MAX];
    bool mark[MAX];

    init_Graph(T, G.n);
    int sumW = 0;
    for(int i = 1; i <= G.n; i++){
        cost[i] = 999;
        mark[i] = false;
        if(G.A[1][i]){
            cost[i] = G.A[1][i];
            parrent[i] = 1;
        }
    }

    cost[1] = 0; // có thể thay đổi
    mark[1] = true;

    for(int i = 1; i < G.n; i++){
        int min_dist = 999;
        int min_u;
        for(int j = 1; j <= G.n; j++){
            if(!mark[j]){
                if(min_dist > cost[j]){
                    min_dist = cost[j];
                    min_u = j;
                }
            }
        }
        int u = min_u; //đánh dấu pi[u] nhỏ nhất
        mark[min_u] = true;
        add_edgeDirection(T, parrent[min_u], min_u, min_dist);
        sumW += min_dist;

        // cập nhật lại pi và p của đỉnh kề với u
        for(int v = 1; v <= G.n; v++){
            if(!mark[v]){
                if(G.A[u][v])
                    if(cost[v] > G.A[u][v]){
                        cost[v] = G.A[u][v];
                        parrent[v] = u;
                    }
            }
        }
    }
    return sumW;
}

Giải thuật Kruskal

⚠️ LƯU Ý

Sử dụng cho danh sách cung

void swap(Edge *a, Edge *b){
    Edge temp = *a;
    *a = *b;
    *b = temp;
}
void bubbleSort(Graph *G){
    int n = G->m;
    for(int i = 0; i < n - 1; i++){
        for(int j = n - 1; j >= i + 1; j--){
            if(G->edges[j].w < G->edges[j-1].w)
                swap(&G->edges[j], &G->edges[j-1]);
        }
    }
}

int kruskal(Graph G, Graph *T){
    int parent[MAX];
    int sumW = 0;
    
    initGraph(T, G.n);
    bubbleSort(&G);

    for(int i = 1; i <= G.n; i++){
        parent[i] = i;
    }
    
    for(int e = 0; e < G.m; e++){
        int u = G.edges[e].u;
        int v = G.edges[e].v;
        int w = G.edges[e].w;

        int rootU = parrent[u];
        int rootV = parrent[v];
        if(rootU != rootV){
            addEdge(T, u,v,w);
            parent[rootV] = rootU;
            sumW += w;
        }
    }
    return sumW;
}