11 / 11 / 6
Регистрация: 03.04.2011
Сообщений: 627
1

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

01.09.2012, 08:10. Показов 3496. Ответов 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
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.09.2012, 08:10
Ответы с готовыми решениями:

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

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

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

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

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

Добавлено через 19 часов 39 минут
повторюсь не у кого записей по работе с графом не осталось?
0
11 / 11 / 6
Регистрация: 03.04.2011
Сообщений: 627
04.09.2012, 19:35  [ТС] 3
.....
0
0 / 0 / 4
Регистрация: 29.05.2016
Сообщений: 13
30.05.2016, 10:53 4
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.05.2016, 10:53
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru