using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpApp.DataStructureAlgorithm
{
    public class Graph
    {
        char[] nodeArr;
        int[,] edgeArr;
        int NodeCount
        {
            get { return nodeArr.Length; }
        }
        int max = 888888;
        int Max
        {
            get { return max; }
            set { max = value; }
        }
        int this[int i, int j]
        {
            get { return edgeArr[i, j]; }
            set { edgeArr[i, j] = value; }
        }
        public Graph(int num)
        {
            nodeArr = new char[num];
            edgeArr = new int[num, num];
            BuildGraph();
        }
        char this[int i]
        {
            get { return nodeArr[i]; }
            set { nodeArr[i] = value; }
        }

        void BuildGraph()
        {
            for (int i = 0; i < nodeArr.Length; i++)
            {
                char nodeName;
                Random rand = new Random((int)DateTime.Now.Ticks);
                do
                {
                    nodeName = (char)rand.Next(99, 122);
                } while (nodeArr.Where(t => t == nodeName).ToArray().Length>0 &&nodeArr[0]!=0);

                nodeArr[i] = nodeName;
                for (int j = 0; j <=i; j++)
                {
                    if (i == j) continue;

                    if (i - j != 2)
                    {
                        this[i, j] = rand.Next(1, 10);
                    }
                    else
                    {
                        this[i, j] = Max;
                    }
                    this[j, i] = this[i, j];
                }
            }
        }
        public int BuildMST()
        {
            int[] chosenNode = new int[NodeCount];
            int[][] candidateEdge = new int[NodeCount - 1][];
            Random rand = new Random((int)DateTime.Now.Ticks);
            int iNode = rand.Next(0, NodeCount - 1);
            int sumPath = 0;
            Console.WriteLine(this[iNode]);
            for (int j = 0; j < NodeCount - 1; j++)
            {
                chosenNode[iNode] = 1;
                int[] shortEdge = new int[2];
                int iShort = 0;
                for (int i = 0; i < candidateEdge.Length; i++)
                {
                    if (candidateEdge[i] == null)
                    {
                        candidateEdge[i] = new int[] { iNode, i };
                    }

                    if (chosenNode[i] == 1 && chosenNode[candidateEdge[i][0]] == 1) continue;

                    if (shortEdge[0] == 0 && shortEdge[1] == 0)
                    {
                        shortEdge[0] = candidateEdge[i][0];
                        shortEdge[1] = candidateEdge[i][1];
                        iShort = i;
                    }

                    if (this[shortEdge[0], shortEdge[1]] > this[iNode, candidateEdge[i][1]])
                    {
                        shortEdge[0] = iNode;
                        shortEdge[1] = candidateEdge[i][1];
                        iShort = i;
                    }

                    if (this[iNode, candidateEdge[i][1]] < this[candidateEdge[i][0], candidateEdge[i][1]])
                    {
                        candidateEdge[i][0] = iNode;
                    }
                }
                chosenNode[shortEdge[0]] = 1;
                iNode = shortEdge[0];
                sumPath += this[shortEdge[0], shortEdge[1]];
            }
            return sumPath;
        }
    }
}