welcome
0%

c-贪心算法解决最小生成树

发表于 更新于 分类于

生成最小生成树的Kruakal算法

Kruakal算法只与边有关，适用于稀疏图。
算法思想：

难点在于判断回路是否形成。
看是否有回路这里主要是使用并查集的方法判断,如果加入的点有回路则边的两点有共同的父节点。即find[x]==find[y].

并查集代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//初始化
int fa[maxn];
void init(int n)
{
    for(int i=0;i<=n;i++)
    fa[i]=i;
}
//查找父节点
int find(int x)
{
 return fa[x]==x?x:fa[x]=find(fa[x]);
}
// 合并
void merge(int i,int j)
{
    fa[find(i)]=find(j);
}

代码

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<iostream>
#include<algorithm>
#include<time.h> 
#include<cmath>
#include<vector>
#define maxn 1024
using namespace std;
long long n,matrix[maxn][maxn],fa[maxn],sum=0,len=0;
//int s=0;
void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}
//结构化点与边、权值 
struct GVE
{
	int x,y,w;
}G[maxn];
//cmp用于排序 内部比交 
int cmp(GVE a,GVE b)
{
	if(a.w!=b.w) return a.w>b.w;//大于符号用于从大到小排序 
	else
	return a.x>b.x;
}
//初始化数据 
class init
{
	public:
	void create()
	{
		cout<<"输入n:";
		cin>>n;
		//全部赋值为零
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		matrix[i][j]=maxn;
		//初始化邻接矩阵
		for(int i=0;i<n;i++)
		{
			if(i==0)
			{
				matrix[i][1]=rand()%n+1;
				matrix[i][2]=rand()%n+1;
			}
			else
			for(int j=i+1;j<n;j++)
			matrix[i][j]=rand()%n+1; 
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(matrix[i][j]!=maxn)
				{
					G[len].x=i;
					G[len].y=j;
					G[len].w=matrix[i][j];
					len++;
				}
			}
		}
		
	}
};
//并查集 
void Finit()
{
	for(int i=0;i<n;i++)
	fa[i]=i;
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	fa[find(x)]=find(y);
}
//打印图
void print() 
{
	cout<<n<<"*"<<n<<"阶的邻接矩阵："<<endl; 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		if(matrix[i][j]==maxn)
		cout<<"m"<<" ";
		else
		cout<<matrix[i][j]<<" ";	
		cout<<endl;	
	}	
}
//kruakal算法
void kruakal()
{
	int x,y,w;
	vector<int> T[3];
	while(T[0].size()<n-1)
	{
		len--;
		x=find(G[len].x);
		y=find(G[len].y);
		w=G[len].w;
		if(x!=y)
		{
			T[0].push_back(x);
			T[1].push_back(y);
			T[2].push_back(w);
			sum+=w;
			merge(x,y);
		}	
	}
	cout<<"通过kruakal算法得到的最小生成树："<<endl;
	for(int i=0;i<n-1;i++)
	{
		printf("边：(%d,%d)  权值：%d\n",T[0][i],T[1][i],T[2][i]);
	}
	cout<<"权值和："<<sum;

} 

int main()
{	 
	//数据初始化 
	init M;
	rand_seed();
	M.create();
    Finit();
    print();
    cout<<endl;
	sort(G,G+len,cmp);
	/*测试使用 
	for(int i=0;i<len;i++)
        {
    	cout<<"x: "<<G[i].x<<" y:"<<G[i].y<<"  w:"<<G[i].w<<endl;
	}
	cout<<endl;
	*/
	kruakal();
}

运行结果

经典案列


代码修饰后运行结果：

生成最小生成树prim算法

prim算法只与点有关，适用于点较少的稠密矩阵。
算法思想：

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<time.h>
#define maxn 1024
using namespace std;
long long matrix[maxn][maxn],n;
void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}
struct GVE
{
	int x,y,w;
}G[maxn];
class init
{
	public:
	void create()
	{
		cout<<"输入n:";
		cin>>n;
		//全部赋值为零
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		matrix[i][j]=maxn;
		//初始化d对称矩阵
		for(int i=0;i<n;i++)
		{
			if(i==0)
			{
				matrix[i][1]=rand()%n+1;
				matrix[i][2]=rand()%n+1;
			}
			else
			for(int j=i+1;j<n;j++)
			matrix[i][j]=rand()%n+1; 
		}
        for(int i=0;i<n;i++)
        {
        	for(int j=0;j<i;j++)
        	{
        		matrix[i][j]=matrix[j][i];
			}
		}
		
	}
};
//打印图
void print() 
{
	cout<<n<<"*"<<n<<"阶的邻接矩阵："<<endl; 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		if(matrix[i][j]==maxn)
		cout<<"m"<<" ";
		else
		cout<<matrix[i][j]<<" ";	
		cout<<endl;	
	}	
}
void perm()
{
	cout<<"出发顶点：";
	int x,g=0;
	cin>>x; 
	//X表示要联通的结点。C1表示边，C2表示权值 
	int X[maxn],Y[maxn],C1[maxn],C2[maxn];
	//初始化数据 
	 X[0]=x;
     for(int i=0;i<n;i++)
     Y[i]=i;
     for(int i=0;i<n;i++)
     {
     	if(i==x)
     	{
     		for(int k=i;k<n-1;k++)
     		Y[k]=k+1;
     		break;
		}
	 }
	 int len=n-1;
	 for(int i=0;i<n;i++)
	 {
	 	C1[i]=x;
	 	C2[i]=maxn;
	 }
	 //计算 
	 while(len!=0)
	 {
	 	for(int i=0;i<len;i++)
	 	{
	 		if(matrix[x][Y[i]]!=maxn)
	 		{
	 			int b=matrix[x][Y[i]];
	 			if(b<C2[Y[i]])
	 			{
	 				C2[Y[i]]=b;
	 				C1[Y[i]]=x;
				 }
	 			
			}
		}
		int minx=C2[Y[0]],u=0;
		for(int i=1;i<len;i++)
		{
			if(minx>C2[Y[i]])
			minx=C2[Y[i]];
		}
		for(int i=0;i<len;i++)
		{
			if(minx==C2[Y[i]])
			{
				u=i;
				break;
			}
			
		}
		//将外部的点与内部点连接并保存到树中 
	    int z=C1[Y[u]];
	    G[g].x=Y[u];
	    G[g].y=z;
	    G[g].w=minx;
	    g++;
	    //更新X，Y；
		X[n-len]=Y[u];
		x=Y[u];
		C2[Y[u]]=maxn;
        for(int i=u;i<len-1;i++)
        Y[i]=Y[i+1];
	    len--;
			 
	 }
	 for(int i=0;i<g;i++)
	 {
	 	printf("边 (%d,%d)",G[i].x,G[i].y);
	 	printf("  权值：%d \n",G[i].w);
	  } 
}
int main()
{
	//数据初始化 
	init M;
	rand_seed();
	M.create();
    print();
    perm();
	return 0;
 }

运行结果：

单元最短路径问题

算法思想：

实现：

伪代码：

输入： 一个大于1的整数n.

输出： 一个随机生成的有向图G=（V，E），对于每一条边，有一个非负数字c(u，v)与之相关。
对于每个顶点v∈V,得到从v_0 到v的最短路径的长度。
程序运行时间。

步骤1： 随机生成一个有向图G=（V，E），用rand_seed()函数使得每一次程序运行时随机生成的有向图都不同。

步骤2： 令S=0，V_S=V-v_0。

步骤3： 将与v_0相连接的点v_i的值c赋值给L(v_i),其余将∞赋值给L(v_i)。

步骤4： 从V_S中选出u使得L(u)是最小的，将u从V_S删除，S=S∪{u}。

步骤5： 对于V_S中的所有点w使得L(w)=min(L(w),L(u)+c(u,w))，返回步骤4.

代码：

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
116
#include<iostream>
#include<time.h>
#include<Windows.h> 
#define maxn 1024
using namespace std;
long long n,matrix[maxn][maxn];
long long L[maxn],S[maxn],V_S[maxn];
//int s=0;
void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}
class init
{
	public:
	void create()
	{
		cout<<"输入n:";
		cin>>n;
		//全部赋值为零
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		matrix[i][j]=maxn;
		//初始化邻接矩阵
		for(int i=0;i<n;i++)
		{
			if(i==0)
			{
				matrix[i][1]=rand()%n;
				matrix[i][2]=rand()%n;
			}
			else
			for(int j=i+1;j<n;j++)
			matrix[i][j]=rand()%n; 
		}
	}
};
void print()//打印图 
{
	cout<<n<<"*"<<n<<"阶的邻接矩阵："<<endl; 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		if(matrix[i][j]==maxn)
		cout<<"m"<<" ";
		else
		cout<<matrix[i][j]<<" ";	
		cout<<endl;	
	
	}	
}
void look_min(int l)
{
	//从V-S中选择u使得L[u]最小
	int minx=L[V_S[0]];
    for(int i=0;i<l;i++)
    {
    	if(L[V_S[i]]<minx) minx=L[V_S[i]];
	}
	//V-S和S中的值变化 
	int u=0;
    for(int i=0;i<l;i++)
    {
    	if(L[V_S[i]]==minx)
    	{
    		//将u从V_S中删去
    		u=V_S[i];
    		S[n-l-1]=i; 
			for(int k=i;k<l-1;k++)
			V_S[k]=V_S[k+1];
			l--;
			break; 
		}
	}
	//对于V_S中的所有点w使得L(w)=min(L(w),L(u)+c(u,w))
	for(int k=0;k<l;k++)
	{
		L[V_S[k]]=min(L[V_S[k]],L[u]+matrix[u][V_S[k]]);
	}   
}

int main()
{
	double start = GetTickCount();//计算时间 
	//数据初始化 
	init M;
	rand_seed();
	M.create();
	//令V_S=V-v0。
	for(int i=1;i<n;i++)
	{
		V_S[i-1]=i;
	}
	//将与v_0相连接的点v_i的值c赋值给L(v_i),其余将∞赋值给L(v_i)。
	for(int i=1;i<n;i++)
	{
		if(matrix[0][i]!=maxn)
		   L[i]=matrix[0][i];
		else
		   L[i]=maxn;
	} 
	for(int i=0;i<n;i++)
	{
		look_min(n-i-1);		 
	}
	double stop = GetTickCount();
	//输出 
	print();
	cout<<endl;
	cout<<"最短路径："<<endl; 
	for(int i=1;i<n;i++)
	cout<<"从顶点v0出发到V"<<i<<"的最短路径为： "<<L[i]<<endl;
	cout<<endl<<"程序运行所需时间："<<stop-start<<" ms"; 
    return 0;
}

结果：

其他的：

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
/*
测试用立
4
1 2 3
4 5 6
2 1 3
5 1 3 
*/
#include<iostream>
#include<cmath>
#include<algorithm>
#define maxn 10000
#define m 10000
using namespace std;
int n;
double array[maxn][maxn];
double L[m]={0};
int V[m]={0},S[m]={0};
double cost(int x1,int y1,int h1,int x2,int y2,int h2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+(h1-h2)*(h1-h2);
}
void prin()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(array[i][j]!=m) 
			cout<<array[i][j]<<" ";
			else
			cout<<"m ";
		} 
		
		cout<<endl;
	}
}
void Dijkstra()
{
	//初始化v，s,l
	S[0]=0;
	for(int i=0;i<n-1;i++)
	V[i]=i+1;
	L[0]=m;
	for(int i=1;i<n;i++)
	{
		if(array[0][i]!=m)
		L[i]=array[0][i];
		else
		L[i]=m;
	} 
	//关键代码 
	for(int i=1;i<n;i++)
	{
		int len=n-i,u=0;//len为V的长度 
		//找L[V]最小的一个数 
		double minx=L[V[0]];
		for(int k=1;k<len;k++)
		{
			if(minx>L[V[k]]) minx=L[V[k]];
		}
		//记录最小值的下标u，传值给s，将u从V中删除
		for(int k=0;k<len;k++)
		{
			if(minx==L[V[k]])
			{
				u=V[k];
				S[i]=u;
				for(int j=k;j<len-1;j++)
				V[j]=V[j+1];
				break;
			}
	    }
		//更新剩下点即V中的值
		//关键代码  
		for(int k=0;k<len-1;k++) 
		L[V[k]]=min(L[V[k]],L[u]+array[u][V[k]]);
	}
}
int main()
{
	cin>>n;
	int x[n],y[n],h[n];
	for(int i=0;i<n;i++)
	cin>>x[i]>>y[i]>>h[i];
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(j>i)
			{
			   array[i][j]=cost(x[i],y[i],h[i],x[j],y[j],h[j]);	
			}
			else
			array[i][j]=m;
		}
	}  
	prin();
    Dijkstra();
    for(int i=1;i<n;i++)
    cout<<"v0到"<<"v"<<i<<"的单源最短路径为： "<<L[i]<<endl;
	return 0;
}

最终版：

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
116
117
118
119
120
121
122
123
124
125
#include<iostream>
#include<time.h>
#include<Windows.h> 
#define maxn 5000
using namespace std;
long long n,matrix[maxn][maxn];
long long L[maxn],S[maxn],V_S[maxn];
//int s=0;
void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}
class init
{
	public:
	void create(int n)
	{

		//全部赋值为零
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		matrix[i][j]=maxn;
		//初始化邻接矩阵
		for(int i=0;i<n;i++)
		{
			if(i==0)
			{
				matrix[i][1]=rand()%n;
				matrix[i][2]=rand()%n;
			}
			else
			for(int j=i+1;j<n;j++)
			matrix[i][j]=rand()%n; 
		}
	}
};
void print()//打印图 
{
	cout<<n<<"*"<<n<<"阶的邻接矩阵："<<endl; 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		if(matrix[i][j]==maxn)
		cout<<"m"<<" ";
		else
		cout<<matrix[i][j]<<" ";	
		cout<<endl;	
	
	}	
}
void look_min(int l)
{
	//从V-S中选择u使得L[u]最小
	int minx=L[V_S[0]];
    for(int i=0;i<l;i++)
    {
    	if(L[V_S[i]]<minx) minx=L[V_S[i]];
	}
	//V-S和S中的值变化 
	int u=0;
    for(int i=0;i<l;i++)
    {
    	if(L[V_S[i]]==minx)
    	{
    		//将u从V_S中删去
    		u=V_S[i];
    		S[n-l-1]=i; 
			for(int k=i;k<l-1;k++)
			V_S[k]=V_S[k+1];
			l--;
			break; 
		}
	}
	//对于V_S中的所有点w使得L(w)=min(L(w),L(u)+c(u,w))
	for(int k=0;k<l;k++)
	{
		L[V_S[k]]=min(L[V_S[k]],L[u]+matrix[u][V_S[k]]);
	}   
}

int main()
{

	//数据初始化 
	cout<<"输入n:";
	cin>>n;
	init M;
	rand_seed();
	M.create(n);
	//令V_S=V-v0。
    LARGE_INTEGER nFreq;	
	LARGE_INTEGER nBeginTime;	
	LARGE_INTEGER nEndTime;	
	QueryPerformanceFrequency(&nFreq);        
	QueryPerformanceCounter(&nBeginTime);//开始计时

	for(int i=1;i<n;i++)
	{
		V_S[i-1]=i;
	}
	//将与v_0相连接的点v_i的值c赋值给L(v_i),其余将∞赋值给L(v_i)。
	for(int i=1;i<n;i++)
	{
		if(matrix[0][i]!=maxn)
		   L[i]=matrix[0][i];
		else
		   L[i]=maxn;
	} 
	for(int i=0;i<n;i++)
	{
		look_min(n-i-1);		 
	}
	QueryPerformanceCounter(&nEndTime);//停止计时
//输出 
	print();
	cout<<endl;
	cout<<"最短路径："<<endl; 
	for(int i=1;i<n;i++)
	cout<<"从顶点v0出发到V"<<i<<"的最短路径为： "<<L[i]<<endl;
    double time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s 
	cout<<"程序运行所需时间：";
	cout<<time*1000<<" ms"<<endl;
    return 0;
}