1. using System;
2. using System.Collections.Generic;
3. using System.Windows.Forms;
4.  
5. namespace Cwiczenia13_12_23
6. {
7.     public partial class Form1 : Form
8.     {
9.         public Form1()
10.         {
11.             InitializeComponent();
12.         }
13.  
14.         private void button1_Click(object sender, EventArgs e)
15.         {
16.             Wezel4 wezel1 = new Wezel4(1);
17.             Wezel4 wezel2 = new Wezel4(2);
18.             Wezel4 wezel3 = new Wezel4(3);
19.  
20.             Krawedz krawedz1 = new Krawedz(wezel1, wezel2, 10);
21.             Krawedz krawedz2 = new Krawedz(wezel2, wezel3, 20);
22.  
23.             Graf graf = new Graf(krawedz1);
24.             graf.addANewPoint(wezel3);
25.  
26.             Graf minimumSpanningTree = graf.KruskalAlgorithm();
27.  
28.             // Wyświetlenie wynikowego minimalnego drzewa rozpinającego
29.             foreach (Krawedz krawedz in minimumSpanningTree.krawedzie)
30.             {
31.                 Console.WriteLine($"Start: {krawedz.poczatek.wartosc}, Koniec: {krawedz.koniec.wartosc}, Waga: {krawedz.waga}");
32.             }
33.         }
34.     }
35.  
36.     class Krawedz
37.     {
38.         public int waga;
39.         public Wezel4 poczatek;
40.         public Wezel4 koniec;
41.  
42.         public Krawedz(Wezel4 firstPoint, Wezel4 secondPoint, int waga)
43.         {
44.             this.poczatek = firstPoint;
45.             this.koniec = secondPoint;
46.             this.waga = waga;
47.         }
48.     }
49.  
50.     class Wezel4
51.     {
52.         public int wartosc;
53.  
54.         public Wezel4(int wartosc)
55.         {
56.             this.wartosc = wartosc;
57.         }
58.     }
59.  
60.     class Graf
61.     {
62.         public List<Krawedz> krawedzie;
63.         public List<Wezel4> wierzcholki;
64.  
65.         public Graf(Krawedz firstLink)
66.         {
67.             wierzcholki = new List<Wezel4>();
68.             krawedzie = new List<Krawedz>();
69.             this.wierzcholki.Add(firstLink.poczatek);
70.             this.wierzcholki.Add(firstLink.koniec);
71.             this.krawedzie.Add(firstLink);
72.         }
73.  
74.         /// <summary>
75.         /// The nuclear option, create a new graph straight away with the provided lists
76.         /// </summary>
77.         /// <param name="krawedzie"></param>
78.         /// <param name="wierzcholki"></param>
79.         public Graf(List<Krawedz> krawedzie, List<Wezel4> wierzcholki)
80.         {
81.             this.wierzcholki = new List<Wezel4>();
82.             this.krawedzie = new List<Krawedz>();
83.             this.krawedzie = krawedzie;
84.             this.wierzcholki = wierzcholki;
85.         }
86.  
87.         public int newGraphsNeeded(Krawedz krawedz)
88.         {
89.             int newGraphCount = 0;
90.             if (!wierzcholki.Contains(krawedz.poczatek))
91.                 newGraphCount++;
92.             if (!wierzcholki.Contains(krawedz.koniec))
93.                 newGraphCount++;
94.  
95.             return newGraphCount;
96.         }
97.  
98.         public Graf KruskalAlgorithm()
99.         {
100.             var krawedzie = this.krawedzie.OrderBy(k => k.waga);
101.             List<Graf> listaGrafow = new List<Graf>();
102.  
103.             foreach (var krawedz in krawedzie)
104.             {
105.                 if (listaGrafow.Count == 0)
106.                 {
107.                     listaGrafow.Add(new Graf(krawedz));
108.                     continue;
109.                 }
110.  
111.                 Graf graph1 = null;  // graf, do którego należy początek krawędzi
112.                 Graf graph2 = null;  // graf, do którego należy koniec krawędzi
113.  
114.                 // Sprawdzanie, do których grafów należą węzły początkowe i końcowe krawędzi
115.                 foreach (var graph in listaGrafow)
116.                 {
117.                     if (graph.wierzcholki.Contains(krawedz.poczatek))
118.                     {
119.                         if (graph1 == null)
120.                             graph1 = graph;
121.                         else
122.                             graph2 = graph;
123.                     }
124.  
125.                     if (graph.wierzcholki.Contains(krawedz.koniec))
126.                     {
127.                         if (graph1 == null)
128.                             graph1 = graph;
129.                         else
130.                             graph2 = graph;
131.                     }
132.                 }
133.  
134.                 if (graph1 != graph2)  // jeżeli wierzchołki należą do różnych grafów
135.                 {
136.                     // Dodawanie krawędzi do grafu
137.                     graph1.krawedzie.Add(krawedz);
138.  
139.                     // Łączenie grafów
140.                     graph1.mergeGraph(graph2);
141.                     listaGrafow.Remove(graph2);
142.                 }
143.             }
144.  
145.             // Zwracanie grafu z minimalnym drzewem rozpinającym
146.             return listaGrafow[0];
147.         }
148.  
149.         public void mergeGraph(Graf otherGraph)
150.         {
151.             foreach (Krawedz krawedz in otherGraph.krawedzie)
152.             {
153.                 this.krawedzie.Add(krawedz);
154.             }
155.  
156.             foreach (Wezel4 wierzcholek in otherGraph.wierzcholki)
157.             {
158.                 this.wierzcholki.Add(wierzcholek);
159.             }
160.         }
161.  
162.         public void addANewPoint(Wezel4 pointToAdd)
163.         {
164.             if (!wierzcholki.Contains(pointToAdd))
165.             {
166.                 wierzcholki.Add(pointToAdd);
167.             }
168.         }
169.     }
170. }