Форум программистов, компьютерный форум CyberForum.ru

[C++] графы - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 52, средняя оценка - 4.88
Kill100
 Аватар для Kill100
359 / 248 / 33
Регистрация: 11.12.2010
Сообщений: 1,068
Завершенные тесты: 1
22.03.2011, 18:51     [C++] графы #1
[C++]Алгоритм фронт фолны в графе
Помогите..
Дана матрица Ag (Матрица смежности графа)
И координаты начальной вершины i,j
и кординаты конечной i1,j1
Найти кротчайший путь из i,j в i1,j1 и вывести его на экран..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2011, 18:51     [C++] графы
Посмотрите здесь:

Графы C++
C++ Графы
C++ Графы
C++ Графы
Графы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:29     [C++] графы #2
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
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
 
using namespace std;
 
const int infinity = numeric_limits <int>::max();
 
typedef vector <int> vi;
typedef vector <vector <int> > vvi;
 
int main()
{
    locale::global(locale(""));
    cout << "Введите количество вершин" << endl;
    int n;
    cin >> n;
    vvi v (n, vi(n, 0)); //матрица смежности
    cout << "Введите матрицу" << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];
    
    int start;
    int finish;
    cout << "Введите начальную вершину" << endl;
    cin  >> start;
    cout << "Введите конечную вершину" << endl;
    cin  >> finish;
 
    vi d(n, infinity);   //массив длин
    d[start-1] = 0;
 
    queue <int> q;
    q.push(start-1);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < n; i++)
            if (v[now][i] != 0 && d[now] + v[now][i] < d[i])
            {
                d[i] = d[now] + v[now][i];
                q.push(i);
            }
    }
 
    cout << "Длинна кротчайшого пути равна "
         << d[finish-1] << endl;
    return 0;
}
волновой алгоритм
Kill100
 Аватар для Kill100
359 / 248 / 33
Регистрация: 11.12.2010
Сообщений: 1,068
Завершенные тесты: 1
22.03.2011, 19:42  [ТС]     [C++] графы #3
Цитата Сообщение от Mayonez Посмотреть сообщение
C++
1
2
3
4
    cout << "Введите начальную вершину" << endl;
    cin  >> start;
    cout << "Введите конечную вершину" << endl;
    cin  >> finish;
волновой алгоритм
как вершина может быть задана 1 цифрой??
или я что то не до понмаю???
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:56     [C++] графы #4
в моем понимании граф - это
[C++] графы
вершины - кружочки с номерами

матрица смежности для него
0 1 8 6 3
1 0 7 5 2
8 7 0 11 7
6 5 11 0 5
3 2 7 5 0
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:58     [C++] графы #5
Цитата Сообщение от Kill100 Посмотреть сообщение
как вершина может быть задана 1 цифрой??
так как в кружочках одна цифра, а кружочки - это вершины, значит вершину графа можно задать одной цифрой, К.О.
Yandex
Объявления
22.03.2011, 19:58     [C++] графы
Ответ Создать тему
Опции темы

Текущее время: 03:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru