Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
2 / 2 / 0
Регистрация: 08.02.2015
Сообщений: 191
1

Поиск длины кратчайшего маршрута между вершинами s и d графа

22.06.2018, 00:33. Показов 1436. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задание. Спроектировать класс GraphM

Описание алгоритмов.

Метод private int bfsM(int s,int d).

* Выполняет обход графа в ширину. Возвращает длину кратчайшего маршрута.

Метод public override string ToString().

* Выполняет преобразование для вывода длины кратчайшего маршрута.

Конструктор public GraphM(int nt, int [,] g,int s,int d)

Каркас программы.

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
class GraphM
 
{
 
int[,] G; int n; int nM; int[] mark;
 
public GraphM(int nt, int [,] g,int s,int d)
 
{
 
n=nt;
 
G=new int[n,n];
 
for (int i = 0; i < n; i++)
 
for (int j = 0; j < n; j++) G[i, j] = g[i, j];
 
mark = new int[nt];
 
for (int i = 0; i < n; i++)
 
mark[i] = 0;
 
nM = 0;
 
nM = bfsM(s,d);
 
}
 
int bfsM(int s,int d)
 
{
 
Queue<int> Q,M; mark[s] = 1; int vt = s;
 
Q = new Queue<int>();
 
M= new Queue<int>();
 
Q.Enqueue(vt); M.Enqueue(0);
 
int nMt;
 
while (true) {
 
vt=Q.Dequeue();
 
nMt=M.Dequeue(); . . . }
 
nM = nMt;
 
return nM;
 
}
 
public override string ToString()
 
{. . . }
 
}
 
class Program
 
{
 
static void Main(string[] args)
 
{
 
StreamReader R = new StreamReader("in.txt");
 
StreamWriter W = new StreamWriter("out.txt");
 
int i;int[,] A;string[] As; int n; int s,d;
 
As = R.ReadLine().Split();
 
n = As.Length;
 
A = new int[n,n];
 
i=0;
 
for (int j = 0; j < n; j++) A[i,j] = Convert.ToInt32(As[j]);
 
for (i++; i < n; i++) {
 
As = R.ReadLine().Split();
 
for (int j = 0; j < n; j++) A[i, j] = Convert.ToInt32(As[j]);
 
}
 
As = R.ReadLine().Split();
 
s=Convert.ToInt32(As[0]);
 
d=Convert.ToInt32(As[1]);
 
GraphM oG = new GraphM(n, A,s,d);
 
W.WriteLine(oG);
 
R.Close();
 
W.Close();
 
}
 
}
Пример исполнения программы.

in.txt

0 1 1 1 0 0

0 0 0 1 0 0

0 0 0 0 0 1

0 0 0 0 1 0

0 0 0 0 0 1

0 0 0 0 0 0

0 5

out.txt

Длина кратчайшего маршрута: 2

Нужно написать в двух местах несколько строк вместо троеточий. Помогите пожалуйста, очень срочно надо(
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.06.2018, 00:33
Ответы с готовыми решениями:

Поиск кратчайшего маршрута между населенными пунктами
Написать програму поиска кратчайшего маршрута между населенными пунктами.

Длина кратчайшего пути между двумя вершинами графа
Найти длину кратчайшего пути между двумя вершинами графа

Написать программу для нахождения кратчайшего пути между заданными вершинами графа
visual studio windows forms нужна программа,которая будет вычислять кратчайший путь от вершины a...

Как в случае связного обыкновенного графа определить длину кратчайшего пути между вершинами
Пусть G = (V,E) -- обыкновенный граф, А(G) -- матрица смежности этого графа, отвечающая нгекоторой...

0
22.06.2018, 00:33
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.06.2018, 00:33
Помогаю со студенческими работами здесь

Поиск кратчайшего пути между заданными вершинами
Добрый день. Прошу помощи. Есть задача :&quot;Даны два слова и словарь. Требуется построить цепочку слов...

Поиск кратчайшего пути в графе между вершинами
Добрый вечер подскажите, пожалуйста, я ищу кратчайший путь в графе: m(a, d). m(c, d). m(c, e)....

Поиск кратчайшего пути между вершинами на основе очереди
Задан ориентированный граф вида матрицы смежности. Нужно определить кратчайшее расстояние от одной...

Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
Доброго всем время суток!! В универе задали на РГР написать программу в С++, которая находит ...


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

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