Поиск в ширину на C#

despair_101 — Sun, 05 Apr 2020 10:56:12 GMT
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
using System;
using System.Collections.Generic;
using System.Collections;
 
namespace BreadthFirstSearch
{
    class BreadthFirstSearch
    {
        static void Main(string[] args)
        {
            Hashtable graph = new Hashtable();
 
            graph.Add("A", new string[] { "G", "H", "F" });
            graph.Add("M", new string[] { "S", "I", "D" });
            graph.Add("G", new string[] { "L", "D" });
            graph.Add("H", new string[] { "M" });
            graph.Add("I", new string[] { "K", "J" });
 
            Console.WriteLine("Введите начальный узел графа: ");
            string startNode = Console.ReadLine();
 
            Console.WriteLine("Введите конечный узел графа: ");
            string endNode = Console.ReadLine();
 
            int answer = BFS(graph, startNode, endNode);
 
            if (answer == -1)
                Console.WriteLine($"Узлы {startNode} и {endNode} не связанны");
 
            else if (answer == 0)
                Console.WriteLine("Введён один и тот же узёл");
 
            else
                Console.WriteLine($"Расстояние между узлами {startNode} и {endNode} = {answer}");
        }
 
        public static int BFS(Hashtable graph, string startNode, string endNode)
        {
            if (startNode == endNode)
                return 0;
 
            Queue<object> queue = new Queue<object>();
            queue.Enqueue(graph[startNode]);
 
            List<string> used = new List<string>();
            used.Add(startNode);
 
            while (queue.Count > 0)
            {
                string[] nodes;
 
                if ((nodes = queue.Dequeue() as string[]) != null)
                {
                    foreach (string node in nodes)
                    {
                        if (!used.Contains(node))
                        {
                            used.Add(node);
 
                            if (node == endNode)
                                return GetWayLength(CreateReverseGraph(graph, DeleteNoKeys(used, graph.Keys)), startNode, endNode);
 
                            queue.Enqueue(graph[node]);
                        }
                    }
                }
            }
 
            return -1;
        }
 
        public static Hashtable CreateReverseGraph(Hashtable graph, List<string> nodes)
        {
            Hashtable reverseGraph = new Hashtable();
            List<string> used = new List<string>();
 
            foreach (string key in nodes)
            {
                string[] values = graph[key] as string[];
 
                foreach (string value in values)
                {
                    if (!used.Contains(value))
                    {
                        reverseGraph.Add(value, key);
                        used.Add(value);
                    }
                    else
                    {
                        int currentWayLength = GetWayLength(reverseGraph, nodes[0], reverseGraph[value] as string);
                        int potentialWayLength = GetWayLength(reverseGraph, nodes[0], key);
 
                        if (potentialWayLength < currentWayLength)
                            reverseGraph[value] = key;
                    }
                }
            }
 
            return reverseGraph;
        }
 
        public static List<string> DeleteNoKeys(List<string> used, ICollection graphKeys)
        {
            List<string> keys = new List<string>();
 
            foreach (string key in graphKeys)
                keys.Add(key);
 
            List<string> noKeys = new List<string>();
 
            foreach (string node in used)
                if (!keys.Contains(node))
                    noKeys.Add(node);
 
            foreach (string node in noKeys)
                used.Remove(node);
 
            return used;
        }
 
        public static int GetWayLength(Hashtable reverseGraph, string startNode, string endNode)
        {
            int wayLength = 1;
            string node;
            string currentNode = endNode;
 
            while ((node = reverseGraph[currentNode] as string) != startNode)
            {
                currentNode = node;
                wayLength++;
            }
 
            return wayLength;
        }
    }
}
Форум программистов и сисадминов Киберфорум - Блоги - despair_101

Поиск в ширину на C#
