0 / 0 / 0
Регистрация: 24.11.2017
Сообщений: 4
1

Рекурсивный поиск в глубину в графе

25.11.2018, 19:05. Показов 3433. Ответов 5

Author24 — интернет-сервис помощи студентам
Помогите с рекурсивным поиском в глубину. Как я понял, у меня не помечает какие ребра были посещены, но я без понятия как это сделать. Подскажите, пожалуйста как это реализовать.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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;
            }
        }
    }
}
P.S. Сорян, если похожая тема уже есть. Просто я искал и не нашёл, либо просто плохо ищу) И заранее спасибо, тем кто поможет)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.11.2018, 19:05
Ответы с готовыми решениями:

Поиск в ширину, глубину в графе
Есть ли у кого программка для поиска в ширину/в глубину на графах с использованием матрицы...

Поиск в глубину
Есть граф, заданный матрицей смежности. Нужно найти путь от указанной вершины до всех остальных....

Поиск в глубину
Необходимо реализовать Поиск в глубину для Ориентированного графа. Граф Взвешенный. Граф следует...

Логическое пограмирование. Поиск в глубину
Привет. Нужна помощь в написании программ: ханойские башни и про 15 монет. Условия. Ханойские...

5
Модератор
Эксперт .NET
15569 / 10800 / 2805
Регистрация: 21.04.2018
Сообщений: 31,764
Записей в блоге: 2
25.11.2018, 19:33 2
Цитата Сообщение от theDevilSingle Посмотреть сообщение
Помогите с рекурсивным поиском в глубину. Как я понял, у меня не помечает какие ребра были посещены, но я без понятия как это сделать. Подскажите, пожалуйста как это реализовать.
Граф у Вас задан в виде общего списка рёбер смежности.
А зачем здесь рекурсия в принципе? Это же одномерный список. Здесь рекурсия совершено не нужна.

Добавлено через 3 минуты
Или Вы ищете путь от одной вершины к другой? Тогда почему метод DFSWithRecursion возвращает bool , а не путь - список рёбер ?
0
0 / 0 / 0
Регистрация: 24.11.2017
Сообщений: 4
26.11.2018, 16:43  [ТС] 3
У меня просто задание сделать именно рекурсивный поиск
0
Модератор
Эксперт .NET
15569 / 10800 / 2805
Регистрация: 21.04.2018
Сообщений: 31,764
Записей в блоге: 2
26.11.2018, 16:57 4
Цитата Сообщение от theDevilSingle Посмотреть сообщение
У меня просто задание сделать именно рекурсивный поиск
Ищете Вы что?
0
0 / 0 / 0
Регистрация: 24.11.2017
Сообщений: 4
26.11.2018, 17:00  [ТС] 5
путь по графу
0
Модератор
Эксперт .NET
15569 / 10800 / 2805
Регистрация: 21.04.2018
Сообщений: 31,764
Записей в блоге: 2
26.11.2018, 17:07 6
Цитата Сообщение от theDevilSingle Посмотреть сообщение
путь по графу
Тогда почему метод DFSWithRecursion возвращает bool, а не путь?

Добавлено через 1 минуту
У Вас граф может быть не связанный?
0
26.11.2018, 17:07
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.11.2018, 17:07
Помогаю со студенческими работами здесь

Рекурсивный поиск не работает
Делал что-то вроде бд, всё неплохо, но поиск всегда возвращает 0. public int Find(string str) ...

Рекурсивный бинарный поиск
Помогите, ребята) нужна программа для рекурсивного бинарного поиска. Этот кусок кода может поможет....

Рекурсивный поиск файлов в C# .NET
Как реализовать? Нужно получить полный путь к файлу, включая имя файла. Есть функция FindInFiles...

Поиск пути в графе
Помогите, пожалуйста! Граф с двунаправленными связями реализован таким образом: Это массив A...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru