Форум программистов, компьютерный форум, киберфорум
C++ Builder
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/22: Рейтинг темы: голосов - 22, средняя оценка - 4.82
11 / 11 / 6
Регистрация: 03.04.2011
Сообщений: 631

Создание графа по матрице и поиск кратчайшего пути из одного графа в другой

01.09.2012, 08:10. Показов 4411. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток.
Задали задание по матрице составить граф и написать функции
1 функция находит количество путей из графа допустим 1 в граф 6
2 функция находит кратчайший путь из графа 1 в граф 5
из какого графа будет искатся путь вводит пользователь, так же пользователь заполняет матрицу по которой строится граф.
У меня ума хватило только на что чтоб задавалась размерность матрицы пользователем, чтоб блокировалась основная диагональ и заполнялась нулями и если связь была с графом 1-5 то и синхронно при нажатии кнопки создание графа появлялась в матрице единица отоброжающая что есть связь между 5-1 тоесть синхронно. Может кто делал такое задание остались материалы?
Если да киньте пожалуйста срочно нужно.
Ну или подскажите как доделать? я не могу понять как программно создать граф его узлы и от одного графа перемещатся к другому.
файл я прикрепил чтоб можно было на компе посмотреть что у меня. ну и код выставляю
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
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 
A=StrToInt(Edit1->Text);
StringGrid1->RowCount=A;
StringGrid1->ColCount=A;
StringGrid1->Col = 1;
StringGrid1->Row = 0;
for (int i=0; i < A; i++) {
StringGrid1->Rows[i]->Clear();
StringGrid1->Cols[i]->Clear();
StringGrid1->Cells[i][i]=0;
}
}
/////////////////////////////////////////////////
void __fastcall TForm1::StringGrid1SelectCell( TObject *Sender, int ACol, int ARow, bool &CanSelect) {
    if (StringGrid1->Cells[ACol][ARow]==0) // будет под запретом ячейки главной диагонали
        {
                CanSelect = false;
        }
}
//---------------------------------------------------------------------------
 
 
 
void __fastcall TForm1::Button2Click(TObject *Sender)//ставит 1 в симметрично расположенную ячейку
{
for (int Col=0; Col < A; Col++)
for (int Row=0;Row<A;Row++){
if (StringGrid1->Cells[Col][Row]==1 ) {
StringGrid1->Cells[Row][Col]=1;
}
 
}
}
Вложения
Тип файла: rar древо графов.rar (6.5 Кб, 45 просмотров)
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
01.09.2012, 08:10
Ответы с готовыми решениями:

Нахождение кратчайшего пути графа
Товарищи программисты! Помогите пожалуйста! Очень нужна программа на С++ Builder для нахождения кратчайшего пути в графе любым из...

Нахождение кратчайшего пути от одной вершины графа до другой
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include &lt;iostream.h&gt; #include...

Библиотека алгоритмов для поиска кратчайшего пути графа
Создать библиотеку алгоритмов. в ней создать 2 алгоритма поиска кратчайшего пути графа (Дейкстры и Флойда). Результат должен выводиться...

3
11 / 11 / 6
Регистрация: 03.04.2011
Сообщений: 631
02.09.2012, 13:42  [ТС]
хелп ми ! люди ну неужели никто такие задания в универе не делал?

Добавлено через 19 часов 39 минут
повторюсь не у кого записей по работе с графом не осталось?
0
11 / 11 / 6
Регистрация: 03.04.2011
Сообщений: 631
04.09.2012, 19:35  [ТС]
.....
0
0 / 0 / 4
Регистрация: 29.05.2016
Сообщений: 13
30.05.2016, 10:53
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
#include<bits/stdc++.h>
#define pairr pair<int,int>
#define pb push_back
#define s second
#define f first
#define mp make_pair
using namespace std;
priority_queue<pairr,vector<pairr>,greater<pairr> >pq;
vector<int>dist(100005,INFINITY);
vector<vector<pairr> >m;
int n,k,h,t,d,v,u,x,y,z,to;
int main()
{
   cin>>n>>k;
   m.resize(n+1);
   cin>>h>>t;
   for(int i=0;i<k;i++)
   {
       cin>>x>>y>>z;
       m[x].pb(mp(y,z));
       m[y].pb(mp(x,z));
   }
   pq.push(mp(0,h));dist[h]=0;
   while(!pq.empty())
   {
       d=pq.top().f;v=pq.top().s;pq.pop();
       if(d>dist[v])continue;
       for(to=0;to<m[v].size();to++)
       {
           int r=m[v][to].f;
           if(dist[r]>dist[v]+m[v][to].s)
           {
               dist[r]=dist[v]+m[v][to].s;
               pq.push(mp(dist[r],r));
           }
       }
   }
   cout<<dist[t]<<endl;
   return 0;
}
Добавлено через 22 секунды
находит наикратчайший путь между парой вершин

Добавлено через 1 минуту
Решено по следующему формату(у меня обозначения другие,не как в условии)


Формат входных данных

Первая содержит два натуральных числа n и m — количество вершин и ребер графа соответственно. Вторая строка содержит натуральные числа s и t — номера вершин, длину пути между которыми требуется найти (s, t ≤ n, s <> t).

Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi — номера концов ребра и его вес соответственно (bi, ei ≤ n, 0 ≤ wi ≤ 100 000).

Гарантируется, что существует путь из s в t.

Добавлено через 17 минут
А этот код находит количество путей между вершинами

Добавлено через 10 секунд
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
#include <bits/stdc++.h>
#define pairr pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
vector<vector<int> >g;
int n,m,na,kon,x,y,k=0;
int used[100]={0};
void dfs(int v);
int main()
{
 
    cin>>n>>m;
    g.resize(n+1);
    cin>>na>>kon;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(na);
    cout<<k<<endl;
    return 0;
}
void dfs(int v)
{
    if(v==kon){k++;}
    used[v]=1;
    for(int to=0;to<g[v].size();to++)
    {
        int i=g[v][to];
        if(used[i]==0)dfs(i);
    }
    used[v]=0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.05.2016, 10:53
Помогаю со студенческими работами здесь

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

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

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

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Поиск кратчайшего пути в матрице
Привет всем, есть задание: &quot;Считать из файла input3.txt двумерный массив. Каждая ячейка имеет вес указанный в матрице, необходимо найти...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Переходник USB-CAN-GPIO
Eddy_Em 20.03.2026
Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .
Оттенки серого
Argus19 18.03.2026
Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .
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 и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru