以judge第七次作业第三题为例

Prim算法

邻接表实现

AC源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <stdlib.h>

#define Infinity 1000000
typedef struct edge {
    int id;
    int adjvex;
    int weight;
    struct edge *link;
} Edge, *Edgeprt;
typedef struct node {
    int data;
    Edgeprt link;
} Node, *Nodeprt;
Nodeprt G[205];
int edge_to_weight[205];

void insert_edge(int ID, int a, int b, int wei) {
    Edgeprt p = (Edgeprt) malloc(sizeof(Edge));
    p->id = ID;
    p->weight = wei;
    p->adjvex = b;
    p->link = NULL;
    if (G[a] == NULL) {
        G[a] = (Nodeprt) malloc(sizeof(Node));
        G[a]->link = p;
    } else {
        Edgeprt q = G[a]->link;
        for (; q->link != NULL; q = q->link);
        q->link = p;
    }
}

void prim(int dis[], int src, int edges[], int n) {
    //初始化
    Edgeprt p = G[src]->link;
    for (int i = 0; i < n; i++) {
        dis[i] = Infinity;
    }
    for (; p != NULL; p = p->link) {
        dis[p->adjvex] = p->weight;
        edges[p->adjvex] = p->id;
    }
    dis[src] = 0;
    for (int i = 1; i < n; i++) {
        int min = Infinity;
        int k = 0;
        for (int j = 0; j < n; j++) {
            if (dis[j] != 0 && dis[j] < min) {
                min = dis[j];
                k = j;
            }
        }
        //找到了最近的k号结点
        dis[k] = 0;//k到生成树的距离为0
        p = G[k]->link;
        for (; p != NULL; p = p->link) {
            if (dis[p->adjvex] != 0 && p->weight < dis[p->adjvex]) {
                dis[p->adjvex] = p->weight;
                edges[p->adjvex] = p->id;
            }
        }
    }
}

int cmp(const void *e1, const void *e2) {
    int p1 = *(int *) e1;
    int p2 = *(int *) e2;
    if (p1 > p2)return 1;
    else if (p1 < p2)return -1;
    else return 0;
}

int main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int num_node, num_edge;
    scanf("%d%d", &num_node, &num_edge);
    int id, a, b, wei;
    for (int i = 1; i <= num_edge; i++) {
        scanf("%d%d%d%d", &id, &a, &b, &wei);
        insert_edge(id, a, b, wei);
        insert_edge(id, b, a, wei);
        edge_to_weight[id] = wei;
    }
    int edges[205] = {0};
    int dis[205] = {0};
    prim(dis, 0, edges, num_node);
    //edges里面存着边序号，
    int sum = 0;
    for (int i = 0; i < num_node; i++) {
        sum += edge_to_weight[edges[i]];
    }
    //实际上只有num_node-1条边，但是由于edges[0]=0无法改变，倒置所有边的下标要后移一位，从1~num_node-1的下标，
    qsort(edges, num_node, sizeof(edges[0]), cmp);
    printf("%d\n", sum);
    for (int i = 1; i < num_node; i++) {
        printf("%d ", edges[i]);
    }
    return 0;
}

邻接表的prim详解

prim算法的两个集合分为已经有的结点集合（最小生成树集合）----Tree，未加入生成树的结点集合Vertex

最开始生成树只有初始结点src，我们需要初始化所有结点到生成树的距离数组dis[]

所有初始距离为Infinity无穷大----自定义一个比所有权重都要大的数值

以下是重复过程：

​ 每次加入一个距离生成树最近的结点node，

​ 修改新加入的node到生成树的距离为0

​ 然后对于新加入的结点node，去更新所有与node相连，并且对于未加入生成树的集合Vertex的距离

​ 同时加入那些更新的距离对应的边

最开始所有结点都在Vertex中，那么所有结点到生成树的距离就是无穷Infinity

则有初始化代码

1
2
3
for (int i = 0; i < n; i++) {
        dis[i] = Infinity;
    }

然后加入第一个结点src，加入到生成树后，我们需要执行上面的“重复过程”

1
2
3
4
5
6
dis[src] = 0;						#修改距离为0
Edgeprt p = G[src]->link;			#更新这个结点所有相连的结点
for (; p != NULL; p = p->link) {
    dis[p->adjvex] = p->weight;		#更新结点的距离，由于此时生成树只有一个结点，所以不需要跳过任何结点
    edges[p->adjvex] = p->id;		#加入更新结点的边
}

对于第一个结点之后的结点，由于最终有n个结点，因此还需要执行n-1次加入单个结点的过程，外层循环n-1次

对于每个“重复过程”，先寻找最近的未加入的结点

1
2
3
4
5
6
7
8
9
10
int min = Infinity;
        int k = 0;								#记录找到的结点编号
        for (int j = 0; j < n; j++) {
            if (dis[j] != 0 && dis[j] < min) {	#需要找所有结点0~n-1中未加入的结点的距离的最小值
                min = dis[j];					#dis[j]!=0就是对于未加入的结点的一个筛选，
                k = j;
            }
        }
        //找到了最近的k号结点
        dis[k] = 0;//k到生成树的距离为0				#加入生成树，距离设置为0

新节点加入生成树之后，我们要去更新那些未加入的结点到生成树的距离

1
2
3
4
5
6
7
p = G[k]->link;
for (; p != NULL; p = p->link) {	#循环找所有与新加入的结点有边的结点去更新距离（只更新不在生成树的）
    if (dis[p->adjvex] != 0 && p->weight < dis[p->adjvex]) {#加入dis[p->adjvex]!=0去筛选不在生成树内的结点
        dis[p->adjvex] = p->weight;
        edges[p->adjvex] = p->id;	#每个更新的结点的边都要加入生成树的边
                 }
        }

到这里prim算法得到生成树就结束了，这里再对每次更新边的序号做一个小解释

每次更新结点到生成树的距离的时候都会有一个代码就是

edges[p->adjvex] = p->id

每次我们加入一个最近结点之后，都要更新距离，如果一个结点到生成树的距离可以被更新，那么是不是说明这个结点在下一次寻找最近结点的时候是有可能被作为最近结点的，所有被更新的结点都有可能接入，而我们更新的边，是在更新某个结点之后紧接着进行的，就是说如果这个结点在下一次的过程有可能作为最近结点，那么它作为最近结点加入生成树所对应的边就是我们更新的边，因为一个结点加入生成树是需要连接一条边的（除了第一个初始结点）

一个结点的距离被更新，它就具有了下一次加入生成树的可能性

假如它真的能够在下一次加入生成树，那么我们更新的这个距离就是它接入生成树的边的权重

上面是一个重复性的过程，所有加入生成树的结点都要经历这一过程，也就是他们的边都被加入edges数组，同时这个edges数组的更新是一个不断覆盖的过程，有的结点距离更新了很多次才加入生成树，对应的它的边也更新了很多次，每次更新都会覆盖之前的数值。

邻接矩阵

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <stdlib.h>

#define Infinity 1000000
typedef struct node {
    int data;
    struct node *link;
} Node, *Nodeprt;
int weight[105][105];
int edge[105][105];
int edge_to_weight[205];

void prim(int src, int n, int edges[]) {
    int dis[205], k;
    for (int i = 0; i < n; i++) {
        dis[i] = Infinity;
    }
    dis[src] = 0;//加入生成树
    for (int i = 1; i < n; i++) {
        if (weight[src][i] != 0) {
            dis[i] = weight[src][i];
            edges[i] = edge[src][i];
        }
    }
    for (int i = 1; i < n; i++) {
        int min = Infinity;
        for (int j = 0; j < n; j++) {
            if (dis[j] != 0 && dis[j] < min) {
                min = dis[j];
                k = j;
            }
        }
        dis[k] = 0;
        for (int i = 0; i < n; i++) {
            if (dis[i] != 0 && weight[k][i] != 0 && weight[k][i] < dis[i]) {
                dis[i] = weight[k][i];
                edges[i] = edge[k][i];
            }
        }
    }
}

int cmp(const void *e1, const void *e2) {
    int p1 = *(int *) e1;
    int p2 = *(int *) e2;
    return p1 - p2;
}

int main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int num_node, num_edge;
    scanf("%d%d", &num_node, &num_edge);
    int id, a, b, wei;
    for (int i = 0; i < num_edge; i++) {
        scanf("%d%d%d%d", &id, &a, &b, &wei);
        edge[a][b] = edge[b][a] = id;
        weight[a][b] = weight[b][a] = wei;
        edge_to_weight[id] = wei;
    }
    int edges[105] = {0};
    prim(0, num_node, edges);
    qsort(edges, num_node, sizeof(edges[0]), cmp);
    int sum = 0;
    for (int i = 1; i < num_node; i++) {
        sum += edge_to_weight[edges[i]];
    }
    printf("%d\n", sum);
    for (int i = 1; i < num_node; i++) {
        printf("%d ", edges[i]);
    }
    return 0;
}

Kruskal算法