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

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

01.09.2012, 08:10. Показов 4369. Ответов 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
Ответ Создать тему
Новые блоги и статьи
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru