Помогите с кодом для DFS с рекурсией

150
06 апреля 2019, 08:30

Помогите с кодом на C# для рекурсивного поиска пути в графе

Но когда я ввожу данные, консоль выводит Process is terminated due to StackOverflowException. Не понимаю в чём проблема

P.S. Сори, если похожий вопрос уже был. Я искал, но не нашёл.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp3
{
    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph("Graph.txt");
            string start = Console.ReadLine();
            string target = Console.ReadLine();
            Console.WriteLine(g.DFSWithRecursion(start, target));
        }
    }
    class Edge
    {
        public string adj;
        public string vertices;
        public Edge(string c, string v)
        {
            adj = c;
            vertices = v;
        }
    }
    class Graph
    {
        public List<Edge> edges;
        public Graph(string path)
        {
            string[] data = System.IO.File.ReadAllLines(path);
            edges = new List<Edge>();
            foreach (var i in data)
            {
                string[] s = i.Split(' ');
                edges.Add(new Edge(s[0], s[1]));
                edges.Add(new Edge(s[1], s[0]));
            }
        }
        public bool DFSWithRecursion(string now,string target)
        {
            Dictionary<string, string> parents = new Dictionary<string, string>();
            foreach (var i in edges)
            {
                if (!parents.ContainsKey(i.adj))
                    parents.Add(i.adj, null);
                if (!parents.ContainsKey(i.vertices))
                    parents.Add(i.vertices, null);
            }
            List<string> closed = new List<string>();
            if (now == target)
            {
                return true;
            }
            else
            {
                closed.Add(now);
                List<string> descendantList = edges.Where(p => p.adj == now).Select(p => p.vertices).ToList();
                foreach (var descendant in descendantList)
                {
                    if (!closed.Contains(descendant))
                    {
                        if (DFSWithRecursion(descendant, target))
                        {
                            Console.WriteLine(descendant);
                            parents[descendant] = now;
                            return true;
                        }
                    }
                }
                return false;
            }
        }
    }
}
READ ALSO
Gif изображение в Android Xamarin

Gif изображение в Android Xamarin

Есть метод для появления Gif

178
Упростить код десериализации

Упростить код десериализации

Помогите упростить кодНаверно, это можно сделать через LINQ или как-то ещё

161
Архитектура авторизации в приложении

Архитектура авторизации в приложении

Мое приложение авторизовываться с помощью одного метода Authorize в сервисе wcfАргумент ы метода - логин, пароль, параметры машины пользователя...

146