Добрый день. Есть код, все вполне прилично. Но минимальное остовное дерево находит неправильно, стоимость, соответсвенно, тоже неправильно считает (правильный ответ cost = 6). 7 вершин, 21 ребро
| C# |
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
| namespace GraphMethods
{
using System;
using System.Collections.Generic;
using System.Linq;
///
/// Class represents graph edge.
///
public class Edge
{
public int U;
public int V;
public double Weight;
}
///
/// Implementation of Kruskal algorithm.
///
public class Kruskal
{
private const int MAX = 100;
private int _edgesCount;
private int _verticlesCount;
private List _edges;
private int[,] tree;
private int[] sets;
public List Edges { get { return _edges; } }
public int VerticlesCount { get { return _verticlesCount; } }
public double Cost { get; private set; }
public Kruskal(string input)
{
tree = new int[MAX, 3];
sets = new int[MAX];
string[] lines = input.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
_verticlesCount = int.Parse(lines[0]);
_edgesCount = int.Parse(lines[1]);
_edges = new List();
_edges.Add(null);
for (int i = 2; i < lines.Count(); i++)
{
string[] line = lines[i].Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
_edges.Add(new Edge
{
U = int.Parse(line[0]),
V = int.Parse(line[1]),
Weight = double.Parse(line[2])
});
}
for (int i = 1; i <= _verticlesCount; i++) sets[i] = i;
}
private void ArrangeEdges(int k)
{
Edge temp;
for (int i = 1; i < k; i++)
{
for (int j = 1; j <= k - i; j++)
{
if (_edges[j].Weight > _edges[j + 1].Weight)
{
temp = _edges[j];
_edges[j] = _edges[j + 1];
_edges[j + 1] = temp;
}
}
}
}
private int Find(int vertex)
{
return (sets[vertex]);
}
private void Join(int v1, int v2)
{
if (v1 < v2)
sets[v2] = v1;
else
sets[v1] = v2;
}
public void BuildSpanningTree()
{
int k = _verticlesCount;
int i, t = 1;
this.ArrangeEdges(k);
this.Cost = 0;
for (i = 1; i <= k; i++)
{
for (i = 1; i < k; i++)
if (this.Find(_edges[i].U) != this.Find(_edges[i].V))
{
tree[t, 1] = _edges[i].U;
tree[t, 2] = _edges[i].V;
this.Cost += _edges[i].Weight;
this.Join(_edges[t].U, _edges[t].V);
t++;
}
}
}
public void DisplayInfo()
{
Console.WriteLine("The Edges of the Minimum Spanning Tree are:");
for (int i = 1; i < _verticlesCount; i++)
Console.WriteLine(tree[i,1] + " - " + tree[i,2]);
}
}
}
public class Program
{
static void Main(string[] args)
{
Kruskal k = new Kruskal(@"7
21
1 2 3
2 3 5
3 4 7
4 5 3
5 6 1
6 7 1
7 1 6
1 3 1
1 4 5
1 5 7
1 6 5
2 4 3
2 5 1
2 6 2
2 7 6
3 5 9
3 6 1
3 7 2
4 6 3
4 7 9
5 7 5");
k.BuildSpanningTree();
Console.WriteLine("Cost: " + k.Cost);
k.DisplayInfo();
Console.WriteLine("Press any key...");
Console.ReadKey();
}
} |
|
(
Сообщение от TopLayer
