sing System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// Zaimplementuj algorytm Prima zgodnie z opisem podanym na wykładzie.

namespace Zadanie5
{
    // implementacja grafu jako macierzy sąsiedztwa
    // klasa implementuje algorytm Prima
    class Prim
    {
        int[,] graphTable;
        public Prim(int[,] graphTable)
        {
            this.graphTable = graphTable;
        }

        // zwraca liczbę wierzchołków
        public int getN()
        {
            return graphTable.GetLength(0);
        }

        //właściwy algorytm
        public List<int> MinSpanningTree()
        {
            int n = getN();
            // jeśli true, wierzchołek odpowiadający danemu indeksowi został już umieszczony
            // w drzewie
            bool[] mstSet = new bool[n];
            int[] wages = new int[n];
            // potrzebny do wygenerowania początkowego wierzchołka
            Random generator = new Random();
            // lista wierzchołków w kolejności dodawania ich do drzewa
            List<int> result = new List<int>();

            int firstVertex = generator.Next(n);
            for (int i = 0; i < n; i++)
            {
                wages[i] = int.MaxValue;
            }
            wages[firstVertex] = 0;

            for (int i = 0; i < n - 1; i++)
            {
                int min = int.MaxValue;
                int minIndex = -1;
                // pętla znajduje wierzchołek, którego odległość(waga) od drzewa jest najmniejsza
                for (int j = 0; j < n; j++)
                {
                    if (mstSet[j] == false && wages[j] < min)
                    {
                        min = wages[j];
                        minIndex = j;
                    }
                }
                // umieść wierzchołek w drzewie
                mstSet[minIndex] = true;
                // i dodaj do listy rezultatów
                result.Add(minIndex);
                // aktualizacja tablicy wag
                for (int j = 0; j < n; j++)
                {
                    if (graphTable[minIndex, j] != 0 && mstSet[j] == false && graphTable[minIndex, j] < wages[j])
                        wages[j] = graphTable[minIndex, j];
                }
            }
            return result;
        }
    }
}


///////////////////////  DIJKSTRA
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// Zaimplementuj algorytm Dijkstry zgodnie z pseudokodem podanym na wykładzie.

namespace Zadanie3
{
    // implementacja grafu jako macierzy sąsiedztwa
    class Graph
    {
        int[,] graphTable;
        public Graph(int[,] table)
        {
            graphTable = table;
        }

        // zwraca liczbę wierzchołków
        public int getN()
        {
            return graphTable.GetLength(0);
        }

        // Algorytm Dijkstry
        // source jest wierzchołkiem odniesienia
        public void Dijkstra(int source)
        {
            int n = getN();
            int[] wages = new int[n];
            bool[] sptSet = new bool[n];
            // sptSet = true, wtedy gdy dla odpowiadającemu mu wierzchołkowi zostały już obliczone wagi najkrótszych ścieżek
            // najpierw wypełnij tablicę wartościami maksymalnymi:
            for (int i = 0; i < wages.Length; i++)
            {
                wages[i] = int.MaxValue;
            }
            // odległość wierzchołka source od jego samego równa się 0
            wages[source] = 0;
            int min = int.MaxValue;
            for (int k = 0; k < n - 1; k++)
            {
                // szukanie wartości min spośród nieznaczonych wartością true wag oraz indeksu tej wartości
                min = int.MaxValue;
                int minIndex = -1;
                for (int i = 0; i < wages.Length; i++)
                {
                    if (!sptSet[i] && wages[i] < min)
                    {
                        min = wages[i];
                        minIndex = i;
                    }
                }
                sptSet[minIndex] = true;
                // dla tego wierzchołka oblicz wagi, jeśli nie zostały jeszcze obliczone (pierwszy warunek), jeśli nie ma połączenia z
                // danym wierzchołkiem (drugi warunek) i jeśli suma min i odległości wierzchołków minIndex oraz 'i' od siebie jest mniejsza
                // od wartości już się znajdującej w tablicy
                for (int i = 0; i < wages.Length; i++)
                {
                    if (!sptSet[i] && graphTable[minIndex, i] != 0 && min + graphTable[minIndex, i] < wages[i])
                    {
                        wages[i] = min + graphTable[minIndex, i];
                    }
                }
            }
            Console.WriteLine("Wierzchołek\tOdległość");
            for (int i = 0; i < wages.Length; i++)
            {
                Console.WriteLine(i + "\t" + wages[i]);
            }
        }
    }
}

/////// prim dla najwiekszych

  public List<int> MaxSpanningTree()
            {
                int n = graphTable.GetLength(0);
                Random generator = new Random();
                bool[] mstSet = new bool[n];
                int[] wages = new int[n];
                List<int> result = new List<int>();

                for (int i = 0; i < wages.Length; i++) // INICJALIZACJA
                {
                    wages[i] = int.MinValue;
                }
                int firstVertex = generator.Next(n);
                wages[firstVertex] = 0;     // geenerowanie vertex
                for (int i = 0; i < n; i++) // big petla
                {
                    int max = -1;   // cos jak u ale nie u
                    int maxIndex = -1;
                    for (int j = 0; j < n; j++)
                    {
                        if (!mstSet[j] && max < wages[j])  // sprawdzamy z ansza tablica bool
                        {
                            max = wages[j];
                            maxIndex = j;
                        }
                    }
                    mstSet[maxIndex] = true;
                    result.Add(maxIndex);
                    for (int j = 0; j < n; j++)
                    {
                        if (!mstSet[j] && graphTable[maxIndex, j] != 0 && graphTable[maxIndex, j] + max > wages[j])
                            wages[j] = graphTable[maxIndex, j] + max;
                    }
                }
                return result;
            }
        }
            static void Main(string[] args)
        {
            int[,] wages =
            {
                {0, 4, 0, 0, 0, 0, 0, 8, 0 },
                {4, 0, 8, 0, 0, 0, 0, 11, 0 },
                {0, 8, 0, 7, 0, 4, 0, 0, 2 },
                {0, 0, 7, 0, 9, 14, 0, 0, 0 },
                {0, 0, 0, 9, 0, 10, 0, 0, 0 },
                {0, 0, 4, 14, 10, 0, 2, 0, 0 },
                {0, 0, 0, 0, 0, 2, 0, 1, 6 },
                {8, 11, 0, 0, 0, 0, 1, 0, 7 },
                {0, 0, 2, 0, 0, 0, 6, 7, 0 }
            };
            // graf ze strony: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
            Graph G = new Graph(wages);
            List<int> maxSpanningTree = G.MaxSpanningTree();
            foreach (var item in maxSpanningTree)
            {
                Console.Write(item + " ");
            }
            Console.ReadLine();
        }
    }
}