Нахождение вершин графа

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication40
 
{
    class Graph
    {
        public class Top
        {
            public int Key;
            public int Count;//Количество входящих вершин
            public Top Next;//След. вершина
            public Rib Ribs;
            public bool Flag;//Для обхода
            public int Range;//Расстояние от текущей вершины до выбранной(Для задания)
        }
 
        public class Rib
        {//Ребро
            public Top Id;//ВершинаDFSт ит
            public Rib Next;//След. ребро
            public int weight;//Вес
        }
 
        public Top Head;//Начало
        public Top End;//Конец
 
        public Graph()
        {//Новый граф
            Head = null;
            End = null;
        }
 
        public List<int> ReturnList()
        {
            List<int> list = new List<int>();
            for (Top node = Head; node != null; node = node.Next)
            {
                list.Add(node.Key);
            }
            return list;
        }
 
        public Top SerachTop(int _key)
        {//выбор вершины
            Top p = Head;
            while (p.Key != _key)
            {
                p = p.Next;
            }
            return p;
        }
 
        public void Add(int _key)
        {//Добавляем вершину
            for (Top temp = Head; temp != null; temp = temp.Next)
            {
                if (temp.Key == _key) return;//Выходим если есть такая вершина
            }
            Top p = new Top();
            p.Key = _key;
            if (Head == null)
            {
                Head = p;
                End = p;
            }
            else
            {
                End.Next = p;
                End = p;
            }
        }
 
        public void ConnectTops(int keyPrev, int keyNext, int weight)
        {//Добавляем ребро
            for (var t = this.SerachTop(keyPrev).Ribs; t != null; t = t.Next)
            {
                if (t.Id == this.SerachTop(keyNext)) return;//Есть такое ребро
            }
            Rib temp = new Rib();
            temp.weight = weight;
            temp.Id = this.SerachTop(keyNext);
            this.SerachTop(keyNext).Count++;
            if (this.SerachTop(keyPrev).Ribs == null)
            {//если первое ребро
                this.SerachTop(keyPrev).Ribs = temp;
            }
            else
            {//если ребра уже есть
                Rib _temp = this.SerachTop(keyPrev).Ribs;
                while (_temp.Next != null) _temp = _temp.Next;
                _temp.Next = temp;
            }
        }
 
        public void DeleteConnection(int keyPrev, int keyNext)
        {//Удаляем ребро
            if (this.SerachTop(keyPrev).Ribs.Id == this.SerachTop(keyNext))
            {
                this.SerachTop(keyNext).Count--;
                if (this.SerachTop(keyPrev).Ribs.Next == null)
                {
                    this.SerachTop(keyPrev).Ribs = null;
                }
                else
                {
                    this.SerachTop(keyPrev).Ribs = this.SerachTop(keyPrev).Ribs.Next;
                }
                return;
            }
            Rib t = this.SerachTop(keyPrev).Ribs;
            while (t != null && t.Next != null)
            {
                if (t.Next.Id.Key == keyNext)
                {
                    if (t.Next.Next == null)
                    {
                        t.Next = null;
                    }
                    else
                    {
                        t.Next = t.Next.Next;
                    }
                    this.SerachTop(keyNext).Count--;
                }
                t = t.Next;
            }
        }
 
        public void DeleteTop(int _key)
        {//Удаление вершины
            if (this.SerachTop(_key).Count != 0)
            {
                for (Top _t = Head; _t != null; _t = _t.Next)
                {
                    for (Rib r = _t.Ribs; r != null; r = r.Next)
                    {
                        if (r.Id.Key == _key)
                        {
                            DeleteConnection(_t.Key, r.Id.Key);
                        }
                    }
                }
            }
            for (Rib r = this.SerachTop(_key).Ribs; r != null; r = r.Next)
            {
                DeleteConnection(_key, r.Id.Key);
            }
            if (Head.Key == _key)
            {//Если начало
                if (Head.Next == null)
                {
                    Head = null;
                }
                else
                {
                    Head = Head.Next;
                }
            }
            Top t = Head;
            while (t != null && t.Next != null)
            {
                if (t.Next.Key == _key)
                {
                    if (t.Next.Next == null)
                    {
                        t.Next = null;
                    }
                    else
                    {
                        t.Next = t.Next.Next;
                    }
                }
                t = t.Next;
            }
 
        }
 
        struct RibFormatrix
        {
            public int x;
            public int y;
        }
        List<RibFormatrix> ribColl = new List<RibFormatrix>();
 
        public int[,] Connectivity()
        {//матрица смежности
            ribColl.Clear();
            int count = 0;
            for (Top top = Head; top != null; top = top.Next) count++;
            int[,] temp = new int[count + 1, count + 1];
            count = 1;
            for (Top top = Head; top != null; top = top.Next)
            {
                temp[0, count] = top.Key;
                temp[count, 0] = top.Key;
                count++;
            }
            for (Top top = Head; top != null; top = top.Next)
            {
                int ind = 0;
                for (int i = 1; i < temp.GetLength(0); i++)
                {
                    if (temp[i, 0] == top.Key)
                    {
                        ind = i;
                        break;
                    }
                }
                for (Rib rib = top.Ribs; rib != null; rib = rib.Next)
                {
                    for (int i = 1; i < temp.GetLength(0); i++)
                    {
                        if (temp[0, i] == rib.Id.Key)
                        {
                            temp[ind, i] = 1;
                            RibFormatrix r = new RibFormatrix();
                            r.x = ind;
                            r.y = i;
                            ribColl.Add(r);
                            break;
                        }
                    }
                }
            }
            return temp;
        }
 
        public object[,] Incident()
        {
            int countRow = 0;
            for (Top top = Head; top != null; top = top.Next) countRow++;
            object[,] result = new object[countRow + 1, ribColl.Count + 1];
            int count = 0;
            for (Top top = Head; top != null; top = top.Next)
            {
                result[count + 1, 0] = top.Key;
                count++;
            }
            for (int i = 0; i < ribColl.Count; i++)
            {
                string str = string.Format("{0};{1}", ribColl[i].x, ribColl[i].y);
                result[0, i + 1] = str;
            }
            for (int i = 0; i < ribColl.Count; i++)
            {
                result[ribColl[i].y, i + 1] = -1;
                result[ribColl[i].x, i + 1] = 1;
            }
            return result;
        }
 
        public int[,] Accessability()
        {
            int n = 0;
            for (var t = Head; t != null; t = t.Next) n++;
            int[,] accessibility = new int[n, n];
            int[,] temp_matx = new int[n, n];
            int[,] _conn = new int[n, n];
            for (int i = 0; i < this.Connectivity().GetLength(0) - 1; i++)
            {
                for (int j = 0; j < this.Connectivity().GetLength(1) - 1; j++)
                {
                    temp_matx[i, j] = this.Connectivity()[i + 1, j + 1];
                    _conn[i, j] = this.Connectivity()[i + 1, j + 1];
                }
            }
            for (int t = 0; t < n - 1; t++)
            {
                temp_matx = Multiplication(_conn, temp_matx);
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        accessibility[i, j] += temp_matx[i, j];
                    }
                }
            }
            int[,] result = new int[n + 1, n + 1];
            n = 1;
            for (Top top = Head; top != null; top = top.Next)
            {
                result[0, n] = top.Key;
                result[n, 0] = top.Key;
                n++;
            }
            for (int i = 1; i < n; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    result[i, j] = accessibility[i - 1, j - 1] + this.Connectivity()[i, j];
                }
            }
            return result;
        }
        int[,] Multiplication(int[,] a, int[,] b)
        {
            int[,] r = new int[a.GetLength(0), b.GetLength(1)];
            for (int i = 0; i < a.GetLength(0); i++)
            {
                for (int j = 0; j < b.GetLength(1); j++)
                {
                    for (int k = 0; k < b.GetLength(0); k++)
                    {
                        r[i, j] += a[i, k] * b[k, j];
                    }
                }
            }
            return r;
        }
 
        public List<int> SearchTopsRange(int range, int key)
        {//поиск вершин находящихся на расстоянии range от данной key(считая вес ребра равному 1)
            List<int> result = new List<int>();
            result.Add(key);
            while (range != 0)
            {
                List<int> temp = new List<int>();
                for (Top top = Head; top != null; top = top.Next)
                {
                    for (Rib rib = top.Ribs; rib != null; rib = rib.Next)
                    {
                        for (int i = 0; i < result.Count; i++)
                        {
                            if (result[i] == rib.Id.Key)
                            {
                                temp.Add(top.Key);
                            }
                        }
                    }
                }
                result = temp;
                range--;
            }
            return result;
        }
 
        public struct TopRange
        {
            public int key;
            public int weight;
            public TopRange(int k, int w)
            {
                key = k;
                weight = w;
            }
        }
        public void SearchTopRange_New(int range, int key)
        {
            for (Top t = Head; t != null; t = t.Next)
            {
                t.Flag = true;
                t.Range = 0;
            }
            List<TopRange> temp = new List<TopRange>();
            DFS(this.SerachTop(key), temp);
            firstList.Sort();
            for (Top t = Head; t != null; t = t.Next)
            {
                t.Flag = true;
                t.Range = 0;
            }
            er = 0;
            _DFS(this.SerachTop(key), firstList);
        }
        static int er;
        static List<int> firstList = new List<int>();
        void _DFS(Top p, List<int> values)
        {//Обход в глубину
            Rib t = p.Ribs;
            p.Key = firstList[er];
            er++;
            p.Flag = false;
            while (t != null)
            {
                if (t.Id.Flag)
                {
                    _DFS(t.Id, values);
                }
                t = t.Next;
            }
        }
 
        void DFS(Top p, List<TopRange> values)
        {//Обход в глубину
            Rib t = p.Ribs;
            TopRange _t = new TopRange(p.Key, p.Range);
            values.Add(_t);
            firstList.Add(p.Key);
            p.Flag = false;
            while (t != null)
            {
                if (t.Id.Flag)
                {
                    DFS(t.Id, values);
                }
                t = t.Next;
            }
        }
        
 
        static void Main(string[] args)
        {
            Graph t = new Graph();
            t.Add(1);
            t.Add(2);
            t.Add(3);
            t.Add(4);
            t.Add(5); 
            t.ConnectTops(2, 1, 3);
            t.ConnectTops(2, 1, 2);
            t.ConnectTops(1, 5, 4);
            t.ConnectTops(5, 3, 2);
            t.ConnectTops(5, 4, 1);
           
            Top p = t.Head;
            while (p != null)
            {
                Console.WriteLine(p.Key);
                while (p.Ribs != null)
                {
                    Console.WriteLine(" {0}", p.Ribs.Id.Key);
                    p.Ribs = p.Ribs.Next;
                }
                p = p.Next;
 
                Console.Read();
            }
        }
    }
}