课程设计内容与要求

​ 用字符文件提供数据建立连通带权无向网络邻接矩阵存储结构.编写程序, 求所有不同构的最小生成树.要求输出每棵最小生成树的各条边（用顶点无序偶 表示）、最小生成树所有边上的权值之和；输出所有不同构的生成树的数目.

总体设计

​ 该实验算法部分采用 dfs 与 prim 算法的结合,并且运用到了组合数的求解, 以及 dfs 的变型.首先,通过 prim 算法求的一个无向图的一个最小生成树的权值 和 ans,其次,假设无向连通图中有 m 条边以及 n 个结点,则最小生成树应当由 n1 条边组成.问题就转换为从 m 条边取 n-1 条边,对于该种方法,可以采用 dfs 搜 索的方式来解决.我们易知从 m 条边取 n-1 条边,所有的可能为组合数𝐶𝑚 𝑛−1,但是 这么多情况中我们仍要排除一种情况,即在所有取出来的边中必须要满足两种情 况,1.必须保证这些边涵盖的无向图中所有的结点.2.必须保证这些边是连通的. 对于这两种情况的判断我们采取如下措施：1.利用 use[]数组保存结点的使用情 况,即要在取出 n-1 条边的同时要把这些边对应的两个结点存进 use[]数组中,相 应位置的下标为 1 时说明包含该结点,为 0 说明不包含该结点.2.我们采取 dfs 的 方式来判断我们选出来的这些边是连通的,我们首先引进一个变量名为 first_Node,然后我们通过遍历 vis 函数来找到第一个 vis[first_Node]=1 的数, 把 first_Node 当作我们 dfs 的起始点,通过 dfs 的遍历,遍历结束后再次判断是 否所有的结点都被成功遍历,如果是,我们返回1则说明我们成功找到了一个最小 生成树,如果不是,直接跳过这种情况,然后遍历其他的情况.在每次成功找到最 小生成树的时候我们就输出.然后继续dfs 找到下一棵最小生成树.当所有最小的 生成树全部找到,程序结束.

具体代码

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
1.	#define _CRT_SECURE_NO_WARNINGS
2.	#include<stdio.h>
3.	#include<stdlib.h>
4.	#include<string.h>
5.	#include<limits.h>
6.	#include<stdbool.h>
7.	#define MAX INT_MAX
8.	#define N 200
9.	struct CD_TP
10.	{
11.	 double lowcost;
12.	 int vex;
13.	};
14.	struct Graph
15.	{
16.	 double** weight;
17.	 int vex;
18.	 int edge;
19.	};
20.	struct Edge
21.	{
22.	 int i;
23.	 int j;
24.	 double weight;
25.	};
26.	struct Visited
27.	{
28.	 bool visited[N];
29.	};
30.	struct Graph* Crt(struct Graph* G, FILE* fp, int* vex, int* edge, struct Edge** E);
31.	void Prim(struct Graph* G, double* sum_weight);//求一棵最小生成树
32.	void Print_Matrix(double** weight, int m);//打印邻接矩阵
33.	void dfs(int x, int sum, struct Graph* G);
34.	int DFS_tree(struct Graph* G, struct Edge* E,int i);
35.	int Judge_tree(struct Graph*G,struct Edge* E, int i, int j);
36.	int Next_Adj(struct Graph* G, struct Edge* E, int u, int v);
37.	int First_Adj(struct Graph* G, struct Edge* E, int u);
38.	int vis[N],ans,visited[N];
39.	int main(void)
40.	{
41.	 int vex, edge;//保存顶点个数,边的个数
42.	 int i = 0;//循环控制变量
43.	 int L = 0;//记录树的棵树
44.	 double sum_weight = 0;//保存一条树上的权值和
45.	 struct Graph* G = NULL;
46.	 struct Visited V;
47.	 struct Edge* E = NULL;//保存边是否被使用过
48.	 while (i < N)
49.	 {
50.	  V.visited[i++] = false;//初始化,全部赋值为false
51.	 }
52.	 FILE* fp = fopen("design.txt", "r");
53.	 if (NULL == fp)
54.	  exit(0);
55.	 G = Crt(G, fp, &vex, &edge, &E);
56.	 printf("邻接矩阵建立完成\n");
57.	 Print_Matrix(G->weight, G->vex);
58.	 Prim(G, &sum_weight);
59.	 printf("其中一条最小生成树的权值和为:%lf\n", sum_weight);
60.	 //ListAlltree(G, V, 0, sum_weight, E, 0, &L);
61.	 //Free(G);
62.	 dfs(0, 0, G,E,sum_weight);
63.	 system("pause>0");
64.	 return 0;
65.	}
66.	struct Graph* Crt(struct Graph* G, FILE* fp, int* vex, int* edge, struct Edge** E)
67.	{
68.	 int m, n;//m存结点个数,n存边的个数
69.	 int i, j;//循环控制变量和顶点个数
70.	 int l = 0;//自计数变量
71.	 double Element;//代表矩阵元素个数
72.	 fscanf(fp, "%d %d", &m, &n);
73.	 //邻接矩阵的建立
74.	 G = (struct Graph*)malloc(sizeof(struct Graph));
75.	 *E = (struct Edge*)malloc(sizeof(struct Edge) * n);//建立边的结构体数组
76.	 if (NULL == G)
77.	  return NULL;
78.	 G->weight = (double**)malloc(sizeof(double*) * m);//行指针分配
79.	 if (NULL == G->weight)return NULL;
80.	 for (i = 0; i < m; i++)
81.	 {
82.	  G->weight[i] = (double*)malloc(sizeof(double) * m);//每一行分配内存
83.	  if (NULL == G->weight[i]) {
84.	   printf("内存分配失败");
85.	   return NULL;
86.	  }
87.	 }
88.	 //邻接矩阵的初始化
89.	 for (i = 0; i < m; i++)
90.	 {
91.	  for (j = 0; j < m; j++)
92.	  {
93.	   if (i == j)
94.	    G->weight[i][j] = 0;
95.	   else
96.	    G->weight[i][j] = MAX;
97.	  }
98.	 }
99.	 while (!feof(fp))
100.	 {
101.	  fscanf(fp, "%d %d %lf", &i, &j, &Element);
102.	  G->weight[i][j] = Element;//邻接矩阵的对称性
103.	  G->weight[j][i] = Element;
104.	  (*E)[l].i = i;//对边进行记录
105.	  (*E)[l].j = j;
106.	  (*E)[l++].weight = Element;
107.	
108.	 }
109.	 G->vex = m;
110.	 G->edge = n;
111.	 return G;
112.	}
113.	void Print_Matrix(double** weight, int m)
114.	{
115.	 for (int i = 0; i < m; i++)
116.	 {
117.	  for (int j = 0; j < m; j++)
118.	  {
119.	   if (weight[i][j] == MAX)
120.	   {
121.	    printf("∞\t");
122.	   }
123.	   else
124.	    printf("%.1lf\t", weight[i][j]);
125.	  }
126.	  printf("\n");
127.	 }
128.	}
129.	void Prim(struct Graph* G, double* sum_weight)
130.	{
131.	 int i, m, j;
132.	 struct CD_TP* closedge = (struct CD_TP*)malloc(sizeof(struct CD_TP) * G->vex);
133.	 if (NULL == closedge)return;
134.	 for (i = 0; i < G->vex; i++)//默认从0号结点开始
135.	 {
136.	  closedge[i].vex = 0;
137.	  closedge[i].lowcost = G->weight[i][0];
138.	 }
139.	 for (m = 0; m < G->vex - 1; m++)
140.	 {
141.	  for (i = 0; i < G->vex; i++)
142.	  {
143.	   if (closedge[i].lowcost > 0)
144.	    break;
145.	  }
146.	  for (j = i + 1; j < G->vex; j++)//选择排序的思想
147.	  {
148.	   if (closedge[j].lowcost > 0 && closedge[j].lowcost < closedge[i].lowcost)
149.	    i = j;
150.	  }
151.	  closedge[i].lowcost = 0;
152.	  for (j = 0; j < G->vex; j++)
153.	  {
154.	   if (closedge[j].lowcost > 0 && closedge[j].lowcost > G->weight[j][i])
155.	   {
156.	    closedge[j].lowcost = G->weight[j][i];
157.	    closedge[j].vex = i;
158.	   }
159.	  }
160.	 }
161.	 for (i = 1; i < G->vex; i++)
162.	 {
163.	  (*sum_weight) += G->weight[i][closedge[i].vex];
164.	 }
165.	
166.	 free(closedge);
167.	}
168.	void dfs(int x, int sum,struct Graph*G,struct Edge*E,double sum_prime) {
169.	 double sum_weight = 0;
170.	 int flag = 0,first_Node;
171.	 if (x > G->edge) return; // 不是 x>=n！！！ // 因为x=n说明轮到了选或不选第n个数,但是没判断此时sum的值  // 还有一种办法是将该语句放在if(sum == m)判断后
172.	 int* use = (int*)malloc(sizeof(int) * G->vex);
173.	 if (use == NULL)return;
174.	 memset(use, 0, sizeof(int)*G->vex);
175.	 if (sum == G->vex-1) {
176.	  for (int i = 0; i < G->edge; i++) {
177.	   if (vis[i])
178.	   {
179.	    sum_weight = sum_weight + E[i].weight;
180.	    use[E[i].i] = 1;
181.	    use[E[i].j] = 1;
182.	   }
183.	  }
184.	  if (sum_weight == sum_prime)
185.	  {
186.	   for (int i = 0; i < G->vex; i++)
187.	   {
188.	    if (use[i] == 0)
189.	    {
190.	     flag = 1;
191.	     break;
192.	    }
193.	   }
194.	   if (flag)return;
195.	   for (int i = 0; i < G->vex; i++)//找到第一条遍历的边的点
196.	   {
197.	    if (vis[i]) {
198.	     first_Node = E[i].i;
199.	     break;
200.	    }
201.	   }
202.	   memset(visited, 0, sizeof(visited));
203.	  
204.	   if (DFS_tree(G, E, first_Node)) {
205.	    ans++;
206.	    printf("第%d棵数", ans);
207.	    for (int i = 0; i < G->edge; i++)
208.	    {
209.	     if (vis[i])
210.	      printf("(%d,%d)", E[i].i, E[i].j);
211.	    }
212.	    printf("最小生成树权重和=%lf", sum_weight);
213.	    printf("\n");
214.	   }
215.	  }
216.	  return;
217.	 }
218.	 vis[x] = 1;
219.	 dfs(x + 1, sum + 1,G,E,sum_prime);
220.	 vis[x] = 0;
221.	 dfs(x + 1, sum,G,E,sum_prime);
222.	 free(use);
223.	}
224.	int DFS_tree(struct Graph* G, struct Edge* E,int i)
225.	{
226.	 int j,k;
227.	 visited[i] = 1;
228.	 for (j = First_Adj(G,E,i); j != -1; j = Next_Adj(G,E, i,j))
229.	 {
230.	  if (!visited[j])
231.	   DFS_tree(G, E, j);
232.	 }
233.	 for (k = 0; k < G->vex; k++)
234.	 {
235.	  if (!visited[k])
236.	   return 0;
237.	 }
238.	 return 1;
239.	}
240.	int First_Adj(struct Graph* G, struct Edge*E,int u)
241.	{
242.	 int v;
243.	 for (v = 0; v < G->vex; v++)
244.	 {
245.	  if (G->weight[u][v] != 0 && G->weight[u][v] != MAX && Judge_tree(G,E, u, v))
246.	   break;
247.	 }
248.	 if (v < G->vex)return v;
249.	 return -1;
250.	}
251.	int Judge_tree(struct Graph*G,struct Edge* E, int i, int j)
252.	{
253.	 for (int k = 0; k < G->edge; k++)
254.	 {
255.	  if (vis[k]) {
256.	   if ((E[k].i == i && E[k].j == j) || (E[k].i == j && E[k].j == i))
257.	   {
258.	    return 1;
259.	   }
260.	  }
261.	 }
262.	 return 0;
263.	}
264.	int Next_Adj(struct Graph* G, struct Edge* E, int u,int v)
265.	{
266.	
267.	 for (++v; v < G->vex; v++)
268.	 {
269.	  if (G->weight[u][v] != 0 && G->weight[u][v] != MAX && Judge_tree(G, E, u, v))
270.	   break;
271.	  
272.	 }
273.	 if (v < G->vex)
274.	  return v;
275.	 return -1;
276.	}


实验结果

样例1

输入

image-20230226122932095image-20230226122937579

程序输出:

image-20230226125307957

样例2

输入

image-20230226123042631image-20230226123046044

程序输出

image-20230226123105250

样例3

程序输入

image-20230226123142550image-20230226123146846

程序输出

image-20230226123546888

结语

这次的数据结构实验考察的难度不大，了解dfs便可以很快的求解。