0-Preview
调试堆相关内存分配时，发现每一个非物理相邻的被 free chunk 的数据结构会有所变化，可能是为了方便 bin 管理？
刚好最近数据结构学到了有关的知识，来分析一下两种算法的设计。
（草稿阶段，完善后会删掉这句话，严谨来讲本文不一定正确。）
1-Prim算法
🔑算法设计思想：
从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1，再连接与 T1 最近顶点 v2 构成树 T2， 如此重复直到所有顶点均在所构成树中为止。
📖算法步骤：
1.先选中一个顶点作为已选顶点，放到集合中。
1
2
3
4
5
6
| C++
#include<stdio.h>
#define MAXN 1000
/*二维数组存储 采用邻阶矩阵数据*/
int input[MAXN][MAXN];
int sign[MAXN]= {0}; // 标记sign数组 初始化全为0 ，1表示已经加入已选列表
|
2.选择图中距离这棵树最近但是没有被树收录的一个顶点，把他收录在树中，并且保证不构成回路.
1
2
3
4
| C++
for(int i=1; i<=n; i++) {
if(sign[i]==0) continue; // 如果当前为加入队列 直接下一次循环 其实这是一个笨方法
for(int j=1; j<=n; j++) {
|
3.按照这样的方法，把所有的图的顶点一一收录进树中。
1
2
3
4
5
6
7
| C++
if(sign[j]==1||input[i][j]==0)
continue;
if(input[i][j]<minNodeValue){// 更小的一个进行标记
flagX=i;
flagY=j;
minNodeValue=input[i][j];
|
4.如果没有顶点可以收录
-a.如果图中的顶点数量等于树的顶点数量–>最小生成树构造完成
-b. 如果图中的顶点数量不等于树的顶点数量–>此图不连通
代码
还是老样子，代码看是看不明白的，能单步调试尽量调试，尤其是牵扯到底层结构的。
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
| C
/*最小生成树 prim算法 从一个连通图中获取一个最小生成树*/
/*
输入要求：输入一个连通图 存储模式：邻接矩阵表示 0表示不可达 点依次默认命名为a,b,c,d,e,f,g...
例如：n*n数组
6
0 1 0 0 6 5
1 0 1 0 0 4
0 1 0 6 0 4
0 0 6 0 8 5
6 0 0 8 0 2
5 4 4 5 2 0
即为一种输入 实际上为上课讲解时的连通图表示
输出要求： n-1长度数组 包含n-1条路径 ()表示的为m号点到k号点的那条路径
(1,2) (2,3) (2,6) (6,5) (6,4)
最小生成树权值之和：1+1+4+5+2=13
*/
#include<stdio.h>
#define MAXN 1000
/*二维数组存储 采用邻阶矩阵数据*/
int input[MAXN][MAXN];
int sign[MAXN]= {0}; // 标记sign数组 初始化全为0 ，1表示已经加入已选列表
int prime(int n) {
int sum=0; // 最小生成树权值之和 初始值为0
/* 默认从第一个点开始 */
sign[1]=1;
int counter=1; // 计算当前状态已加入最小生成树队列的个数
int flagX=-1,flagY=-1,minNodeValue=1000000;
while(counter!=n) {
flagX=-1,flagY=-1,minNodeValue=1000000; // 每一次都要初始化
/* 每一次循环都是一次贪心 当前局势的一种最优解 */
for(int i=1; i<=n; i++) {
if(sign[i]==0) continue; // 如果当前为加入队列 直接下一次循环 其实这是一个笨方法
for(int j=1; j<=n; j++) {
// 在查找下一个连接点时 发现这个连接点已经在里面了（或者为0，即不可达） 我们直接跳过 我能说这是一个笨方法么？但似乎只能这样
if(sign[j]==1||input[i][j]==0) continue;
if(input[i][j]<minNodeValue){
// 更小的一个进行标记
flagX=i;
flagY=j;
minNodeValue=input[i][j];
}
}
}
/* 一轮查找后 */
sign[flagY]=1; // 谁该标1 要清楚
counter++; // 找到加一
sum+=input[flagX][flagY]; // 这里其实不用担心指针越界 如果是连通图 在一轮查找下来 肯定能找到一个最小的
printf(" (%d,%d) ",flagX,flagY); // 其实我们都知道 flagX flagY 的位置 在这里顺序不重要
}
return sum;
}
int main() {
/*作为输入的主函数*/
int n;
printf("请输入邻接矩阵的维度n：");
scanf("%d",&n);
printf("邻接矩阵：\n");
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
scanf("%d",&input[i][j]);
}
}
/*调用函数*/
int sum = prime(n);
printf("\n最小生成树权值之和：sum=%d\n",sum);
}
|
2-Kruskal 算法—将树合并成森林
🔑算法设计思想：
把n个顶点看成看成n棵分离的树（每棵树只有一个顶点），每次选取可连接两个分离树中权值最小的边把两个分离的树合成一个新的树取代原来的两个分离树，如果重复n-1步后便得到最小生成树。
输入： 图G
输出： 图G的最小生成树
具体流程：
(1)将图G看做一个森林，每个顶点为一棵独立的树
(2)将所有的边加入集合S，即一开始S = E
(3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E’
(4)重复(3)直到所有点属于同一棵树，边集E’就是一棵最小生成树
kruskal算法与Prim算法的区别在于每次都选权值最小的边加入
📖算法步骤：
1.图的存储结构(a，b为边的两个顶点，w为边的权值)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| CPP
#define Max 50
typedef struct road *Road;
typedef struct road
{
int a , b;
int w;
}road;
typedef struct graph *Graph;
typedef struct graph
{
int e , n;
Road data;
}graph;
|
2.排序sort函数（按照权值从小到大）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| CPP
void sort(Road data, int n)
{
int i , j;
for(i = 1 ; i <= n-1 ; i++)
{
for(j = 1 ; j <= n-i ; j++)
{
if(data[j].w > data[j+1].w)
{
road t = data[j];
data[j] = data[j+1];
data[j+1] = t;
}
}
}
}
|
3.getRoot寻源函数（v为并查集，x为待查顶点）
1
2
3
4
5
6
7
8
9
| CPP
int getRoot(int v[], int x)
{
while(v[x] != x)
{
x = v[x];
}
return x;
}
|
代码
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
105
106
107
108
109
110
111
112
113
114
115
| CPP
#include <stdio.h>
#include <stdlib.h>
#define Max 50
typedef struct road *Road;
typedef struct road
{
int a , b;
int w;
}road;
typedef struct graph *Graph;
typedef struct graph
{
int e , n;
Road data;
}graph;
Graph initGraph(int m , int n)
{
Graph g = (Graph)malloc(sizeof(graph));
g->n = m;
g->e = n;
g->data = (Road)malloc(sizeof(road) * (g->e));
return g;
}
void create(Graph g)
{
int i;
for(i = 1 ; i <= g->e ; i++)
{
int x , y, w;
scanf("%d %d %d",&x,&y,&w);
if(x < y)
{
g->data[i].a = x;
g->data[i].b = y;
}
else
{
g->data[i].a = y;
g->data[i].b = x;
}
g->data[i].w = w;
}
}
int getRoot(int v[], int x)
{
while(v[x] != x)
{
x = v[x];
}
return x;
}
void sort(Road data, int n)
{
int i , j;
for(i = 1 ; i <= n-1 ; i++)
{
for(j = 1 ; j <= n-i ; j++)
{
if(data[j].w > data[j+1].w)
{
road t = data[j];
data[j] = data[j+1];
data[j+1] = t;
}
}
}
}
int Kruskal(Graph g)
{
int sum = 0;
//并查集
int v[Max];
int i;
//init
for(i = 1 ; i <= g->n ; i++)
{
v[i] = i;
}
sort(g->data , g->e);
//main
for(i = 1 ; i <= g->e ; i++)
{
int a , b;
a = getRoot(v,g->data[i].a);
b = getRoot(v,g->data[i].b);
if(a != b)
{
v[a] = b;
sum += g->data[i].w;
}
}
return sum;
}
int main()
{
int m , n , id = 1;
while(scanf("%d %d",&m,&n) != EOF)
{
int r , i;
Graph g = initGraph(m,n);
create(g);
r = Kruskal(g);
printf("Case %d:%d\n",id++,r);
free(g);
}
return 0;
}
|
