Поиск в глубину по матрице смежности
- Записать матрицу смежности в соответствии с заданием.
- Реализовать алгоритмы DFS и BFS
- Записать возможные маршруты движения и расстояния всего маршрута от центрального вокзала (корня) до всех остальных вершин.
- Результаты вывести на дисплей. Задание Маршруты движения автобусов с Киева;
- Киев –(135) Житомир –(80) Новоград-Волынский –(100) Ровно –(68) Луцк
- Киев –(135) Житомир –(38) Бердичев –(73) Винница –(110) Хмельницкий –(104) Тернополь
- Киев –(135) Житомир –(115) Шепетовка
- Киев –(78) Белая церковь –(115) Умань
- Киев –(78) Белая церковь –(146) Черкассы –(105) Кременчуг
- Киев –(78) Белая церковь –(181) Полтава – (130) Харьков
- Киев –(128) Прилуки –(175) Сумы
- Киев –(128) Прилуки –(109) Миргород Как я понял матрица смежности такая 135 80 100 68 0
135 38 73 110 104
135 115 0 0 0
78 115 0 0 0
78 146 105 0 0
78 181 130 0 0
128 175 0 0 0
128 109 0 0 0
DFS
namespace Graphs
{
class DepthFirstSearch
{
private HashSet<Node> visited;
private LinkedList<Node> path;
private Node goal;
private bool limitWasReached;
public LinkedList<Node> DFS(Node start, Node goal)
{
visited = new HashSet<Node>();
path = new LinkedList<Node>();
this.goal = goal;
DFS(start);
if (path.Count > 0)
{
path.AddFirst(start);
}
return path;
}
private bool DFS(Node node)
{
node.Handler();
if (node == goal)
{
return true;
}
visited.Add(node);
foreach (var child in node.Children.Where(x => !visited.Contains(x)))
{
if (DFS(child))
{
path.AddFirst(child);
return true;
}
}
return false;
}
public LinkedList<Node> DLS(Node start, Node goal, int limit)
{
visited = new HashSet<Node>();
path = new LinkedList<Node>();
limitWasReached = true;
this.goal = goal;
DLS(start, limit);
if (path.Count > 0)
{
path.AddFirst(start);
}
return path;
}
private bool DLS(Node node, int limit)
{
node.Handler();
if (node == goal)
{
return true;
}
if (limit == 0)
{
limitWasReached = false;
return false;
}
visited.Add(node);
foreach (var child in node.Children.Where(x => !visited.Contains(x)))
{
if (DLS(child, limit - 1))
{
path.AddFirst(child);
return true;
}
}
return false;
}
public LinkedList<Node> IDDFS(Node start, Node goal)
{
for (int limit = 1; ; limit++)
{
var result = DLS(start, goal, limit);
if (result.Count > 0 || limitWasReached)
{
return result;
}
}
}
}
}
Граф
namespace Graphs
{
class Program
{
static void Main(string[] args)
{
var n01 = new Node("01");
var n02 = new Node("02");
var n03 = new Node("03");
var n04 = new Node("04");
var n05 = new Node("05");
var n06 = new Node("06");
var n07 = new Node("07");
var n08 = new Node("08");
var n09 = new Node("09");
var n10 = new Node("10");
var n11 = new Node("11");
var n12 = new Node("12");
var n13 = new Node("13");
var n14 = new Node("14");
var n15 = new Node("15");
n01.AddChildren(n02).AddChildren(n03);
n02.AddChildren(n05);
n03.AddChildren(n04);
n04.AddChildren(n05, false).AddChildren(n10, false).AddChildren(n11, false);
n06.AddChildren(n01, false);
n07.AddChildren(n03, false).AddChildren(n08);
n09.AddChildren(n08).AddChildren(n10);
n11.AddChildren(n12).AddChildren(n13);
n12.AddChildren(n13);
n14.AddChildren(n15);
var search = new DepthFirstSearch();
var path = search.DLS(n06, n13,6);
PrintPath(path);
}
private static void PrintPath(LinkedList<Node> path)
{
Console.WriteLine();
if (path.Count == 0)
{
Console.WriteLine("You shall not pass!");
}
else
{
Console.WriteLine(string.Join(" -> ", path.Select(x => x.Name)));
}
Console.Read();
}
}
class Node
{
public string Name { get; }
public List<Node> Children { get; }
public Node(string name)
{
Name = name;
Children = new List<Node>();
}
public Node AddChildren(Node node, bool bidirect = true)
{
Children.Add(node);
if (bidirect)
{
node.Children.Add(this);
}
return this;
}
public void Handler()
{
Console.WriteLine($"visited {this.Name}");
}
}
}
BFS
static void Main(string[] args)
{
Random rand = new Random();
Queue<int> q = new Queue<int>(); //Это очередь, хранящая номера вершин
string exit = "";
int u;
do
{
Console.WriteLine("Задать размер массива самостоятельно? ");
if (Console.ReadLine() == "да")
{
Console.WriteLine("Введите размер:");
u = Convert.ToInt32(Console.ReadLine()) - 1;
if (u < 3)
{
Console.WriteLine("Вы ввели некорректный размер массива. Программа автоматически заменила размер.");
u = rand.Next(3, 5);
}
}
else
u = rand.Next(3, 5);
bool[] used = new bool[u + 1]; //массив отмечающий посещённые вершины
int[][] g = new int[u + 1][]; //массив содержащий записи смежных вершин
for (int i = 0; i < u + 1; i++)
{
g[i] = new int[u + 1];
Console.Write("\n({0}) вершина -->[", i + 1);
for (int j = 0; j < u + 1; j++)
{
g[i][j] = rand.Next(0, 2);
}
g[i][i] = 0;
foreach (var item in g[i])
{
Console.Write(" {0}", item);
}
Console.Write("]\n");
}
used[u] = true; //массив, хранящий состояние вершины(посещали мы её или нет)
q.Enqueue(u);
Console.WriteLine("Начинаем обход с {0} вершины", u + 1);
while (q.Count != 0)
{
u = q.Peek();
q.Dequeue();
Console.WriteLine("Перешли к узлу {0}", u + 1);
for (int i = 0; i < g.Length; i++)
{
if (Convert.ToBoolean(g[u][i]))
{
if (!used[i])
{
used[i] = true;
q.Enqueue(i);
Console.WriteLine("Добавили в очередь узел {0}", i + 1);
}
}
}
}
Console.WriteLine("Завершить программу?");
exit = Console.ReadLine();
Console.Clear();
} while (exit != "да" || exit != "lf");
Console.ReadKey();
}
1 Меня интересует, как Записать возможные маршруты движения и расстояния всего маршрута от центрального вокзала (корня) до всех остальных вершин. 2
var n01 = new Node("01");
var n02 = new Node("02");
var n03 = new Node("03");
var n04 = new Node("04");
var n05 = new Node("05");
var n06 = new Node("06");
var n07 = new Node("07");
var n08 = new Node("08");
var n09 = new Node("09");
var n10 = new Node("10");
var n11 = new Node("11");
var n12 = new Node("12");
var n13 = new Node("13");
var n14 = new Node("14");
var n15 = new Node("15");
сюда мне записать мою матрицу?