1 View Code
2
3 int prime(
int cur)
4 {
5 int index;
6 int sum =
0;
7 memset(visit,
false,
sizeof(visit));
8 visit[cur] =
true;
9 for(
int i =
0; i < m; i ++
){
10 dist[i] =
graph[cur][i];
11 }
12
13 for(
int i =
1; i < m; i ++
){
14
15 int mincost =
INF;
16 for(
int j =
0; j < m; j ++
){
17 if(!visit[j] && dist[j] <
mincost){
18 mincost =
dist[j];
19 index =
j;
20 }
21 }
22
23 visit[index] =
true;
24 sum +=
mincost;
25
26 for(
int j =
0; j < m; j ++
){
27 if(!visit[j] && dist[j] >
graph[index][j]){
28 dist[j] =
graph[index][j];
29 }
30 }
31 }
32 return sum;
33 }
View Code
1 View Code
2
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6
7 const int size =
128;
8 int n;
9 int father[size];
10 int rank[size];
11
12 //把每条边成为一个结构体，包括起点、终点和权值
13 typedef
struct node
14 {
15 int val;
16 int start;
17 int end;
18 }edge[SIZE * SIZE /
2];
19
20 //把每个元素初始化为一个集合
21 void make_set()
22 {
23 for(
int i =
0; i < n; i ++
){
24 father[i] =
i;
25 rank[i] =
1;
26 }
27 return ;
28 }
29
30 //查找一个元素所在的集合,即找到祖先
31 int find_set(
int x)
32 {
33 if(x !=
father[x]){
34 father[x] =
find_set(father[x]);
35 }
36 return father[x];
37 }
38
39 //合并x,y所在的两个集合：利用Find_Set找到其中两个
40 //集合的祖先，将一个集合的祖先指向另一个集合的祖先。
41 void Union(
int x,
int y)
42 {
43 x =
find_set(x);
44 y =
find_set(y);
45 if(x ==
y){
46 return ;
47 }
48 if(rank[x] <
rank[y]){
49 father[x] =
find_set(y);
50 }
51 else{
52 if(rank[x] ==
rank[y]){
53 rank[x] ++
;
54 }
55 father[y] =
find_set(x);
56 }
57 return ;
58 }
59
60 bool cmp(pnode a, pnode b)
61 {
62 return a.val <
b.val;
63 }
64
65 int kruskal(
int n)
//n为边的数量
66 {
67 int sum =
0;
68 make_set();
69 for(
int i =
0; i < n; i ++){
//从权最小的边开始加进图中
70 if(find_set(edge[i].start) !=
find_set(edge[i].end)){
71 Union(edge[i].start, edge[i].end);
72 sum +=
edge[i].val;
73 }
74 }
75 return sum;
76 }
77
78 int main()
79 {
80 while(
1){
81 scanf(
"%d", &
n);
82 if(n ==
0){
83 break;
84 }
85 char x, y;
86 int m, weight;
87 int cnt =
0;
88 for(
int i =
0; i < n -
1; i ++
){
89 cin >> x >>
m;
90 //scanf("%c %d", &x, &m);
91 //printf("%c %d ", x, m);
92 for(
int j =
0; j < m; j ++
){
93 cin >> y >>
weight;
94 //scanf("%c %d", &y, &weight);
95 //printf("%c %d ", y, weight);
96 edge[cnt].start = x -
'A';
97 edge[cnt].end = y -
'A';
98 edge[cnt].val =
weight;
99 cnt ++
;
100 }
101 }
102
103 sort(edge, edge + cnt, cmp);
//对边按权从小到大排序
104 cout << kruskal(cnt) <<
endl;
105 }
106 }
View Code
1 View Code
2
3 void floyd()
4 {
5 for(
int k =
0; k < n; k ++){
//作为循环中间点的k必须放在最外一层循环
6 for(
int i =
0; i < n; i ++
){
7 for(
int j =
0; j < n; j ++
){
8 if(dist[i][j] > dist[i][k] +
dist[k][j]){
9 dist[i][j] = dist[i][k] + dist[k][j];
//dist[i][j]得出的是i到j的最短路径
10 }
11 }
12 }
13 }
14 }
View Code
1 View Code
2
3 void dijkstra(
int s)
//s是起点
4 {
5 memset(visit,
false,
sizeof(visit));
6 visit[s] =
true;
7 for(
int i =
0; i < n; i ++
){
8 dist[i] =
graph[s][i];
9 }
10
11 int index;
12 for(
int i =
1; i < n; i ++
){
13 int mincost =
INF;
14 for(
int j =
0; j < n; j ++
){
15 if(!visit[j] && dist[j] <
mincost){
16 mincost =
dist[j];
17 index =
j;
18 }
19 }
20 visit[index] =
true;
21 for(
int j =
0; j < n; j ++
){
22 if(!visit[j] && dist[j] > dist[index] +
graph[index][j]){
23 dist[j] = dist[index] +
graph[index][j];
24 }
25 }
26 }
27 }
View Code
转载于:https://www.cnblogs.com/LK1994/p/3149040.html
