Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 21.04.2014
Сообщений: 2

Найти пути графа

09.01.2015, 01:37. Показов 627. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем доброй ночи!
Задачка такого характера. Вводятся кол-во вершин и дуг. Вводится матрица инцидентности графа. Вводятся две вершины. ( В моем случае они не буквенные, а числовые. Дуги также числовые.) И нужно найти все пути.
например матрица такая:
Число вершин 5, дуг 7.
-1 1 0 0 0
1 0 0 -1 0
0 1 -1 0 0
0 0 1 0 -1
-1 0 1 0 0
1 0 0 0 -1
0 0 0 -1 1
То программа должна вывести
2=>3=>1=>4
2=>3=>1=>5=>4
2=>1=>4
2=>3=>5=>4
Сама программа.
Pascal
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
program my;
const n= 100; m= 100;
var
i, j,k,e: integer;
iVer, iDug, iNachVer, iEndVer, iSpr,iVidG: integer;
A: array [1..n, 1..m] of integer;
B: array [1..n, 1..m] of integer;
boo: boolean;
 
begin
boo:=true;
i:=0; j:=0; iVer:=0; iDug:=0; iNachVer:=0; iEndVer:=0;
writeln('Введите число вершин'); readln(iVer);
writeln('Введите число дуг'); readln(iDug);
if (iVer>0)and (iDug>0)and (2*iVer >=iDug) and (iVer <= iDug) then
begin
writeln('Если граф ориентированный введите 1,в противном случае - 0'); readln(iVidG);
        for i:=1 to iDug do
        begin
          for j:=1 to iVer do
            begin
            write(' Элемент ', i,' строки, ',j,' столбца = ');
            readln(A[i, j]);
            end;
        end;
 
        writeln(' Получившаяся матрица инцидентности: ');
 
        for i:=1 to iDug do
        begin
        for j:=1 to iVer do
          begin
          write(A[i, j]:5);
          end;
          writeln
        end;
 
writeln('Введите номер начальной вершины'); readln(iNachVer);
writeln('Введите номер конечной вершины'); readln(iEndVer);
j:=iNachVer;
if iVidG = 0 then
begin
write(iNachVer,'=>');
WHILE BOO do
begin
 
        for i:=1 to iDug do
      begin
      iSpr:= iSpr+ A[i,j];
      end;
if (iSpr = 0) and (A[iEndVer,iEndVer]= 0) then BOO:=false else iSpr:=0;
 
     for i:=1 to iVer do
       begin
        if (A[i,iNachVer]= 1) then
          begin
          A[i,iNachVer]:= 0;
          iNachVer:=i;
          write(iNachVer,'=>');
          break
          end;
      end;
     A[iEndVer,iEndVer]:=1;
     for i:=1 to iDug do
      if (A[iNachVer,i]= 1) then
      begin
        A[iNachVer,i]:= 0;
          if iNachVer= iEndVer then
            begin
            iNachVer:=j;
             writeln(' ');
            end
          else  iNachVer:=i;
          break;
      end;
 
end;
end
else
 
begin
WHILE BOO do
begin
 
        for i:=1 to iDug do
      begin
      iSpr:= iSpr+ abs(A[i,j]);
      end;
if (iSpr = 0) and (A[iEndVer,iEndVer]= 0) then BOO:=false else iSpr:=0;
 
     for i:=1 to iVer do
     begin
        if (A[i,iNachVer]= 1) then
          begin
          A[i,iNachVer]:= 0;
          iNachVer:=i;
          write(iNachVer,'=>');
          break
          end;
     end;
     A[iEndVer,iEndVer]:=1;
     for i:=1 to iDug do
      if (A[iNachVer,i]= -1) then
      begin
        A[iNachVer,i]:= 0;
          if iNachVer= iEndVer then
            begin
            iNachVer:=j;
             writeln(' ');
            end
          else  iNachVer:=i;
          break;
      end;
 
end
end;
end
 
ELSE writeln ('VOT TOLKO NE NADO A?');
end.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.01.2015, 01:37
Ответы с готовыми решениями:

Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик глубины рекурсии WG)
помоги, пожалуйста, нужна программа:wall: Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик...

Нахождение длины кратчайшего пути от одной вершины-источника ко всем остальным вершинам графа
Напишите программу, реализующую нахождение длины кратчайшего пути от одной вершины – источника ко всем остальным вершинам графа с...

Найти все пути, соединяющие вершину графа v1 с вершинной с заданным номером m
По заданной матрице смежности вершин ориентированного графа найти все пути, соединяющие вершину v1 с вершинной с заданным номером m. ...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
09.01.2015, 01:37
Помогаю со студенческими работами здесь

Вывод пути графа, при котором получится максимальное значение
входные данные: 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Вывести путь, при котором получится максимальное значение. Например здесь...

Определить номера вершин графа, в которых пересекаются кратчайшие пути из вершин
Дано взвешенный граф в котором насчитывается N вершин и M ребер. Необходимо определитить номера вершин, в которых пересекаются кратчайшие...

кратчайшие пути из одной заданной вершины графа в другую
Найти, если возможно, кратчайшие пути из одной заданной вершины в другую и наоборот. Осталась последняя задача, но...

Создание графа по матрице и поиск кратчайшего пути из одного графа в другой
Доброго времени суток. Задали задание по матрице составить граф и написать функции 1 функция находит количество путей из графа допустим...

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


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++
8Observer8 17.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru